EEIC前期実験i2 第4日

本日のメニュー

• 教師なし学習
  • クラスタリング
  • 次元圧縮
  • 非負値行列因子分解

はじめに

これまで学んだ線形回帰やロジスティック回帰、ニューラルネットワークでは、入力データと正解ラベルの組を用いてモデルを学習してきた。このような学習を教師あり学習と呼ぶ。

一方、教師なし学習では正解ラベルは与えられない。与えられるのはデータそのもののみである。

\[ \mathbf{X} = \begin{bmatrix} \mathbf{x}_1 \ \mathbf{x}_2 \ \ldots \ \mathbf{x}_N \end{bmatrix} \in \mathbb{R}^{D \times N} \]

教師なし学習の目的は、

• 類似したデータ同士をグループ化する
• データをより少ない特徴で表現する
• データの背後に存在する潜在構造を発見する

ことである。

本日は代表的な教師なし学習手法として、

• k-meansクラスタリング
• 主成分分析（Principal Component Analysis; PCA）
• 非負値行列因子分解（Nonnegative Matrix Factorization; NMF）

を学ぶ。

さらに最後に、これらの手法を低ランク近似という統一的な視点から理解する。 低ランク近似は現在の深層学習におけるモデル圧縮にもつながる重要な視点である。

---

クラスタリング

クラスタリングとは

クラスタリングとは、似たデータ同士を同じグループにまとめる問題である。

例えば顧客データを分析する場合を想定すると、

• 若年層
• ファミリー層
• 高齢層

のようなグループが観測されるデータから自然に発見されることが期待される。

クラスタリングでは正解ラベルが存在しないため、データ間の距離や類似度を用いてグループ化を行う。

---

k-meansクラスタリング

k-meansクラスタリング（k-means法）は最も代表的なクラスタリング手法である。\(N\)個あるデータ点に対して、これらのデータを代表する点を\(K\)個生成（計算）し、これをデータセットの簡易表現とするという考え方である。

基本的に、クラスタ数はあらかじめ与えることが多い。データセットに対する最適なクラスタ数決定は回帰におけるモデル複雑度の考え方に近く、さまざまな方法が考えられる。ここではまずクラスタ数 \(K\)を所与のものとしてあらかじめ固定する。

各クラスタの中心を

\[ \mathbf{\mu}_1,\mathbf{\mu}_2,\ldots,\mathbf{\mu}_K \]

とする。

各サンプルは最も近いクラスタ中心へ割り当てられる。

\[ c_i = \arg\min_k \Vert \mathbf{x}_i-\mathbf{\mu}_k \Vert^2 \]

ここで \(c_i\) はサンプル \(\mathbf{x}_i\) が属するクラスタ番号である。

---

目的関数

k-means法は代表点だけを用いて、データセットを近似するという考え方である。そのため直感的には次の目的関数を最小化すればよいことになる。

\[ J= \sum_{i=1}^{N} \Vert \mathbf{x}_i-\mathbf{\mu}_{c_i} \Vert^2 \]

すなわちデータ点を代表点で置き換えたと仮定した場合の二乗誤差の総和である。一方で、別の見方をするとクラスタ中心から所属するデータ点をみた時のクラスタ内部のばらつきを表しているともいえる。

この観点からみると k-means法は「クラスタ内部の分散をできるだけ小さくする」ようにクラスタ中心を求めるアルゴリズムと考えることもできる。

---

アルゴリズム

k-means法の目的関数は直感的にわかりやすいが、実は最適化は少し考える必要がある。「データ点を距離最小の代表点を対応づける」という操作が非連続的であるため、この目的関数を微分して勾配法で... という形で記述しにくい。

そこで、まずそれぞれのクラスタ単位での二乗誤差の総和をさらにクラスタ全部で加算するというふうに置き換える。

\[ J = \sum_{k=1}^{K} \sum_{\mathbf{x} \in C_k} \Vert \mathbf{x}-\mathbf{\mu}_{k} \Vert^2 \]

