MIT OCW, Machine Learning 13日目

Rohit Singh, Tommi Jaakkola, and Ali Mohammad. 6.867 Machine Learning. Fall 2006. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

停電でデータが消えるという悲しみ

• • • Mixture models and clustering
    • Mixtures and K-means
    • K-means
    • Distance and clustering

Mixture models and clustering

与えられたデータは暗黙的に複数の種類に分けられると仮定し，それを踏まえてより精度の高い推測をするというのがmixture modelの動機のひとつだった. 一方で，その暗黙の構造自体を明らかにすることも有用である. このような問題をclusteringという. つまり，データセットをいくつかのclusterに分類するのである.
mixture modelをgenerative modelとして扱うには，我々が分類しようとしているクラスターがどんなものなのか知らなければならない. 最も単純な例がspherical Gaussian clusterで，すなわち
$$P(\mathbf{x};\theta, m) = \sum_{j=1}^m P(j) N(\mathbf{x};\mu_j,\sigma^2_j I)$$
というmixture modelを推測する.
他にも様々なクラスタリングアルゴリズムがあり,あるものはネストしたクラスターを小さなクラスターをマージしていくことで生成し(hierarchical agglomerative clustering)，またあるものは$D$に最適なクラスターの数を推測してからクラスタリングを行う(k-means). などと期待問題によって適したアルゴリズムは異なる.

データセット$D$に対して$m$をどのように設定すればいいかとか,$D$が十分大きければEM-algorithmでよいクラスタリングが出来るのかとか,頑強なモデルであるのかとか，様々な疑問があり，その答えの一部を以下で与える.

Mixtures and K-means

Gaussian mixture modelを,全ての分散行列を同一のspherical(単位行列の定数倍)にし,さらに全てのcomponentの頻度を同一にすることで単純化する.すなわち
$$P(\mathbf{x};\theta)=\frac{1}{m} \sum_{j=1}^m N(\mathbf{x};\mu_m,\sigma^2 I)$$
を考える. これをEM-algorithmで最適化するとどうなるのかをみる.
まず,クラスター$i, j$の境界がどうなっているかをみる. つまり$P(i |\mathbf{x},\theta)=P(j|\mathbf{x},\theta)$をみたす$\mathbf{x}$をみる. 仮定より,この点で
$N(\mathbf{x}, \mu_i, \sigma^2I)=N(\mathbf{x};\mu_j,\sigma^2I)$が成立する.どちらのGaussianも同じsphericalな共分散行列を持つので, これが成立する$\mathbf{x}$では
$$\|\mathbf{x}-\mu_i\| = \|\mathbf{x}-\mu_j\| \text{ or } 2\mathbf{x}^T (\mu_j-\mu_i)=\|\mu_i\|^2 - \|\mu_j\|^2$$
が成立する.
すなわち境界は線形であり,fig.1のように，任意のクラスターの組に対してこのような境界を引ける. 組ごとの比較はVoronoi partitionを導く. Voronoi partitionのあるregionでは，例えば,全ての点が$\mu_1$に最も近い.このregionは同時に$P(1|\mathbf{x}, \theta)> P(j|\mathbf{x}, \theta)$が任意の$j \neq 1$で成立する.

K-means

上のような単純なモデルではEM-algorithmも単純化できて,それを特にK-meansという.
K-meansでは，E-stepで,$j_t = \arg\min_j \|\mathbf{x}_t-\mu_j\|$とし,M-stepで$\mu_j = average\{\mathbf{x}_t | j_t=j \}$とmeanを設定し直す．

K-meansは非常によく利用されるhard assignment(各点がどれかただ一つのクラスターに分類される)版EM-algorithmである. K-meansはEM-algoと同様初期値が結果に大きく影響するので,初期値を変更して何度も行うのが望ましい. また,ある一点を$\mu_1$に割り当て，$\mu_1$から最も遠い点を$\mu_2$,$\mu_1,\mu_2$から最も遠い点を$\mu_3$,…として初期の$\mu$を決める方法をgreedy packingという.

Distance and clustering

これまでの議論でEuclidean distanceを使ってきたことを正当化する. ところで，多くの場合，特徴データを特別な関数で$\mathbb{R}^n$空間に写像して，それからclusteringを考えたりする．
例えば文書をクラスタリングすることを考える. document $\mathbf{x}$を単語の入った袋と考えて,これを以下の写像によって扱いやすいベクトルにする.
$$\begin{aligned} n_w(\mathbf{x}) &= \text{ number of times world } w \text{ appears in } \mathbf{x} \\ f(w|\mathbf{x}) &= \frac{n_w(\mathbf{x})}{\sum_{w'} n_{w'}(\mathbf{x})} = \text{ term frequencey} \\ \phi_{w}(\mathbf{x}) &=f(w|\mathbf{x}) \cdot \underline{\log \left[ \frac{\text{ number of docs}}{\text{ numer of docw with word }w}\right]}_{IDF} \end{aligned}$$
$\phi(\mathbf{x})=(\phi_{w_1},...,\phi_{w_m})\mathbf{(x)}$をTFIDF(term frequency - inverse document frequency)写像という． IDFは,多くの文書に現れるためクラスタリングに役立たなそうなwordほど小さく(1に近く)なる. こうして文書を実数空間に写して，K-meansのようなアルゴリズムに掛けることができる.
クラスタリングを行う際には適切な距離関数を使うことが非常に重要で，適切な距離を使うためにクラスタリングアルゴリズムを選んでもよいほどである. ほとんどのアルゴリズムは任意の距離関数で使える． 適切な距離関数はモデル選択理論を使って選ぶことが出来る．