note.momee.mt

• Mutsuha Asadaのノート
• note.momee.mtのリポジトリ
• X: @mutsuha_asada
• GitHub: @momeemt

nixpkgs レビューログ

NixOS/nixpkgsのレビュー時に見逃していた・気を付けるべき点について記録しておく。

習慣

• できるだけ起床してから30〜60分間はnixpkgsへのレビューに充てる
  • 朝の方が当日中に他のレビュワーやコントリビュータからの返信に対応しやすい
• バージョン更新だけなど、レビューしやすいPRは作業の合間に取り組みたい...
  • まだnixpkgs-reviewが実行されていないPRに対して自動で実行しておくツールが欲しい
• 過去にレビューしたPRの更新や、レビュワーから指摘にはできるだけ優先的に対応する
  • これが苦手なのが課題

一般

• Approveしてから他のレビュワーによって改善点が指摘された場合にはメモしておく
• Request Changesを送ってからマージされるまではTodoistに入れて確認するようにする
• Approveしてからコミッタにマージされない場合はNixOS Discourseのprs-ready-for-reviewに投稿する
• Request Changesを送る際にはできるだけ丁寧に改善点について説明する

ログ

2025/06/10

• ocamlPackages.ancient: init at 0.10.0
• ocamlPackages.amqp-client: init at 2.3.0

2025/06/09

• ocamlPackages.kcas: 0.6.1 -> 0.7.0
• ocamlPackages.{landmarks, landmarks-ppx}: 1.4 -> 1.5
• ocamlPackages.mmap: 1.1.0 -> 1.2.0
  • useDune2は古いので削除

2025/06/08

• ocamlPackages.dum: 1.0.1 -> 1.0.3
  • substituteInPlaceに対するオプション--replaceは非推奨になったので、--replace-failなどのオプションを使う。ref
• ocamlPackages.eigen: 0.2.0 -> 0.3.3

2025/06/07

• ocamlPackages.mirage-crypto: 1.2.0 -> 2.0.1
• ocamlPackages.awa: 0.5.1 -> 0.5.2
• ocamlPackages.benchmark: 1.6 -> 1.7
• ocamlPackages.bitwuzla-cxx: 0.6.1 -> 0.8.0
• ocamlPackages.cow: 2.4.0 -> 2.5.0
• ocamlPackages.directories: 0.5 -> 0.6

2025/06/06

• ocamlPackages.encore: 0.8 -> 0.8.1

2025/06/05

• ocamlPackages.lua-ml: 0.9.2 -> 0.9.4
  • odocはドキュメント生成のみに必要（with-doc）なので、buildPhaseには必要ないことがある

2025/06/04

• ocamlPackages.wasm: 2.0.1 -> 2.0.2
  • opamパッケージとしてビルドされているが、upstreamがduneプロジェクトの場合にはbuildDunePackageを用いて書き直した方が良い
• ocamlPackages.ffmpeg: 1.2.1 -> 1.2.5
  • meta.changelogは、テキスト形式の方が扱いやすいので、https://raw.githubusercontent.com/で指定した方が良い
• ocamlPackages.xenstore: 2.3.0 -> 2.4.0 (draft)
  • xenstore-toolがバージョンアップによって消されたAPIを使っていて、かつ報告場所がないので困っている、という旨のコメントをOCamlパッケージをメンテナンスしてる方に投げてみた
• 30分くらいのつもりだったけど2時間経っていた
• SATySFi
  • satysfiDirs.ml
  • ここで~/.opam/配下のパッケージパスを特定している
  • SATYSFI_RUNTIMEを書き換えると出力先を選べる
  • Pythonスクリプト不要かも。satyrographosに処理を委譲できそう

NixOSでフォントが読み込めないとき

fc-cache -rv

詳細

uguisu側で修正したnix-configurationsをoshidori側で反映させたらAlacrittyがnerd-fontsを読み込めないと怒ってきた。実際にnvim-treeのアイコンが表示されなくなっていた。 nix-community/home-manager #6160を読んだら解決した。 どうやらhome-manager switchだけではフォントのリロードが行われないよう。

含意

$A$ ならば $B$ のような論理式を含意といい、$A\to B$ と表現する。 これは、$A$ が正しいとき、$B$ もまた正しいならば正しいことを意味する。

解釈

含意演算子は以下のように評価される。

$A$ が正しくなければ常に $A\to B$ が正しいことの導出

次の2つを用いることで、$A$ が正しくなければ常に $A\to B$ が正しいことを導出できる。

1. $B$ が無条件に正しければ、$A$ の正否に関わらず $A\to B$ は正しい
2. 対偶

まず、$A$ が正しくないとする。 それは $\bar{A}$ が正しいことを意味する。 (1)より $\bar{B}$ の正否に関わらず $\bar{B}\to \bar{A}$ は正しい。 これの対偶を考えると、$A\to B$ も正しい。 したがって、$A$ が正しくなければ常に $A\to B$ は正しい。

集合論

参考資料

• ✅ 筑波大学 GA15121 情報数学A
  • 指定教科書: 論理と集合から始める数学の基礎
• 集合・位相入門
  • 2025/06/27〜
  • きちんとした数学書を読むのは初めてなので、竹内先生の数学書の読み方についてを参考にしている

集合

範囲のはっきりしたものの集まりを集合という。 集合は普通、ラテン大文字で表される。 幾何学的表現を用いて、集合を空間、その元を点と呼ぶこともある。

元

$A$ が1つの集合であるとき、$A$ に含まれる個々のものを $A$ の元（元素、要素とも）という。 もの $a$ が集合 $A$ の元であることを、$a\in A$、あるいは $A\ni a$ で表す。 このことを、$a$ が $A$ に属する、$a$ は $A$ に含まれる、$A$ は $a$ を含むなどという。

$a\in A$ の否定は、$a\notin A$、または $A\not\ni a$ で表す。

$a\in A$ と $a\notin A$ はいずれか一方だけが成り立ち、両方同時に成り立つことや、両方同時に成り立たないことはない。

無限に多くの元を持つ集合を無限集合、有限個の元しか持たない集合を有限集合という。 また固有名詞的に、自然数全体の集合を $\mathbb{N}$、整数全体の集合を $\mathbb{Z}$、有利数全体の集合を $\mathbb{Q}$、実数全体の集合を $\mathbb{R}$ で表す。

$A$ が集合であるとき、どんなもの $a$ を取ってきても $a\in A$ であるか $a\notin A$ であるかは定まっているが、その判定問題が容易に解けるかどうかはまた別問題。

変数と条件

考察の対象となるものを代表的に表す文字を変数という。 変数が表す対象は任意で、数値だけではない。

また、変数を含む文章をその変数についての条件または性質という。 条件 $C$ が変数 $x$ についての条件であることを明示したいとき、$C(x)$ と表す。 ある具体的なもの $a$ を $C(x)$ に代入して得られる文章 $C(a)$ が正しいとき、$a$ は条件 $C$ を満たす、または $a$ は性質 $C$ をもつ、という。 条件 $C$ を満たすようなもの全体は1つの集合を形成する。

記法

一般に、元 $a,b,c,\cdots$ より成る集合を以下のように表す。 これを外延的記法という。

$$\{a,b,c,\cdots \}$$

ただし、この記法はすべての元を列挙するか、簡単に $\cdots$ 部分が推測できるような集合でなければならない。 そこで、ある条件を満たすもの全体の集合、ある性質を満たすもの全体の集合を表現できる、内包的記法を用いる。 条件 $C$ を満たすようなもの全体の集合を、次のように表す。

$$\{x\mid C(x)\}$$