\(C_k\) はクラスタ番号\(k\)に所属するデータ点の集合を表す。さらにデータ点\(\mathbf{x}_{n}\) が クラスタ\(k\)に所属する場合に1、そうでない場合に0を取る変数 \(r_{nk}\) を導入する。すると目的関数は

\[ J = \sum_{k=1}^{K} \sum_{n=1}^{N} r_{nk} \Vert \mathbf{x}_n-\mathbf{\mu}_{k} \Vert^2 \]

この目的変数の\(\mathbf{\mu}_{k}\) に対する勾配をもとめ、極小点を導くことで更新式が導出できる。

最終的にk-means法は次の手順を繰り返す。

1. クラスタ中心を初期化する
2. 各サンプルを最近傍のクラスタへ割り当てる
3. クラスタ中心を再計算する
4. 収束するまで繰り返す

クラスタ中心は次式で更新される。

\[ \mathbf{\mu}_k= \frac{1}{N_k} \sum_{i:c_i=k} \mathbf{x}_i \]

ここで \(N_k = |C_k|\) はクラスタ \(k\) に属するサンプル数である。

演習（座学・実装なし）

上述の目的関数から、クラスタ中心の更新式を導出せよ。\(r_{nk}\) は割り当て後のものとしてよい（\(\mathbf{\mu}_{k}\)で偏微分するとよい）

k-means 法は極小点に基づく更新アルゴリズムであるため、クラスタ中心の初期化への依存性がある。以下にいくつかの方策を示す。

• \(D\)次元空間（与えられたデータの次元）のベクトルとしてランダムにセットする
• 与えられたデータからランダムに選択する
• LBG（Linde-Buzo-Gray）アルゴリズム
• k-means++

最初の2つは直感的であるが、制御しにくい側面もある。特に空間から完全にランダムに決定してしまうと、与えられたデータの全てと対応しない値が初期値となる可能性もあり、所望のクラスタ数を実現できない場合もある。データから選択した場合はその心配はないものの、たまたま選んだデータが外れ値で、周辺に値が存在しなような場合は、割り当て1のクラスタが生まれる可能性もある。

LBGアルゴリズムは主に音声符号化で最初に提案されたアルゴリズムである。以下の手順でクラスタ中心を決定していく。

1. 直前のステップでクラスタ中心\(\mathbf{\mu}\)に着目
2. このクラスタ中心に適当な摂動ベクトル\(\mathbf{\epsilon}\)を加減し、\(\mathbf{\mu}_1 = \mathbf{\mu} + \mathbf{\epsilon}\), \(\mathbf{\mu}_2 = \mathbf{\mu} - \mathbf{\epsilon}\) と二つのクラスタ中心に分割する。
3. これらを初期値としてk-means法を回す
4. 収束したクラスタ中心をさらに2つずつに分割し、同様に繰り返していく。データ全体の中心から出発するので、比較的安定に動作する。

このアルゴリズムはデータ全体の平均を出発点として、倍々にクラスタ数を増加させていく。

一方k-means++ は、データ点から選択する初期化であるが、ランダムではなく、確率に距離に基づく偏りを持たせて選択していく。

1. 一点をデータから選択する。
2. この選ばれたクラスタ中心と全てのデータ点との距離をとる。
3. 距離が大きいものほど高い確率で選ばれるように重みづけをして、次の点を選択する。
4. これを所望のクラスタ数まで繰り返す。

演習（k-means法の実装）

NumPyを用いて k-means法を実装せよ。

実装方針として以下の関数を完成させて組み合わせることになる。

def assign_clusters(X, centers):
    pass

def update_centers(X, labels, K):
    pass

def kmeans(X, K, max_iter=100):
    pass

データ点としては、分類の時に用いたような、中心が既知の正規分布を複数用意し、これらからサンプリングした擬似データを使用する。

また以下の点を確認し、考察せよ。

