言語処理のための機械学習入門 - 1. 必要な数学的知識 1.1-1.2.1

言語処理のための機械学習入門をざっとまとめたりして過ごしていました。

 

この章で紹介されること:

  1. 最適化問題
  2. 確率論
  3. 情報理論

1.1 準備

[文の構造を明らかにするタスク]

単語分割(word segmentation): 与えられた文を単語に分割

品詞タグ付け(part-of-speech tagging): 文中の単語の品詞を推定

構文解析(syntactic parsing): 文の構文的な構造を推定

[その他]

文書分類(text classification): 与えられた文書に対して、適切なクラスを決定

その他、照応解析、質問応答、機械翻訳、等

 

事例(instance)・・・それぞれのタスクでの対象の処理単位

コーパス(corpus)・・・言語の様々な形の用例の集まり

 

1.2 最適化問題

最適化問題(optimization problem): 

    ある制約のもとで関数を最適化する変数値とその関数値を求める問題

目的関数(objective function): 最適化したい関数

最適解(optimal solution): 最適値を与える変数値

 

[制約について]

不等式制約(inequality constraint):    e.g. {g(x) \geq 0}

等式制約(equality constraint):     e.g. {h(x)=0}

実行可能解(feasible solution): 制約を満たす解のこと

実行可能領域(feasible region): 実行可能解の集合

閉形式(closed-form): 加減乗除や初等関数の合成関数による解の表し方

閉形式の解が得られる問題を解析的に解ける(analytically solvable)問題という。

 

[凸計画問題(convex programming problem)]

凸計画問題では、目的関数の値が改善する方向に進んでいけば解にたどりつく

=> 解きたい問題を凸計画問題で表すことができれば、問題解決へ大躍進とのこと

 

1.2.1 凸集合と凸関数

[凸集合(convex set)とは?]

任意の{x^{(1)} \in A}{x^{(2)} \in A}があったとき、任意の{t \in [0,1]}に対して{tx^{(1)}+(1-t)x^{(2)} \in A}が成り立つこと。

直感的にいえば「へこみのない集合」

>空間内の立方体とか凸集合なイメージだね、と誰かと話していた気がする。

 

[凸性について]

凹関数(concave function): 下に凸な関数    e.g. {f(x)=-x^{2}}

凸関数(convex function): 上に凸な関数    e.g. {f(x)=x^{2}}

=>「上に凸である」とは?

関数上の任意の2点を結ぶ線分が常にグラフの下もしくは同じ高さにあること。

=> 任意の{x^{(1)},x^{(2)} \in R^{d}}、任意の{t \in [0,1]}に対し、{f(tx^{(1)}+(1-t)x^{(2)}) \geq tf(x^{(1)})+(1-t)f(x^{(2)})}が成立すること。

※凸集合は集合としてへこみがないものだったけど、凸な関数はその値についてへこみがない関数、とのこと。だけども上下逆なだけなので、両方とも凸関数と表現されることもあるらしい。

※ここでいう凸関数および凹関数はスカラー値関数に対してのみ定義されうる。

 

凸関数であるための1次の条件(first-order convexity condition)は、任意の{x^{(1)},x^{(2)} \in R}について、{f(x^{(2)})-f(x^{(1)}) \leq \frac{\partial f(x^{(1)})}{\partial x}(x^{(2)}-x^{(1)})}が成り立つこと。

凸関数である為の2次の条件(second-order convexity condition)は、1変数関数の場合は、2階微分{f''(x)}が常に負または0であることだが、多変数関数の場合も、2階微分が負ならば上に凸になる。

色々な変数の組についての微分を、ヘッセ行列(Hessian){H_{x}}でまとめて表す。多変数関数の場合、それぞれの2階微分が負である必要は無く、ヘッセ行列が負であれば上に凸である。

=>行列の「正負」とは?

☆0または正: 行列が半正定値(positive semi-definite)

行列{nxn}行列{M}が半正定値であるとは、任意の{n}次元ベクトル{x}について{x^{T}Mx \geq 0}が成り立つこと。 

☆0または負: 行列が半負定値(negative semi-definite)

行列{nxn}行列{M}が半負定値であるとは、任意の{n}次元ベクトル{x}について{x^{T}Mx \leq 0}が成り立つこと。

 

関数が

下に凸であるための必要十分条件: ヘッセ行列が半正定値であること

上に凸であるための必要十分条件: ヘッセ行列が半負定値であること

 

P.11の下の方の説明がよくわからず、2次元のヘッセ行列とかシンプルなのを考えてみた。任意のn次元ベクトル{(n_{1},....n_{n})}、という設定から考えると結局{n_{i}^{2}×f''_{i}(x_{i})}の和になる。(※{n_{i}}の2乗とのかけ算ってところは、次元数nが増えても行列式の計算考えると一緒。)その和が常に正なのか負なのかを考えたときに、{n_{i}^{2}}はいつも正の値を取ること等を考えると、{f''_{i}(x_{i})}のどれかが正だったり負だったりバラバラだと、多変数関数が上に凸か下に凸かは決まらないんだろうな。と勝手に考えたりして過ごしてました。

 

演習付いてて素敵な本です。ぜひ。

 

言語処理のための機械学習入門 (自然言語処理シリーズ)

言語処理のための機械学習入門 (自然言語処理シリーズ)

 

 

今日はいい天気でしたね。