たとえば、$a,b$ を両端とする $\mathbb{R}$ の閉区間は $\{x\mid a\le x\le b\}$、開区間は $\{x\mid a<x<b\}$ である。

空集合

元を全く含まない集合を空集合という。 空集合は $\varnothing$、あるいは外延的記法では $\{\}$ と表す。 たとえば、$\{x\mid x\in \mathbb{R},x^2=-1\}$ は空集合。

空集合 $\varnothing$ は元を含まないから、${\forall }_{a}a\notin \varnothing$ である。

相等

集合 $A,B$ は、全く同じ元から成るとき、すなわち以下が成り立つときに等しいという。 これを、$A=B$ と表す。

$${\forall }_x(x\in A\iff x\in B)$$

同等

2つの文章 $p,q$ が与えられたとき、$p\to q$ とは、$p$ が正しいときに $q$ もまた正しいことを示す。 また、$q\to p$ も成り立つとき、$p\iff q$ と表せて、$p$ と $q$ は（論理的に）同等であるという。

部分集合

Definition 4.1.1 (部分集合).

集合 $A,B$ において、以下を満たすならば $A$ は $B$ の部分集合であるといい、$A\subset B$ または $B\supset A$ と表す。 これを、$A$ は $B$ に含まれる、$B$ は $A$ を含むという。

$${\forall }_x(x\in A\to x\in B)$$

その否定は、$A\not\subset B$、または $B\not\supset A$ と表される。

$A\subset B\wedge A\ne B$ であるとき、$A$ は $B$ の真部分集合であるという。

$A=B$ であるための必要十分条件は、$A\subset B\wedge A\supset B$ が成り立つことである。 もし2つの集合が同等であることを証明したければ、両向きに部分集合であることを示す。

$A\subset B\wedge B\subset C\to A\subset C$ が成り立つことも明らか。

空集合と部分集合

空集合 $\varnothing$ は任意の集合 $A$ の部分集合である。

$$\varnothing \subset A$$

これは、含意を用いて証明できる。 $\varnothing \subset A$ を示すためには、${\forall }_{x}x\in \varnothing \to x\in A$ を示す必要がある。 ここで、${\forall }_{x}x\notin \varnothing$ であるから、常に正しい。 したがって、元の式は正しい。

和集合

記号 $\cup$ は結び、join、cupなどと呼ばれる。 たとえば、$A$ を正の偶数全体の集合、$B$ を正の奇数全体の集合とすると、$A\cup B=\mathbb{N}$。

基本的な性質

包含関係

上位集合閉包

Proposition 4.2.1.1 (和集合の包含関係) より、$A\cup B$ は $A$ と $B$ をどちらも含む。 また、Proposition 4.2.1.2 (和集合の上位集合閉包) より、$A$ も $B$ も含む任意の集合は、$A\cup B$ を含む。 したがって、$A\cup B$ は、$A,B$ の両方を含む最小の集合であると言える。

冪等律

交換律

結合律

結合律の一般化

自分で書いた証明は証明になっていなかったのでチャッピーに教えてもらった。 仮定を適用できる範囲が自分が思っていたより広かった。

結合律の一般化が成り立つので、括弧を省略して次のように表してよい。

$$A_1\cup A_2\cup \cdots \cup A_n=\bigcup _{i=1}^n{A}_i$$

包含と和集合の同値命題

単調性

チャッピーがもっと賢い証明を教えてくれた。 自分が書いた証明は嘘ではないけど冗長っぽい。

かしこ！全く思いつかなかった。

恒等律

教科書を読んでいたら Proposition 4.2.1.7 (包含と和集合の同値命題)を使っても示せることが書かれていた。 結構感動した。

共通部分

記号 $\cap$ は交わり、meet、capなどと呼ばれる。 たとえば、$A$ を正の偶数全体の集合、$B$ を正の奇数全体の集合とすると、$A\cap B=\varnothing$。

一般に、$A\cap B\ne \varnothing$ である時には、$A,B$ は交わるという。 また、$A\cap B=\varnothing$ である時には、$A,B$ は交わらない、または互いに素であるという。

基本的な性質

包含関係

上位集合閉包

ここから、$A\cap B$ は、$A,B$ の両方に含まれる集合のうちで最大のものであることが言える。

冪等律

交換律

結合律

Proposition 4.2.1.6 (和集合の結合律の一般化)の証明と同様に、共通部分のどこにどのような順序で括弧をつけても結果的に得られる集合は変わらない。 したがって、以下のように書ける。

$$A_1\cap A_2\cap \cdots \cap A_n=\bigcap _{i=1}^n{A}_i$$

包含と共通集合の同値命題

線形代数

参考資料

• ✅ 筑波大学 GA15221 線形代数A
  • 2022年春BCに履修
• ✅ 筑波大学 GB10244 線形代数B
  • 2023年春ABに履修
• 筑波大学 GB22501 情報線形代数
• 数研講座シリーズ 大学教養 線形代数
• チャート式シリーズ 大学教養 線形代数
• 基礎数理講座 線形代数汎論

グラム・シュミットの直交化法

$n$ 本の線型独立なベクトル $a_1,a_2,\cdots ,a_n$ から正規直交基底を作る手法。

基底 $u_1$ を計算する

$$u_1=\frac{a_1}{\left|a_1\right|}$$

基底 $u_k$ を計算する

まず、直交化により $v_k$ を計算する。

$$v_k=a_k-\sum _{i=1}^{k-1}(a_k\cdot u_i)u_i$$

次に、正規化して $u_k$ を得る。

$$u_k=\frac{v_k}{\left|v_k\right|}$$

スペクトル分類

任意の正規行列 $A$ は、固有値 ${\lambda }_1,\dots ,{\lambda }_N$ と、固有値 ${\lambda }_i$ の固有空間への射影行列 $P$ を用いて次のように分解できる。

$$A=\sum _{i=1}^N{\lambda }_i{P}_{{\lambda }_i}$$

確率論

参考資料

• 筑波大学 GB11601 確率論
• プログラミングのための確率統計
  • 正直、確率統計をそれぞれ講義で勉強した後に読むものではないと思う
  • 冗長な表現が多くてきちんと知りたい時にはもっと適した本がありそう
  • でも、情報科学をやる上で確率論を学ぶモチベーションを知ることはできるから、入学前くらいで読むのは良さそう
• IT Text 確率統計学

統計学

参考資料

• 筑波大学 GB11621 統計学
• 統計学入門
• IT Text 確率統計学

記述統計

統計データ

分類

データは、質的データと量的データに二分できる。 質的データはカテゴリカルなデータで、量的データは数値として表されるため定量的に大きさを測ることができるデータ。

量的データは、連続的な値を取る計量値と離散的な値を取る計数値に分類できる。

尺度

名義尺度

質的データのうち、性別や学籍番号など、値の大小に本質的な意味を持たない、ラベルとしてのデータ。

順序尺度

質的データのうち、成績などの数値の大小に意味を持つが、数値間の差や比に意味を持たないデータ。

間隔尺度

量的データのうち、気温や偏差値など数値の大小に意味を持ち、数値間の差にも意味を持つデータ。

比率尺度

量的データのうち、身長や体重などのように、数値の大小、差、比、全てに意味を持つデータ。

0（原点）が何もないことを意味していれば比率尺度、そうでなければ間隔尺度のように見分けることができる。

多次元データ

ある学生の身長、のように1つのラベルに対して1つの値だけが与えられているようなデータを1次元データという。 ある学生の身長と体重、のように1つのラベルに対して2つの値が与えられているようなデータを2次元データという。 ある学生の身長、体重、座高のように1つのラベルに対して3つの値が与えられているようなデータを3次元データという。

2次元以上のデータを1次元のデータに対して、多次元データと呼ぶ。