• 各反復における目的関数の値を計算し、グラフ等にまとめよ。
• クラスタ中心の変化を確認せよ。matplotlib等で可視化するとよい。
• 収束までの反復回数を記録せよ。収束は目的関数の変化率が一定以下になった場合、もしくはクラスタ割り当てが変化したデータの個数で判定することが多い。

演習（k-means法の性質を考察する）

さらに以下の条件を変更して実験、考察を行え。

• クラスタ数 \(K\) => 擬似データの正規分布数と比べながら実験する
• 初期値 => いくつかの初期化法を試す
• サンプル数 => サンプリングするデータ数を変化させる
• 細長いクラスタを生成し、k-means法の結果を観察せよ。サンプリングする分布の分散共分散行列を変化させると良い

アルゴリズムデザイン

k-meansは

1. なんらかの誤差関数というものを定義する
2. 変数の更新を繰り返す
3. 更新のたびに誤差関数が減る（ポイント）
4. よって大雑把に言うといつか局所解に収束する

という逐次更新型のアルゴリズムの良い教育的例題になっているともいえる。皆さんは今後卒論や修論で自分でアルゴリズムをデザインすることになるが、この「誤差を作り反復の度に減らす」という考え方を是非身に着けておくとよいだろう。例えば深層学習やLLMを使うような複雑な処理を内側に用いるとしても、

1. LLMでXXXする
2. 得られた結果でYYYをする
3. 1に戻る

といった逐次型のアルゴリズムを考えるとして、その毎ステップで誤差が減る一方であることを保証できるなら、局所解におおざっぱに収束するものだと主張することが出来る。逆に言うと、各ステップで誤差が増える可能性があるなら、このアルゴリズムは収束しない。

次元削減

次元削減とは

高次元データをより少ない次元で表現することを考える。

例えば100次元のデータを2次元へ圧縮できれば、

• 可視化が容易になる
• 計算量を削減できる
• ノイズを除去できる

といった利点がある。また現実のデータは実行的には少ない次元で表現できることも多い。例えば地球を想像してみよう。地球は何次元か。球体なので3次元である。これはもちろん正しいのだが、地図情報として捉えた場合、地殻の下にあまり興味はないので、緯度経度でデータが表現する方が良さそうである。この地球の実効的な次元数は2次元ということができる。この例では曲面を考えているため、これから考える次元削減よりもう一歩複雑ではあるが、このように次元を落として考えることが実用上重要な場面は、機械学習では現実よりさらに頻繁に登場する。

我々は何次元にいるのか --多様体のお話--

このタイトルをみてアニメを見たくなった人は一旦落ち着こう。

さて、さきほどの球面の話、例えば日本からアルゼンチンに向かう最小距離はといった場合に、地球を貫通するのが最短というのがユークリッド距離的には正しい。しかしさきほどの議論の通り、実生活の実効的な空間は地球表面であるため、地球表面を通った距離で考える必要があるのは想像できるだろう。このような見方において、地球表面を「多様体」、この考え方でみた距離のことを「測地線距離」という。この点では我々は実効的に2次元にいるといってもよい。なおこのような多様体は機械学習でも重要な話題であり、今日扱う次元圧縮にデータそのものの多様体構造を考慮した方法論のことを「多様体学習（manifold learning）」とよぶ。このあと出てくる主成分分析を全ての基本としつつ、なかなか面白い世界が広がっているので興味がある人は調べてみるとよい。

---

主成分分析

分散最大化

主成分分析では、データをある方向へ射影したときの分散が最大となる方向を求める。データが\(D\)次元だった場合に、全てをこの方向に収める（この向きでの大小のみで表現する）といった見方である。つまり、データ全体を表現したいときに、最もばらつくように射影する軸の向きが最重要の成分という風に考える。

射影方向を\(\mathbf{w}\), \(\Vert\mathbf{w}\Vert = 1\) （単位ベクトル）とすると、

