Home

最近はRustの勉強がてらAtcoderやAOJの簡単な問題を解いているが、その際に順列を生成する関数が欲しくなったので実装してみた (Atcoderでは itertools クレートを使えるので不要だが)。 実装全体はこちら: Generate k-permutations in Rust 動き方としては、 let s = "ABCD"; s.chars().permutations(2).for_each(|cs| { println!("{:?}", cs); }); // Output: // ['A', 'B'] // ['A', 'C'] // ['A', 'D'] // ['B', 'A'] // ['B', 'C'] // ['B', 'D'] // ['...

年末年始の休みでRustを触っており、勉強がてら線形回帰を実装してみた。 線形回帰 まずは線形回帰について簡単に解説しておく。PRMLの3.1節を参考にした。 回帰は連続量である目的変数 $y$ を $d$ 次元の説明変数 $x = (x_1, \dots, x_D)^\text{T} \in \mathbb{R}^d$ を使って予測することである。パラメータ $w’ = (w’_0, \dots, w’_D)^\text{T} \in \mathbb{R}^{d+1}$ を用いると、線形回帰を表すモデル $y$ は \[y(x, w') = w'_0 + \sum_{i=1}^d w'_ix_i \tag{1}\] のように表せる (ここでは $y \in \mathbb{...

最近PuLPという線形計画問題 (や混合整数問題) を解くためのPythonライブラリを触ったのでそれの使い方をメモしておきます。 まず線形計画問題について簡単に説明をします。 線形計画問題とは 用語の復習から。 実数$c_1, \dots, c_n \in \mathbb{R}$に対して、次のように与えられる実変数$x_1, \dots, x_n$の関数 \[f(x_1, \dots, x_n) = c_1x_1 + \dots + c_nx_n\] を線形関数 (linear function) と呼びます。$f$が線形関数で、$b$が実定数のとき、 \[f(x_1, \dots, x_n) = b\] の関係式を線形等式 (linear equality) といい...

スプライン関数 元の現象が連続的なものであっても、実験や統計の結果として得られるデータは離散的なものです。そのため、測定しなかった入力に対する出力が欲しい場合は、手元にある離散的なデータから推定する必要があります。 古典的な推定法としては、Lagrangeの補完法というものがあります。これは、$n$個の点$\{(x_i, y_i)\}_{i=1}^n,\ \ i\neq j \Rightarrow x_i \neq x_j$が与えられたときに多項式を用いてデータを推定するものです。具体的には、 \[P(x) = \sum_{i=1}^n y_ip_i(x)\\ p_i(x) = \prod_{j=1, j\neq i}^n \frac{x - x_j}{x_i - x_j}\] ...

前回の記事の続き。 関数$f$が狭義凸関数であるときにヘッセ行列が正則になる証明を行っていく。以下では、ヘッセ行列の各成分は実数であるとする。 流れ 先に証明の流れを書いておく。 １. 正定値対称行列が正則であることを証明する ２. ヘッセ行列が正定値対称行列であることを証明する ２.１. 狭義凸関数の性質である \[f(x) > f(a) + \nabla f(a)^T (x - a)\] を証明する。 ２.２. $f$を2次のテーラー展開して、ヘッセ行列が式中に現れることを確認する。 \[f(x) = f(a) + \nabla f(a)^T(x - a) + \frac{1}{2}(x - a)^T Hf(c)(x - a)\ \ \ \ (\exis...

Newton法について勉強したので記録する1。なお、この記事ではベクトルをボールド体にせず、スカラと同じように表記する。 語句の定義 狭義凸関数 (strictly convex function) 凸集合$X$を定義域とする関数$f$が、任意の2点 $x_0, x_1 \in X$, $0 \le \lambda \le 1$である任意の実数$\lambda$に対して、 \[f(\lambda x_0 + (1 - \lambda)x_1) < \lambda f(x_0) + (1 - \lambda) f(x_1)\] が成立するとき、$f$は狭義凸関数とよばれる。 (凸集合の定義は前回の記事を参照のこと。) つまり狭義凸関数は凸関数の定義から等号を除いたバー...

凸関数の和は凸関数になるが、それの証明を確認したので記録しておく。 以下では簡単化のために集合$X$は有限次元ユークリッド空間$R^m$の部分集合であるとする。 まず用語の定義から。 凸結合 $X$の2つの点$\boldsymbol{x}_0$, $\boldsymbol{x}_1$をとり、$0 \le \lambda \le 1, \lambda \in \mathbb{R}$である$\lambda$を一つ定める。このとき、 \[\boldsymbol{x} = \lambda \boldsymbol{x}_0 + (1 - \lambda) \boldsymbol{x}_1\] で表される点の集合$\boldsymbol{x}$を、$\boldsymbol{x}_0$,...

小ネタだけど地味に便利だったのでメモ。 macOSにおいて、画像ファイルをPreviewなどのアプリで開いた後にその画像をどこかに貼り付けたいときがある。 今まではFinderを開き、画像ファイルが置いてある場所まで移動してファイルをドラッグ＆ドロップする、という手順を行っていたが、 Previewで開かれるウィンドウの上にあるファイル名が書いてある隣りにある小さなアイコンはドラッグできるので、 それを直接ドラッグしてペーストしたいところにドロップすればコピペが完了する。 ついでに、ファイル名をクリックするとリネームができる。 Previewに限らず、ウィンドウの上にアイコンとファイル名が表示されるタイプのアプリはおそらく全てこの操作ができる。 結構長いことmac使って...