時系列データ

同一の対象の異なった時点での観測値からなるデータを時系列データと呼ぶ。 経済分析や気象学、天文学の現象分析に幅広く利用されている。

クロスセクション・データ

いくつかの異なった対象について調査・実験を行い、観測値を得た場合のデータをクロスセクション・データという。 また、定めた一定範囲の対象に対して時系列データを集めたものをパネル・データという。

度数分布表とヒストグラム

データをある範囲ごとに区切ったとき、その範囲に属する数値の散らばりの様子を度数分布と呼ぶ。 また、それを表にしたものを度数分布表という。 さらに、度数分布表をグラフ化したものをヒストグラムといい、その形状によってデータの分布を直観的に把握することができる。

度数分布表において区切られた各区間を階級、各区間の幅を階級幅、階級のちょうど中央の値を階級を代表する値として階級値、各階級に属するデータ数を度数という。 データの総数に対する度数の割合を相対度数といい、データ数が異なる複数のデータを比較する際に用いられる。 また、度数、相対度数それぞれの累積値を累積度数、累積相対度数と呼ぶ。

ヒストグラムの注目するべき要素

1. 中心の位置
2. ばらつき具合
3. 分布の形
   • データにいくつの山ができるのか
   • 山が複数できる場合は何かの性質により分離すると単峰型のデータにできることがある
   • データを性質ごとに分離することを層別という
4. 外れ値
   • 大部分のデータからかけ離れたごく少数のデータを外れ値という
   • 転記ミスなどの人為的なミスや、重大な異常が潜むことがある

ヒストグラムの作成

1. データ測量単位 $u$ を明確にし、$n$ 個のデータを得る
2. データの最大値、最小値をそれぞれ $x_{\text{max}},x_{\text{min}}$ とし、データの範囲 $r=x_{\text{max}}-x_{\text{min}}$ を求める
3. $c^{\prime }=\sqrt{n}$ を目安に、仮の階級数 $c$ を決める
4. $w^{\prime }=\frac{r}{c}$ を目安に、階級幅 $w$ を決める
   • ただし、$w$ は測量単位の整数倍になるように調整する
5. 最も小さい階級の下側境界値を $x_{\text{min}}-\frac{u}{2}$ として、ここから $w$ ずつ加えていき、各階級の境界値を求める
   • このとき、境界値が $x_{\text{max}}$ より大きくなるまで階級を作る
6. 階級を元に、データの度数を数え、度数分布表を作成する
7. 度数分布表よりヒストグラムを作成する

累積度数のグラフ化

累積度数はヒストグラムと合わせて折れ線グラフで表示すると便利。 同様のグラフを相対度数、相対累積度数にして作成できる。

分析プロセス

統計データの分析における最初の仕事は、分析を行うべき仮説を考えること。 仮説が構築され、分析したい対象が明らかになれば必要なデータが分かる。

必要なデータが元から存在しない場合には、データ獲得を行う必要がある。 この作業は、自然科学の分野では実験、人文社会科学の分野では調査と呼ばれる。 実験や調査の規則や技術については実験計画法、社会調査法と呼ばれる分野がある。

実験や調査により、生のデータである原データを得ることができるが、大規模な実験・調査は費用面や時間面で誰にでもできるわけではない。 行政機関や研究機関、調査会社、第三者の調査結果を利用することも多いが、その場合は原データを獲得できず、何らかの統計処理を施した後の調査結果である統計資料が分析対象の統計データとなる。

分類

あらかじめ統計資料を作成する目的で調査を行い、その結果を集計したものを第一義統計と呼ぶ。 対して、統計資料の作成が目的ではない資料を集計して得た統計資料を第二義統計、業務統計と呼ぶ。

統計資料を加工して作成された統計資料を二次統計、加工統計と呼ぶ。

データ収集の段階では、原データでなく統計資料の場合には、誰が行ったものか、全数調査か標本調査か、誰を対象としたものか、いつの時点のものか、どの地域を対象としたものか、分類の定義はどうなっているかなどの定義に注意する必要がある。

計算理論

参考資料

• ✅ 筑波大学 GB20401 オートマトンと形式言語
  • 2023年秋ABに履修した
• 計算理論の基礎　[原著第3版] 1.オートマトンと言語
• 計算理論の基礎　[原著第3版] 2.計算可能性の理論
• 計算理論の基礎　[原著第3版] 3.複雑さの理論
• 計算できるもの、計算できないもの

画像認識

• $K\times K$ 画素画像は、$K^2$次元実数ベクトルと見なすことができる
• 3次元実数ベクトル空間 $V$ について、$V$ を張る基底は無限個存在するが、3本の基本ベクトルが最もシンプルな基底
  • ${\mathbb{R}}^3=⟨{\mathbf{e}}_1,{\mathbf{e}}_2,{\mathbf{e}}_3⟩$