\[ z_i= \mathbf{w}^\top \mathbf{x}_i \]

となる。

主成分分析は、この射影後の分散を最大にする方向を求める問題である。\(\Vert\mathbf{w}\Vert = 1\) をラグランジュの未定乗数法で制約条件として加え、分散値を\(\mathbf{w}\) と 未定乗数\(\lambda\) で偏微分する方針となる。

---

共分散行列

これを踏まえて具体的な手順に移る。まずデータを中心化する。

\[ \tilde{\mathbf{x}}_i= \mathbf{x}_i-\bar{\mathbf{x}} \]

中心化後のデータ行列を\(\tilde{\mathbf{X}} \in \mathbb{R}^{D\times N}\)とする。

共分散行列は

\[ \mathbf{\Sigma}= \frac{1}{N} \tilde{\mathbf{X}}\tilde{\mathbf{X}}^\top \]

で与えられる。

---

固有値分解

実は先ほどの分散最大化問題の帰結として、主成分は次の固有値問題として求められる。

\[ \mathbf{\Sigma} \mathbf{w}= \lambda \mathbf{w} \]

最大固有値に対応する固有ベクトルが第一主成分である。 第二主成分以降は、既に求めた主成分と直交する方向から選ばれる。

---

主成分への射影

上位 \(r\) 個の主成分を並べた行列を

\[ \mathbf{W}= \begin{bmatrix} \mathbf{w}_1, \mathbf{w}_2,\ldots & \mathbf{w}_r \end{bmatrix} \in \mathbb{R}^{D\times r} \]

とすると、

低次元表現は

\[ \mathbf{Z}= \mathbf{W}^\top\mathbf{X} \]

で与えられる。

---

演習（座学・実装なし）

分散最大化の定式化から主成分分析が固有値問題として帰着することを式変形によって示せ。

演習（PCAの実装）

NumPyを用いてPCAを実装せよ。

手順

1. データを中心化する
2. 共分散行列を計算する
3. 固有値分解を行う
4. 上位主成分を選択する
5. データを射影する

def pca(X, n_components):
    pass

演習（擬似データを用いたPCAの分析）

正規分布に従う3次元以上のデータを擬似データとして生成し、2次元にPCAをした上で表示せよ。データは以下の方法で作成してみる。方針としては分散共分散行列をランダムに生成する。

1. 次元\(D > 2\) を決めて、適当なサイズの行列\(A \in \mathbb{R}^{D\times N_1}\)を生成する。\(N_1\) は適当に大きくせよ。
2. \(AA^\top \in \mathbb{R}^{D\times D}\) は正定値行列となるので、これを分散共分散行列として、\(D\)次元正規分布からサンプルを\(N_2\)個生成する。

この擬似データの基本性質は、生成に用いた分散共分散行列の固有値に集約している。得られたサンプルでのPCAとこの値の比較を通して以下を行え。

• 各主成分の寄与率を計算せよ
• 何次元まで残せば十分か考察せよ

PCAは可視化やデータの圧縮に至るまで非常に重要なアルゴリズムである。scikit-learn等でも簡単に利用できるが、理論的背景を知っておくと良い。

faiss

k-meansとPCAは工学上極めて有用なツールであり、未知のデータを前にしてまず行うことは（１）k-means等でのクラスタリング、（２）PCA等での次元削減、（３）フーリエ変換等での周波数解析、などになるだろう。よって、これらを高速に計算することは極めて重要なテーマである。

このような高速計算のためのデファクトのライブラリは、Meta社からOSSで公開されているfaissである。faissは元々最近傍探索（day3を思い出そう）のライブラリであるが、近傍探索とk-means等は計算的にはかなり近い関係にある（k-meansにおいて計算時間がかかるステップはどこなのか、それはどういう計算なのか、考えてみよう）。faissには様々な機能があるが、k-meansやPCAに関しては機能が切り出されて関数１つ呼ぶだけで使えるようになっている。余力のある人は是非上記を実行してみて、自分の実装と速度を比較してみよう。信じらないぐらいfaissが高速であることがわかる。そして、このような単純な処理になぜここまで速度差が出るのか、是非考えてみよう。

