教師なし学習(クラスタリング問題）の数理的な問題設定

教師なし学習 機械学習 最適化問題 勉強 クラスタリング ハードクラスタリング ソフトクラスタリング

教師なし学習の数学的な問題設定

教師なし学習の問題としては、２つの問題設定があります。

(\bf{x} _ i, z _ i) (ただしi = 1,...,n)という標本の集合が存在するとします。この集合の各要素について、\bf{x} _ iは観測可能だが、それに対応するz _ iは観測できません。このような状況下で、z _ iを推定するというのが教師なし学習の１つ目の問題です。また、母集団に存在する未知の\bf{x}についても、それに対応するzを予測するというのが２つ目の問題です。

1. クラスタリング問題

1.1 ハードクラスタリング

z _ i \in \{ 1,...,K \} のときクラスタリングまたはハードクラスタリングといいます。ハードクラスタリングは、教師変数のない他クラス分類問題と言いかえることもできます。また、ハードクラスタリングは、\bf{z} _ i = (z _ {i1}, ..., z _ {iK}) \in \{ \{ 0, 1 \} ^ K, |\bf{z} _ i| = 1 \} と言いかえることもできます。(one-hot encoding, 1 of K 表記)

K-平均法

  • 予測
    各k \in [ K ] でクラスタ中心を\mu _ k \in \mathbb{R} ^ d定めて、各\bf{x} \in \mathbb{R} ^ dについて、
\DeclareMathOperator*{\argmin}{arg\,min} %argmin \begin{aligned} z _ k = \left\{ \begin{array}{11} 1 & k = \argmin _ {k'} || \bf{x} - \mu _ {k'} ||\\ 0 & otherwise \end{array} \right. \end{aligned}

と定めます。要は一番近いクラスタ中心に属するという意味です。

  • 目的関数
    \mu = \mu _ k, Z = z _ {ik}とし、
\begin{aligned} J(\mu) = \sum _ {i} \min _ {k} || \vec{x} - \mu _ {k'} || ^ 2 \\ = \min _ {Z} \mathfrak{L}(Z, \mu) \\ ただし、\mathfrak{L}(Z, \mu) = \sum _ {i} \sum _ {k} z_ {ik} || \vec{x _ i} - \mu _ k || ^ 2 です。\\ Zにかかわらず J(\mu) \leq \mathfrak{L}(Z, \mu) となります。 \end{aligned}
EMアルゴリズム

STEP1 \muを適当に定めます。

STEP2 Eステップ
Eステップでは、\mathfrak{L}(Z, \mu)のZについての最小化をします。

\begin{aligned} Z = \argmin _ {Z'} \mathfrak{L}(Z', \mu) \\ すなわち次のようにパラメータを更新をします。\\ z _ {ik} = \left\{ \begin{array}{11} 1 & k = argmin _ {k'} || \bf{x} - \mu _ {k'} ||\\ 0 & otherwise \end{array} \right. \end{aligned}


STEP3 Mステップ
Mステップでは、\mathfrak{L}(Z, \mu)の\muについての最小化をします。

\begin{aligned} \mu = \argmin _ {\mu'} \mathfrak{L}(Z, \mu') \\ すなわち次のようにパラメータを更新をします。\\ \mu _ {k} = \frac{\Sigma _ i z _ {ik} \bf{x _ i}}{\Sigma _ i z _ {ik}} \end{aligned}

STEP4 EステップとMステップを繰り返す
値が更新されなくなるまで、EステップとMステップを繰り返します。

1.2 ソフトクラスタリング

\bf{z} _ i = (z _ {i1}, ..., z _ {iK}) \in \{ \bf{z} \in [ 0, 1 ] ^ K, | \bf{z} _ i| _ 1 = 1 \} のときソフトクラスタリングといいます。z _ {ik}はデータiがクラスkに属する割合と解釈されます。

ソフトK-平均法

  • 予測
    各k \in [ K ] でクラスタ中心を\mu _ k \in \mathbb{R} ^ d定めて、各\bf{x} \in \mathbb{R} ^ dについて、
\begin{aligned} z _ k = \frac{exp(-\beta ||\bf{x} - \mu _ k || ^ 2)}{\Sigma _ k' exp(-\beta ||\bf{x} - \mu _ k' || ^ 2)} \end{aligned}

と定めます。統計力学に出てくるカノニカル分布みたいな形をしていますね。

ちゃんとプリント読まないときついかも

  • 目的関数 K-平均法のminをsoftminで置き換えます。

\mu = \mu _ k, Z = z _ {ik}とし、

\begin{aligned} J(\mu) = \beta ^ {-1} \sum _ {i} \min _ {k} || \vec{x} - \mu _ {k'} || ^ 2 \\ = \min _ {Z} \mathfrak{L}(Z, \mu) \\ ただし、\mathfrak{L}(Z, \mu) = \sum _ {i} \sum _ {k} z_ {ik} || \vec{x _ i} - \mu _ k || ^ 2 です。\\ Zにかかわらず J(\mu) \leq \mathfrak{L}(Z, \mu) となります。 \end{aligned}
EMアルゴリズム

STEP1 \muを適当に定めます。

STEP2 Eステップ
Eステップでは、\mathfrak{L}(Z, \mu)のZについての最小化をします。

\begin{aligned} Z = \argmin _ {Z'} \mathfrak{L}(Z', \mu) \\ すなわち次のようにパラメータを更新をします。\\ z _ {ik} = \left\{ \begin{array}{11} 1 & k = argmin _ {k'} || \bf{x} - \mu _ {k'} ||\\ 0 & otherwise \end{array} \right. \end{aligned}


STEP3 Mステップ
Mステップでは、\mathfrak{L}(Z, \mu)の\muについての最小化をします。

\begin{aligned} \mu = \argmin _ {\mu'} \mathfrak{L}(Z, \mu') \\ すなわち次のようにパラメータを更新をします。\\ \mu _ {k} = \frac{\Sigma _ i z _ {ik} \vec{x _ i}}{\Sigma _ i z _ {ik}} \end{aligned}

STEP4 EステップとMステップを繰り返す
値が更新されなくなるまで、EステップとMステップを繰り返します。