• $G$ が1次独立な画像ベクトル ${\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3$ で生成されるとき、${\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3$ が基底ベクトルである
  • 3つのベクトルが同一平面上に存在しない

正射影

任意の $v\in V$ は、$v=u+w(u\in U,w\in U^{\perp })$ と一意に表される。 このとき、$v$ に対して $u$ を対応させる写像を $V$ から $U$ への正射影であるといい、$p{r}_u$ と書く。

また、$V$ を計量ベクトル空間、$U$ を $V$ の部分空間とする。 $u_1,u_2,\dots ,u_k$ を $U$ の正規直交基底とすると、正射影は以下のように書ける。

$$p{r}_u=(v,u_1)u_1+(v,u_2)u_2+\cdots +(v,u_k)u_k$$

画像ベクトル空間における正射影は、特徴抽出として極めて重要。 たとえば、$v$ の1次元部分空間 $⟨{\mathbf{e}}_1⟩$ への正射影は、ベクトル $\mathbf{v}$ から画像成分 ${\mathbf{e}}_1$ のみを抽出することになる。 また、係数 $a_1$ がその成分の強さを意味する。

射影行列

射影行列 $\mathbf{P}$（$\mathbf{P}\in {\mathbb{R}}^{d\times d}$）は、ベクトル $\mathbf{x}$ を$n$次元部分空間 $U=⟨e_1,e_2,\cdots ,e_n⟩$ への正射影ベクトル ${\mathbf{x}}^{\prime }$ に写像する。

$$\begin{array}{rl}{\mathbf{x}}^{\prime }& =\mathbf{Px}\\ & =\sum _{i=1}^n{\mathbf{e}}_i{\mathbf{e}}_i^T\end{array}$$

部分空間 $U$ への射影行列を $\mathbf{P}$ とするとき、$U$ の直交補空間 $U^{\perp }$ への正射影を表す射影行列 $\mathbf{Q}$ は以下のようになる。 ただし、行列 $\mathbf{I}$ は、射影行列 $\mathbf{P}$ と同じサイズの単位行列。

$$\begin{array}{rl}\mathbf{Q}& =\mathbf{I}-\mathbf{P}\\ {\mathbf{x}}^{\prime }& =\mathbf{Q}\mathbf{x}\end{array}$$

画像パターン分布の局在性

ある同種の物体の画像パターンは相関を持つので、他次元ベクトル空間の部分空間内に集中している。 このような部分空間を、その物体の固有空間と呼ぶ。

重みが大きい基底ベクトルを主成分ベクトルと呼ぶ。

固有空間の求め方

• 主成分分析（PCA）
  • 多変量解析
  • カール・ピアソンが1901年に提案
• KL変換
  • 信号処理
  • Karhunent(1947)、Loeve(1977)

どちらも同値の操作であるが、異なる分野で独立に開発された。

主成分

以下のいずれかの基準で主成分を決める。

• 平均二乗誤差最小基準
• 分散最大基準

平均二乗誤差最小基準

$n$ 個の画像ベクトルが与えられている。 そのうち、ある画像 $i$ のベクトルが ${\mathbf{x}}_i$ とする。 また、ベクトル ${\mathbf{u}}_1$ への正射影ベクトルを ${\tilde{\mathbf{x}}}_i$ とする。 このとき、平均二乗誤差は以下の ${ϵ}^2({\mathbf{u}}_1)$ によって与えられる。

$${ϵ}^2({\mathbf{u}}_1)=\frac{1}{n}\sum _{i=1}^n||{\mathbf{x}}_i-{\tilde{\mathbf{x}}}_i|{|}^2$$

また、第一主成分のベクトルを求めることは、すなわち最適化問題 ${\mathrm{argmin}}_{{\mathbf{u}}_1}{ϵ}^2({\mathbf{u}}_1)$ を解くことである。

さらに、平均二乗誤差最小基準は射影最大基準に同値変形することができる。 これは、二乗誤差 $||{\mathbf{x}}_i-{\mathbf{x}}_i|{|}^2$ と射影長の二乗 ${\delta }^2({\mathbf{u}}_1)=||{\tilde{\mathbf{x}}}_i|{|}^2$ の和は三平方の定理から常に定数（$||{\mathbf{x}}_i|{|}^2$）であり、平均二乗誤差が最小を取るとき、常に射影は最大になるからである。

第一主成分のベクトルを求めることは、すなわち最適化問題 ${\mathrm{argmax}}_{{\mathbf{u}}_1}{\delta }^2({\mathbf{u}}_1)$ を解くことでもある。

平均二乗誤差最小基準では固有値分解により主成分を計算することができる。

1. 主成分を求めたいデータセットから、自己相関行列 $R=\frac{1}{n}{\sum }_{i=1}^n{\mathbf{x}}_i{\mathbf{x}}_i^T$ を求める
2. 自己相関行列は、画像ベクトルを列として並べた行列 $A=\left[\begin{array}{cccc}{\mathbf{x}}_1& {\mathbf{x}}_2& \cdots & {\mathbf{x}}_n\end{array}\right]$ を用いて、$R=\frac{1}{n}A{A}^T$ と書ける
3. 自己相関行列 $R$ の固有値と固有ベクトルを求める
4. $k$ 番目に大きい固有値 ${\lambda }_k$ に対応する固有ベクトル ${\mathbf{u}}_k$ を第$k$主成分ベクトルとする
5. $k$ 番目までのベクトルをとった場合の平均二乗誤差は、$\frac{1}{n}{\sum }_{i=1}^n{\mathbf{X}}_i^T{\mathbf{X}}_i-{\sum }_{i=1}^k{\lambda }_i$ で計算できる
6. 主成分ベクトルをいくつ求めるかは、固有値から求められる累積寄与率（集中度）によって決定する。寄与率 $c$ は以下で与えられる

$$c=\frac{{\sum }_{i=1}^k{\lambda }_i}{{\sum }_{i=1}^N{\lambda }_i}$$

分散最大基準

1. 主成分を求めたいデータセットから、共分散行列 $C$ を求める
2. $C$ の固有値と固有ベクトルを求める
3. $k$ 番目に大きい固有値 ${\lambda }_k$ に対応する固有ベクトル ${\mathbf{u}}_k$ を第 $k$ 主成分ベクトルとする
4. ここで、固有値 ${\lambda }_k$ がその方向の分散に相当する
5. 主成分ベクトルをいくつ求めるかは、固有値から求められる累積寄与率（集中度）により決定する

共分散行列は、平均ベクトル $\mathbf{m}$ を求め、$C=\frac{1}{n}{\sum }_{i=1}^n({\mathbf{x}}_i-\mathbf{m})({\mathbf{x}}_i-\mathbf{m}{)}^T$ で求められる。

Sparse PCA

ALOI: Amsterdam Library of Object Imagesに対する主成分分析の結果を観察すると、第一主成分に正規分布が、第二主成分に正規分布の一次微分が、第三主成分に正規分布の二次微分が現れる。 1つ目は平滑化フィルタに、2つ目はエッジ抽出フィルタに、3つ目は輪郭抽出フィルタ（Laplacian Gaussian）に対応し、脳内にもこのような応答をする細胞が存在する。

基底数を制限すると局所性が現れるため、固有空間を得ることができる。 固有空間への正射影は、次のようなメリットがある。

• 情報圧縮
  • 少数の基底ベクトルの1次結合で表現できる
• 特徴抽出
  • 顔の固有空間への正射影は人間成分の抽出になる
• 画像パターンの可視化
  • 動画像パターンセットは高ベクトル空間において多様体を形成する
• 画像復元
  • もし一部が欠落した画像でも、事前に欠落していない画像からなる特徴ベクトルに射影すれば、部分空間上の画像の中で最も近い画像を得ることができる

線形判別法

2クラス以上を対象にして、各クラスをできるだけ識別しやすい部分空間を求める手法。 クラス間変動のクラス内変動に対する比 $F_s$ を最大にする1次元軸 $\mathbf{u}$ を求めることが目標。

全体平均 $\tilde{m}$ を用いて、以下のような変換を行う。

• クラス内変動 ${\mathbf{S}}_w=n_1{\sigma }_1^2+{\tilde{\sigma }}_2^2$
• クラス間変動 ${\mathbf{S}}_B=n_1(m_1-m{)}^2+n_2(m_2-\tilde{m}{)}^2$

よって、$F_s$ は以下のように求められる。

$$\begin{array}{rl}{F}_s& =\frac{{\mathbf{S}}_B}{{\mathbf{S}}_w}\\ & =\frac{n_1{n}_2}{n}\cdot \frac{(m_1-m_2{)}^2}{n_1{{\sigma }_1}^2+n_2{\sigma }_2^2}\end{array}$$

クラス間変動を行列として考えると、$i$ クラスのデータ数 $n_i$、全データの平均ベクトル $\mathbf{m}$、クラス$i$の平均ベクトル ${\mathbf{m}}_i$ を用いて、次のように定義できる。

$${\mathbf{S}}_B=\sum _{i=1,2}{n}_i({\mathbf{m}}_i-\mathbf{m})({\mathbf{m}}_i-\mathbf{m}{)}^T$$

同様にクラス内変動行列についても、クラス $i$ の $j$ 番目のデータ $x_j^i$、クラス $i$ の平均ベクトル ${\mathbf{m}}_i$、$i$ クラスのデータ数 $n_i$ を用いて、次のように定義できる。

$$\begin{array}{rl}{\mathbf{S}}_w& =S_{w1}+S_{w2}\\ & =\sum _{i=1}^{n_1}(x_i^1-{\mathbf{m}}_1)(x_i^1-{\mathbf{m}}_1{)}^T+\sum _{i=1}^{n_2}(x_i^2-{\mathbf{m}}_2)(x_i^2-{\mathbf{m}}_2{)}^T\end{array}$$

マハラノビス距離

1次元

平均 $\mu$、分散 ${\sigma }^2$ を用いて、マハラノビス距離 $d$ は次のように定義される。

$$d=\sqrt{\frac{(\hat{x}-\mu {)}^2}{{\sigma }^2}}$$

多次元

平均ベクトル $\mathbf{\mu }$、分散共分散行列 $C$ を用いて、$k$ 次元正規分布を $\mathcal{N}(\mathbf{\mu },C)$ とする。 マハラノビス距離 $d$ は次のように定義される。

$$d=\sqrt{(\mathbf{x}-\mathbf{\mu }{)}^T{C}^{-1}(\mathbf{x}-\mathbf{\mu })}$$

ただし、$k(<d)$ 本の $d$ 次元ベクトル ${\mathbf{X}}_i$ の分散共分散行列 $C={\sum }_{i=1}^k(X_i-\mu )(X_i-\mu {)}^T$ は逆行列を持たない。 そこで、行列 $C$ の $k$ 個の固有値 ${\lambda }_i(>0)$ と、対応する固有ベクトル ${\mathbf{u}}_i$ を用いて、近似的に擬似逆行列 $C^{-1}$ を定義する。

$$C^{-1}=\sum _{i=1}^k\frac{{\mathbf{u}}_i{\mathbf{u}}_i^T}{{\lambda }_i}$$

機械学習

種類

• 教師あり学習
  • 予測対象が連続値
    • 回帰
    • 推薦
  • 予測対象が離散値
    • 分類
• 教師なし学習
  • 予測対象が連続値
    • 次元削減
    • 主成分分析
  • 予測対象が離散値
    • クラスタリング

教師付き学習ではデータとラベルを持つ既知事例から、データのみを持つ未知事例のラベルを予測する。

TODO

以下は、勉強中に出てきたがまだ調べていないこと

• 方向統計学（Directional statistics）
  • 方角のような通常の実数とは異なる連続性を持つ仕組みのための統計
  • コンパクトなリーマン多様体の性質を扱う
    • ？
• CMA-ES
  • 秋本先生の解説論文
  • $p_{\sigma }^{(t)}$ の係数が何を意味しているかわかると面白い（うえかん談）
• テンソル積
  • https://manabitimes.jp/math/1845

平均二乗誤差

実際の目標値 $t_i$ と予測した目標値 $wx+b$ の差を誤差という。 誤差 $e$ は、次のように計算できる。

$$e=\left|t_i-(wx+b)\right|$$

ここで、全訓練事例に対する二乗誤差の平均を平均二乗誤差という。 線形モデル $wx+b$ における平均二乗誤差 $E(w)$ は、次のように計算できる。

$$E(w)=\frac{1}{N}\sum _{i=1}^N(t_i-(w{x}_i+b){)}^2$$

平均二乗誤差を最小化するようなモデルが良いモデルであると言える。 したがって、次のような $w,b$ を求めたい。

$$\underset{w,b}{\min }\frac{1}{N}\sum _{i=1}^N(t_i-(w{x}_i+b){)}^2$$

これは、最急降下法を用いることで求められる。

最急降下法

関数 $f$ が微分可能であるとき、${\min }_{x}f(x)$ となる $x$ を求める手法。

アルゴリズム

1. $t=0,x^0$ をランダムに初期化する
2. $x^{t+1}\leftarrow x^t-\eta \frac{\text{d}}{\text{d}x}f(x^t)$
3. $t\leftarrow t+1$
4. $\left|x^{t+1}-x^t\right|<ϵ$ を満たすまで繰り返す

傾きが$0$と見做せるまで移動し続けることで最小値を見つける。 $f$ の形によっては局所解に収束することがあるので、初期値の値を変えながら複数回試すことで結果が改善することがある。 また、微分を解析的に計算するために絶対値ではなく二乗を使う。

最小二乗法を使わない理由

最小二乗法を使うには、$\frac{\text{d}f}{\text{d}x}=0$ が解析的に解ける必要がある。 線形モデルでは当然解けるが、多くの機械学習モデルでは解けない。

確率的勾配降下法

SGD: stochastic gradient descent method。

ナイーブな最急降下法は全事例の訓練誤差総和についての勾配を計算するが、計算量はサンプル数$N$について$\mathrm{O}(N)$となる。 SGDは、ランダムに選んだ1つの事例の訓練誤差について勾配を計算する。

勾配は近似的だが、更新あたりの計算量はサンプル数$N$について$\mathrm{O}(1)$。 訓練誤差が単調減少しないなど、最適化の過程は不安定になる。

ミニバッチSGD

全データから比較的少数のデータをランダムに選んだ集合であるミニバッチを作成する。 ランダムに選んだミニバッチの予測誤差について勾配計算を行う。

更新あたりの計算量はミニバッチサイズに比例するが、SGDほど更新過程が不安定ではなくなる。 バッチごとに独立に勾配を計算できるので並列化できるという嬉しさもある。

これらは1ステップあたりの計算量を減らすが、全体として計算量が減ることや計算時間が短くなることを保証するものではない。

線形回帰

単回帰

• 訓練事例
  • $(x_1,t_1),(x_2,t_2),\dots ,(x_N,t_N)$
  • $x_i$
    • 特徴量
    • 観測可能なデータ
  • $t_i$
    • 目標値
    • 予測対象となるデータ

学習時には、訓練事例から特徴量と目標値の間の線形モデル $t=wx+b$ を求める。 パラメータ $w$ は特徴量 $x$ と目標値 $t$ の関係の強さで、符号が正なら特徴量が大きい値を取るほど目標値も大きくなり、符号が負なら特徴量が小さい値を取るほど目標値は大きくなる。 パラメータ $b$ はバイアスと呼ばれ、特徴量が$0$の時の予測値を表す。

その線形モデルを用いて、目標値が不明の特徴量が与えられたときに、その目標値を予測する。

重回帰

• 特徴（独立変数）: $x_i\in {\mathbb{R}}^D$
• 目標値（従属変数）: $t_i\in {\mathbb{R}}^1$
• 事例: 特徴と目標値の組 $(x_i,t_i),i=1,\dots ,N$
• 目的
  • 多数の目標値付き事例が与えられた時に、事例から目標値を予測する

重回帰では、複数の特徴量とバイアスから目標値を予測するので、目標値は以下のように計算される。

$$t=w_0+w_1{x}_1+\cdots +w_D{x}_D=w_0+\sum _{d=1}^D{w}_d{x}_d$$

また、事例を次のように定義すると、

$$\left(\begin{array}{c}{\mathbf{x}}_1^T\\ {\mathbf{x}}_2^T\\ ⋮\\ {\mathbf{x}}_N^T\end{array}\right)=\left(\begin{array}{ccccc}1& x_{11}& x_{12}& \cdots & x_{1D}\\ 1& x_{21}& x_{22}& \cdots & x_{2D}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& x_{N1}& x_{N2}& \cdots & x_{ND}\end{array}\right)$$

重回帰モデルを次のように表現できる。

$$t=\sum _{i=0}^D{w}_i{x}_i={\mathbf{w}}^T\mathbf{x}$$

データの属性

データはいくつかの属性に分類することができる。 機械学種で扱う際には順序属性やカテゴリカル属性も数値属性に変換する。

数値属性

スカラやベクトルで表現できる属性。 年齢や実行時間。

順序属性

順序関係を持つ属性。 成績評価（A+ > A > B > C > D）など。

順序を保存したスカラ値に変換する。

カテゴリカル属性

順序関係を持たない属性。 血液型など。

1-of-k変換（one-hot encoding）を行う。 たとえば血液型なら、A型は(1, 0, 0, 0)、B型は(0, 1, 0, 0)、O型は(0, 0, 1, 0)、AB型は(0, 0, 0, 1)。 すなわち、属性値がN種類あるとき、$k=N$ となる。

前処理

機械学習で扱うデータを前処理する方法にはいくつか種類がある。

欠損値

• 欠損値を含むサンプルを除去する
• 欠損値はその特徴の平均値や中間値で補完する

外れ値

• 全体を俯瞰し、極端な外れ値を含むサンプルを除去する
  • 測定エラーや入力ミス、例外の可能性があるため

スケーリング

• 各特徴が平均0、標準偏差1になるようにスケーリングする
• 最大値が1、最小値が0になるようにスケーリングする

文書の特徴ベクトル化

Bag-of-words

文書中に含まれる単語について、頻度によらず出現したかどうかのみを特徴とするベクトルをBag-of-wordsという。

TF-IDF

Bag-of-wordsベクトルの出現フラグの代わりに、単語の出現頻度や珍しさを反映した値を持つベクトルをTF-IDFという。 情報検索分野でも頻出。

• N個の文書 $D=\{d_1,d_2,\dots ,d_N\}$
• $n_{ij}$ は、$j$番目の文書における語$i$の出現回数
• TF (term freq.)
  • 語$i$の文章$j$における出現割合
  • ${\text{tf}}_{ij}=\frac{n_{ij}}{{\sum }_{d_k\in D}{n}_{kj}}$
• IDF (inv. doc. freq.)
  • 語$i$の珍しさ
  • ${\text{idf}}_i=\frac{N}{|\{d|i\in d,d\in D\}|}$
• TF-IDF
  • 語$i$の文書$j$における重要さ
  • ${\text{tfidf}}_{ij}={\text{tf}}_{ij}\times {\text{idf}}_i$

画像の特徴ベクトル化

認識対象について、必要な情報を残し、不要な情報を削除する。

輝度値特徴

アピアランスベース画像認識と呼ばれる、画像の見え方をそのまま用いる手法。 (画素 x 画素)次元特徴ベクトルになる。 顔の見え方そのものが必要で、画像の明るさは不要な顔認識などに用いられる。

高次局所自己相関特徴（HLAC）

各画素において、マスクの灰色の箇所と重なる画素値の積を計算し、画面全体に走査してその和を計算する。 画像のサイズに依らず25次元特徴ベクトルとなる。 見え方、色、形状、個数が必要で、物体の位置が不要な物体認識などに用いられる。

凸計画問題

最適化問題において、制約を満たす解を実行可能解、制約を満たす領域を実行可能領域と呼ぶ。 目的関数が凸関数で、実行可能領域が凸集合であるような問題を凸計画問題と呼ぶ。

凸集合・凸関数

集合 $A$ が凸集合であるとは、$foral{l}_{x,y}\in A\text{and}t\in [0,1],tx+(1-t)y\in A$ を満たすことと同値である。 また、関数 $f$ が下に凸であるとは、${\forall }_t\in [0,1],f(tx+(1-t)y)\le tf(x)+(1-t)f(y)$ を満たすことと同値である。

凸関数の具体例

• 線形関数
• アフィン関数
• 正定値行列 $Q$ について、${\mathbf{x}}^T\mathbf{Q}\mathbf{x}+{\mathbf{c}}^T\mathbf{x}$
• ノルム
• $x_i\ge 0$ について、$(x_1{x}_2\dots x_n{)}^{\frac{1}{n}}$
• $\log (e^{x_1}+e^{x_2}+\cdots +e^{x_n})$

微分可能な凸関数の最適化

解析的に解く

勾配ベクトルが0ベクトルとなる$x$を解析的に求める。

近似的に解く

最急降下法やそれに類する手法により近似解を求める。

凸計画問題の種類

• $f$が微分可能

  • 制約なし
    • $f$の微分を$0$にする点が解析的に求まる
      • その点が最適解
    • 求まらない
      • 最急降下法などで近似的に解く
  • 等式制約
    • ラグランジュの未定乗数法
  • 不等式制約
    • ラグランジュの未定乗数法
    • SVM導出などで出てくる

• $f$が微分不可能

  • 制約なし
  • 等式制約
  • 不等式制約

多項式回帰

M次多項式回帰モデルによる回帰。

1次元特徴

• 特徴量関数 $\psi :\mathbb{R}\to {\mathbb{R}}^{M+1}$
• 多項式特徴量 $\psi (x)=(x^0,x^1,x^2,\dots ,x^M)$
• 線形回帰モデル $t={\mathbf{w}}^T\psi (x)$

$$t=w_0+w_{1}x+w_2{x}^2+\cdots +w_M{x}^M$$

D次元特徴

$$t=w_0+\sum _{m=1}^M\sum _{d=1}^D{w}_{md}{x}_d^m$$

あるデータが与えられたときに、次元を上げて複雑にすればするほどにその訓練データを上手く説明することはできるが、overfittingを起こすので、適切な複雑さを選ぶ必要がある。

多項式次元を上げるほど訓練誤差は小さくなり、最終的に0にできる。 しかし、テスト誤差は最初は大きく、次元を上げるごとに徐々に小さくなるが、必要以上に多項式次元を上げると増加する。

回帰における誤差

手持ちのN個のサンプル $(x_1,t_1),(x_2,t_2),\dots ,(x_N,t_N)$ について、$x_i$ を与えられたら $t_i$ を返すハッシュ関数は常に二乗誤差が0だが、サンプル以外には対応できないので意味がない。 このようなサンプルに対して過学習したモデルは使えないので、訓練用とテスト用のサンプルに分けて訓練を行う。

訓練誤差

• モデル $t=f(\mathbf{x})$ を明らかにしたい
• 訓練事例 $X_{tr}=\{({\mathbf{x}}_i,t_i)\}$ を使って学習させる
• 学習した回帰モデル ${\hat{t}}_i=\hat{f}({\mathbf{x}}_i)$
• 訓練事例で得た回帰モデルの、訓練事例における誤答率を訓練誤差と呼ぶ

$$\text{TrainingErr}=\frac{1}{\left|X_{tr}\right|}\sum _{({\mathbf{x}}_i,t_i)\in X_{tr}}(t_i-\hat{f}({\mathbf{x}}_i){)}^2$$

汎化誤差

• データ生成分布 $p(\mathbf{x},t)$
  • 知ることができない
• 真のモデル $t=f(\mathbf{x})$
  • こちらも知ることができない
• 学習した回帰モデル ${\hat{t}}_i=\hat{f}({\mathbf{x}}_i)$

$$\text{GeneralizationErr}=\int \int (t-\hat{f}(\mathbf{x}){)}^{2}p(\mathbf{x},t)\text{d}\mathbf{x}\text{d}t$$

汎化誤差を使えば回帰モデルの性能を調べることができるが、実際にはこれを計算することはできない。 ただし、汎化モデルの上界を証明するような研究は存在し、学習機の性能保証として使える。

テスト誤差

• モデル $t=f(\mathbf{x})$ を明らかにしたい
• テスト事例 $X_{ts}=\{({\mathbf{x}}_i,t_i)\}$
• 学習した回帰モデル ${\hat{t}}_i=\hat{f}({\mathbf{x}}_i)$
• 訓練事例で学習した回帰モデルの、テスト事例における誤答率をテスト誤差と呼ぶ

$$\text{TestErr}=\frac{1}{\left|X_{ts}\right|}\sum _{({\mathbf{x}}_i,t_i)\in X_{ts}}(t_i-\hat{f}({\mathbf{x}}_i){)}^2$$

汎化誤差の有限サンプル近似がテスト誤差となる。 これは、標本平均が母平均の有限サンプルにおける近似だからで、サンプル数無限大における標本平均は母平均に一致する。

K-fold交差検証

偏りの大きい事例が訓練事例に集中すると、学習モデルの偏りも大きくなってしまうため、 様々な分割パターンで学習を行ってできるだけ偏りを少なくする手法。

1. 事例を$k$個に分割する
2. $i$番目の分割をテスト事例として、残る$k-1$個を訓練事例としてテスト誤差を評価する
3. 全てのfoldのテスト誤差を平均し、これを汎化誤差の推定値として出力する

正則化

動機

複雑度の高いモデルは、訓練誤差は抑えられるがテスト誤差は大きくなる。 そこで、モデルに対する知識で複雑さを制御することでテスト誤差を制御する正則化を導入する。

罰則付き最適化

両者が矛盾するような $f(\mathbf{x}),g(\mathbf{x})$ の両方を最小化するような問題を考える。

$$\text{minimize}h(\mathbf{x})=f(\mathbf{x})+\lambda g(\mathbf{x})$$

回帰問題に対しては、訓練誤差の最小化と複雑さの最小化をトレードオフパラメータ$\lambda$によって制御して、汎化誤差が小さくなることを期待する。

リッジ回帰

重回帰分析の誤差関数に含まれる二乗誤差項 $E(\mathbf{w})={\sum }_{i=1}^N(t_i-{\mathbf{w}}^T{\mathbf{x}}_i{)}^2$ に、L2正則化項を加えたものを誤差関数とする回帰をリッジ回帰（Ridge regression）という。

$$E(\mathbf{w})=\sum _{i=1}^N(t_i-{\mathbf{w}}^T{\mathbf{x}}_i{)}^2+\lambda {\mathbf{w}}^T\mathbf{w}$$

L2正則化項では$\mathbf{w}$の各要素が大きい値を取ると大きくなるため、複雑さを抑制する。 また、二乗誤差項も凸関数で、L2正則化項も凸関数であるから、誤差関数全体としても凸関数であり、唯一の局所最適解を持つ。 さらに、微分可能であるから解析解も求められる。

特徴選択

目標変数の予測に必要ない特徴を排除して有用な特徴のみを使ってモデリングする手法。 予測時における計算効率の向上や、目標変数の予測精度の向上、学習結果の解釈性の向上のために行う。

フィルター法

$D$次元の特徴変数 $x_1,x_2,\dots ,x_D$ と目標変数 $t$ があるとき、各特徴変数と目標変数の相関を計算する。 たとえば、ピアソン相関係数 $r_s$ を以下のように求める。

$$r_s=\frac{{\sum }_{i=1}^N({\bar{x}}_s-x_{si})(\bar{t}-t_i)}{\sqrt{{\sum }_{i=1}^N({\bar{x}}_s-x_{si}{)}^2{\sum }_{i=1}^N(\bar{t}-t_i{)}^2}}$$

次に、ある閾値 $\theta$ を決めて、それより大きな変数のみを特徴として利用する。 ただし、2つ以上の変数がセットで目標値に影響を与える場合はフィルター法が適用できない。

ラッパー法

$D$次元の特徴変数と目標変数があるとする。 ここで、特徴のインデックスを $\{1,2,\dots ,D\}$ として、$M$ 個の特徴を選択する。 サイズ$M$のべき集合を列挙して、各要素についてその集合で指定された特徴でモデルを学習させ、そのテスト誤差を評価する。 最後に、もっとも良いテスト誤差を与える特徴部分集合を採用する。

最良の特徴選択が実現でき、複数個の変数がセットで目標値に影響を与える場合にも対応できるが、部分集合の候補数が特徴量に対して指数的に増加する。 そこで、前向き貪欲探索を行うが、最良の特徴選択ができる保証はなく、並び方により最終的な結果が異なる。

スパース性を導入する正則化の利用

ラッソ回帰

重回帰分析の誤差関数に含まれる二乗誤差項 $E(\mathbf{w})={\sum }_{i=1}^N(t_i-{\mathbf{w}}^T{\mathbf{x}}_i{)}^2$ に、L1正則化項を加えたものを誤差関数とする回帰をラッソ回帰（Lasso regression）という。

$$E(\mathbf{w})=\sum _{i=1}^N(t_i-{\mathbf{w}}^T\mathbf{x}{)}^2+\lambda \sum _{i=1}^D\left|w_i\right|$$

原点からの遠さに対して線形で罰する。 誤差項もL1正則化項も凸関数なので最適解は比較的求めやすいが、原点付近で微分不可能なので解析解を求めることはできない。

L1正則化項は目的関数の等高線と正則化項の等高線の接する部分が軸上になりやすく、係数が0になるので結果的に特徴選択もできることがある。

勾配降下法の収束

μ強凸

ある関数 $f:{\mathbb{R}}^D\to \mathbb{R}$ が以下を満たすとき、$f$ はμ強凸であるという。

$$f(\mathbf{y})>f(\mathbf{x})+(\mathbf{y}-\mathbf{x}{)}^T\nabla f(\mathbf{x})+\frac{\mu }{2}||\mathbf{x}-\mathbf{y}|{|}_2^2$$

ここで、$\mu$は凸性の強さを表している。

L平滑

ある関数 $f:{\mathbb{R}}^D\to \mathbb{R}$ が以下を満たすとき、$f$ はL平滑であるという。

$$||\nabla f(\mathbf{x})-\nabla f(\mathbf{y})|{|}_2<L||\mathbf{x}-\mathbf{y}|{|}_2$$

勾配の変化が入力の変化の変化の定数倍で抑えられる性質を持つ。 近接した点の勾配は互いに近接している。

勾配降下法の収束

${\mathbf{w}}^{\ast }={\mathrm{argmin}}_{\mathbf{w}}E(\mathbf{w})$ とする。 また関数 $E$ は微分可能な凸関数とする。 関数 $E$ がL平滑で、ステップサイズが $\eta <\frac{1}{L}$ であるとき、以下が成立する。

$$E({\mathbf{w}}^{(t)})-E({\mathbf{w}}^{\ast })<\frac{2L||{\mathbf{w}}^{(0)}-{\mathbf{w}}^{\ast }|{|}_2^2}{t+4}$$

収束速度がステップ数$t$について$\mathrm{O}(\frac{1}{t})$となる。 また、誤差を$ϵ$以下にするためには、$\mathrm{O}(\frac{1}{ϵ})$回の更新が必要となる。

μ強凸な誤差関数に対する勾配降下法の収束

${\mathbf{w}}^{\ast }={\mathrm{argmin}}_{\mathbf{w}}E(\mathbf{w})$ とする。 また関数 $E$ は微分可能な凸関数とする。 関数 $E$ がμ強凸（$\mu >0$）かつL平滑（$L>0$）で、$\eta =\frac{1}{L}$ であるとき、以下が成立する。

$$E({\mathbf{w}}^{(t)})-E({\mathbf{w}}^{\ast })<(1-\frac{\mu }{L}{)}^t[E((w{)}^{(0)}-E({\mathbf{w}}^{\ast })]$$

収束速度はステップ数 $t$、収束係数 $c=1-\frac{\mu }{L}$ に対して、$\mathrm{O}(c^t)$。 誤差を $ϵ$ 以下にするには、$\mathrm{O}(\log (\frac{1}{ϵ}))$ 回の更新で良い。

つまり、μ強凸である方が収束が高速。 回帰やridge回帰は強凸かつL平滑で、ロジスティック回帰はL平滑だが強凸ではない。 また、LassoやSVMはL平滑ではない。

学習率

学習率は小さすぎると収束が遅くなり、大きすぎると収束は早いが最適解周辺で振動する。 また、非常に大きいと発散してしまう。

更新回数が増加するにつれて学習率を小さくしたり、更新量が減少するにつれて学習率を小さくさせるようなスケジューリングができる。 しかし、適切な学習率を理論的に決定することは困難で、問題ごとにチューニングしなければならない。

劣勾配

微分不可能な点では勾配を求めることができないが、凸関数に対しては微分不可能な点における傾きを1つの値ではなく集合として表現することで一般化することができる。 これを劣微分と呼ぶ。 また、劣微分によって得られる要素を劣勾配という。

絶対値関数 $f(x)=\left|x\right|$

原点が微分不可能な点であり、原点での傾きを $[-1,+1]$ として表す。

劣勾配降下法

最急降下法における勾配を劣勾配に置き換えて行う手法。 微分不可能な点を持つ関数、たとえばラッソ回帰（L1正則化項が微分不可能な点を持つ）に対しても最適解を求められる。

超平面

D次元実数値空間 ${\mathbb{R}}^D$ を2つの半空間に分割する平面を超平面という。 超平面は ${\mathbb{R}}^{D-1}$ 次元の平らな集合である。 具体的には、3次元空間の超平面は2次元平面となる。

特徴量 $\mathbf{x}$ の1次元目を1として、${\mathbf{w}}^T\mathbf{x}=0$ と書ける。 この時、パラメータ空間は ${\mathbb{R}}^D$ であり、半空間は ${\mathbf{w}}^T\mathbf{x}>0$ と ${\mathbf{w}}^T\mathbf{x}<0$ となる。

分類

分類問題ではラベルが離散値であり、たとえば気温や湿度から天気（晴れ、曇り、雨）を予測する。

事例 $(x_i,t_i)$（$x_i\in {\mathbb{R}}^D,t_i\in \{C_1,C_2\}$）から未知事例のラベルを当てる。

空間をクラスごとに分割した領域全体を決定領域（decision region）という。 また、異なるクラスの領域を分割している線や面を決定境界（decision boundary）という。 決定境界が線形であるとき、線形分類可能、そうでないとき線形分類不可能であるという。

• 決定的識別モデル
  • $t_i\in \{-1,1\}$
  • 決定境界 $f(\mathbf{x})$ を学習する
  • $f(\mathbf{x})>0$ であるとき、$\mathbf{x}$ のラベルは $C_1$
• 確率的識別モデル
  • $t_i\in \{0,1\}$
  • 条件付き確率 $p(C_1\mid \mathbf{x})$ を学習する
  • $p(C_1\mid \mathbf{x})>0.5$ であるとき、$\mathbf{x}$ のラベルは $C_1$

ここで、最も単純な決定的識別モデル $t_i$ は超平面 ${\mathbf{w}}^T\mathbf{x}=0$ に用いて以下のように定義できる。

$$t_i=\text{sgn}({\mathbf{w}}^T{\mathbf{x}}_i)=\{\begin{array}{rl}& 1\text{if}{\mathbf{w}}^T{\mathbf{x}}_i>0\\ & -1\text{o.w.}({\mathbf{w}}^T{\mathbf{x}}_i\le 0)\end{array}$$

回帰では ${\mathbf{w}}^T\mathbf{x}$ そのものが予測を与えたが、分類では識別モデルを別に定義することに注意。

最適な線形分類モデル

正しい分類と予測した分類の不一致数である分類誤差を最小化するような $\mathbf{w}$ が最適なモデルである。 したがって、以下のような誤差関数が定義できる。

$$E(\mathbf{w})=\sum _{i=1}^{N}I(t_i,\text{sgn}({\mathbf{w}}^T{\mathbf{x}}_i))$$

ただし、$I(a,b)$ は$a$と$b$が一致するなら0、不一致なら1を返す関数である。

正しい分類を与える超平面を得るためには、以下の条件を満たす $\mathbf{w}$ を求めれば良い。

$$t_i({\mathbf{w}}^T{\mathbf{x}}_i)>0,{\forall }_i=1,\dots ,N$$

サポートベクターマシン（ハードマージン）

先ほどの条件を満たす決定境界は複数存在し得るが、識別平面とデータの距離 = マージン が最大である方がより良い適切境界である。 マージンは $\frac{|{\mathbf{w}}^T\mathbf{x}|}{||\mathbf{w}||}$ で計算できるから、次の最適化問題を解くことになる。

$$\underset{\mathbf{w}}{\max }\underset{i\in \{1,2,\dots ,N\}}{\min }\frac{\left|{\mathbf{w}}^T{\mathbf{x}}_i\right|}{||\mathbf{w}|{|}_2}\text{subject to}{t}_i({\mathbf{w}}^T{\mathbf{x}}_i)>0$$

ここで、超平面は定数倍に対して不変なので、${\min }_i{t}_i({\mathbf{w}}^T{\mathbf{x}}_i)=1$ となるようにスケーリングする。 すると、${\min }_{i\in \{1,2,\dots ,N\}}\frac{|{\mathbf{w}}^T{\mathbf{x}}_i|}{||\mathbf{w}|{|}_2}=\frac{1}{||\mathbf{w}|{|}_2}$ に変形でき、逆数なので双対問題を考えて以下のような最適化問題を考えられる。

$$\underset{\mathbf{w}}{\min }||\mathbf{w}|{|}_2^2\text{subject to}{t}_i({\mathbf{w}}^T{x}_i)\ge 1,i=1,\dots ,N$$

これをハードマージンのサポートベクターマシンという。

サポートベクターマシン（ソフトマージン）

ハードマージンのサポートベクターマシンは以下の2つの理由で扱いづらいことがある。

1. 線形等式・不等式制約のある二次形式の最適化である凸二次計画問題（QP: quadratic programming）に持ち込めば解けるが、計算としては重い
2. どのような超平面でも正しい分類と予測した分類の不一致数を0にできないような線形分離不可能な場合がある

そこで、予測に失敗した際に識別平面からの距離に応じたペナルティを与えることを考える。

$$\underset{\mathbf{w}}{\min }||\mathbf{w}|{|}_2^2+C\sum _{i=1}^N\max \{0,1-t({\mathbf{w}}^T{\mathbf{x}}_i)\}$$

これをソフトマージンのサポートベクターマシンという。

損失関数への一般化

ソフトマージンのSVMは、L2正則化項と各データに対する個別のペナルティ = 損失関数の足し合わせであると見なすことができる。 回帰で扱う損失関数は二乗損失と呼ぶが、SVMにおける損失をヒンジ損失という。

$$l_{\text{hinge}}(t_i,{\mathbf{w}}^T{\mathbf{x}}_i)=\max \{0,1-t_i({\mathbf{w}}^T{\mathbf{x}}_i)\}$$

0-1損失関数は正確に外れたケースに対してだけ一定のペナルティを与えられるが、組合せ最適化により最適化されるため簡単には解けず、マージン最大化も考慮されない。 また、二乗損失は微分可能で解析解を得ることができるが、当たっているのに巨大な損失を与えてしまうので良い分類モデルであるかは疑問。 ヒンジ損失関数は微分可能ではないが凸関数なので劣勾配を考えることができ、確率的劣勾配降下法により大局的最適化を行うことができる。

混同行列と性能評価

2値分類問題の分類結果をまとめた行列。

• 予測が真
  • 実際も真
    • TP: True positive
  • 実際は偽
    • FP: False positive
• 予測が偽
  • 実際は真
    • FN: False negative
  • 実際も偽
    • TN: True negative

正解率: accuracy

予測がどの程度当たったかを示す指標を正解率という。

$$\text{accuracy}=\frac{\text{TP}+\text{TN}}{\text{TP}+\text{FP}+\text{FN}+\text{TN}}$$

精度: precision

真と予測したデータのうち、実際に真である割合を精度という。 取りこぼしても良い = False negativeは許容するが、間違いが許されない場合に使う。

$$\text{precision}=\frac{\text{TP}}{\text{TP}+\text{FP}}$$

偽陽性率: false positive rate

実際は偽であるにも関わらず真であるように予測してしまった事例の割合。

$$\text{false positive rate}=\frac{\text{FP}}{\text{TN}+\text{FP}}$$

再現率: recall

実際に真であるもののうち、真と予測した割合。 予測が間違っても良いが、取りこぼしが許されない場合に使う。

$$\text{recall}=\frac{\text{TP}}{\text{TP}+\text{FN}}$$