非負値行列因子分解

NMFとは

主成分分析では、主成分の係数に負の値が含まれる。そのため、得られた特徴の意味を解釈しにくい場合がある。

そこで非負行列（全ての要素が負にならない行列）

\[ \mathbf{X} \ge \mathbf{0} \in \mathbb{R}^{D\times N} \]

に対して、

\[ \mathbf{X} \approx \mathbf{W}\mathbf{H} \]

となる分解を求める。

ただし、

\[ \mathbf{W} \ge \mathbf{0} \in \mathbb{R}^{D\times K} \]

および

\[ \mathbf{H} \ge \mathbf{0} \in \mathbb{R}^{K\times N} \]

である。\(K\) は通常\(D\)や\(N\) に対して非常に小さい。この\(K\)をランクとよぶ。 この手法を非負値行列因子分解（Non-negative Matrix Factorization: NMF）と呼ぶ。

---

NMFの解釈

NMFではデータを複数の部品の足し合わせとして表現する。

例えば顔画像であれば、

• 目
• 鼻
• 口

といった部品が抽出される。これは固有顔と呼ばれる初期の顔の因子分解に対して、パーツを加算的に扱う方法論となっている。

また文書データ（文章中の単語頻度を行列で表した場合）では、

• スポーツ
• 政治
• 科学

などの潜在トピックが抽出される。これは潜在意味解析（LSA）と呼ばれ、LSAとNMFは一般化KLダイバージェンス基準の元で理論的等価である。

最適化問題

もっとも基本的なNMFの場合では次の目的関数を最小化する。

\[ J = \Vert\mathbf{X}-\mathbf{W}\mathbf{H}\Vert_F^2 \]

ここで

\[ \Vert \mathbf{A} \Vert_F = \sqrt{ \sum_{i,j} a_{ij}^2 } \]

はフロベニウスノルムである。ベクトルノルムの行列版と考えればよい。なおNMFの目的関数としては、一般化KLダイバージェンス（Iダイバージェンス）や板倉斎藤距離などが知られており、それぞれに対応する反復更新アルゴリズムがある。今回の目的関数はフロベニウスノルム基準でのNMFと呼ばれる。NMFの重要な制約として、全ての値が負にならないというものがある。そのため、更新式は乗法更新アルゴリズムと呼ばれ、非負の値をかけることで更新され、更新の過程で値が0になる要素があるとそれはそのまま0となり続ける。

非負制約は機械学習的には「スパース誘導効果」と呼ばれる効果を内在しており、データをできる限り少数の正の重みで表現しようとする。

乗法更新アルゴリズム

Lee と Seung による乗法更新法では、以下の更新を交互に行う。

Hの更新

\[ \mathbf{H} \leftarrow \mathbf{H} \odot \frac{\mathbf{W}^\top \mathbf{X}} {\mathbf{W}^\top \mathbf{W} \mathbf{H}} \]

Wの更新

\[ \mathbf{W} \leftarrow \mathbf{W} \odot \frac{\mathbf{X} \mathbf{H}^\top} {\mathbf{W} \mathbf{H} \mathbf{H}^\top} \]

ここで

• \(\odot\) は要素ごとの積
• 分数は要素ごとの除算

を表す。

要素ごとに書くと、

\[ h_{kj} \leftarrow h_{kj} \frac{ (\mathbf{W}^\top \mathbf{X})_{kj} }{ (\mathbf{W}^\top \mathbf{W} \mathbf{H})_{kj} } \]

\[ w_{ik} \leftarrow w_{ik} \frac{ (\mathbf{X} \mathbf{H}^\top)_{ik} }{ (\mathbf{W} \mathbf{H} \mathbf{H}^\top)_{ik} } \]

となる。

---

アルゴリズム

1. \(\mathbf{W}, \mathbf{H}\) を正の乱数で初期化する。
2. 以下を収束まで繰り返す（以下の更新式参照）。
3. 得られた \(\mathbf{W}, \mathbf{H}\) を出力する。

\[ \mathbf{H} \leftarrow \mathbf{H} \odot \frac{\mathbf{W}^\top \mathbf{X}} {\mathbf{W}^\top \mathbf{W} \mathbf{H}} \]

\[ \mathbf{W} \leftarrow \mathbf{W} \odot \frac{\mathbf{X} \mathbf{H}^\top} {\mathbf{W} \mathbf{H} \mathbf{H}^\top} \]

演習（NMFの実装）

NMFを実装せよ。擬似データとしては適当な正規乱数で生成したベクトルの要素をそれぞれ2乗したものをサンプルデータとする。\(D\)や\(N\)は適宜設定して良い。

• 目的関数の推移を記録せよ
• 近似誤差の変化を確認せよ
• ランクを変更して比較せよ

低ランク近似という統一的視点

ここまで学んだ手法は、一見すると異なるアルゴリズムに見える。

しかし、いずれも「元のデータをより単純な構造で近似する」という共通の考え方に基づいている。 データ行列を\(\mathbf{X} \in \mathbb{R}^{D\times N}\) とする。

---

k-means法

クラスタ割当行列を\(\mathbf{Z} \in [0,1]^{k\times N}\)

とすると、

\[ \mathbf{X} \approx \mathbf{C}\mathbf{Z} \]

と表現できる。

ここで

• \(\mathbf{Z}\) はクラスタ割当行列
• \(\mathbf{C} \in \mathbb{R}^{D\times k}\) はクラスタ中心行列

である。

---

PCA

主成分数を \(r\) とすると、

\[ \mathbf{X} \approx \mathbf{U}\mathbf{V}^\top \]

となる。\(\mathbf{U} \in \mathbb{R}^{D \times r}\), \(\mathbf{V} \in \mathbb{R}^{N \times r}\) である。

---

NMF

NMFでは

\[ \mathbf{X} \approx \mathbf{W}\mathbf{H} \]

となる。

---

共通点

いずれも元のデータ行列を

\[ r \ll d \]

となる低次元構造で近似している。

このような考え方を低ランク近似という。

教師なし学習の多くは、低ランク近似という視点から統一的に理解できる。

---

発展トピック

以下では本日の教師あり学習に関連するキーワード、トピックを簡単に示す。発展課題として適宜調査、実装を試みてみるとよい。

自己組織化マップ

自己組織化マップは競合学習に基づく教師なし学習手法である。

k-means法では勝者となったクラスタ中心のみを更新する。一方、自己組織化マップではクラスタ中心を擬似的なトポロジーに配置した上で、このトポロジー上の近傍ノードも同時に更新することで、データのトポロジ構造を保存する。2次元のトポロジーやハニカム構造などトポロジーとして仮定することで、データの可視化などにも適している。

---

ガウス混合モデル

ガウス混合モデルでは、クラスタを確率分布として表現する。k-means法の確率的拡張とみなすことができる。

---

オートエンコーダ

オートエンコーダはニューラルネットワークによる次元削減手法である。非線形な低次元表現を学習できる。活性化関数に恒等写像を仮定した場合にPCAと等価となる。

---

t-SNEとUMAP

t-SNEやUMAPは高次元データの可視化によく用いられる。主成分分析では表現できない非線形構造を可視化できる。

---

まとめ

本日は教師なし学習の代表的な手法を学んだ。

• k-means法はクラスタを発見する
• PCAは重要な方向を発見する
• NMFは非負制約のもとで、データの潜在因子（正の重みづけ）を発見する

また、これらの手法はいずれも低ランク近似という共通の考え方に基づいている。この視点は、後に学ぶ生成モデルや表現学習を理解する上でも重要となる。