早稲田大学 創造理工学研究科 経営システム工学専攻 2016年7月実施 情報数理応用 問題2

标签：

• Waseda-University
• K-Means
• Decision-Tree
• Support-Vector-Machine
• Ensemble-Learning

Author

祭音Myyura

Description

多次元特徴空間上のデータへ適用するパターン認識・機械学習について答えよ。

1. 教師なし学習と教師あり学習の概要を説明せよ。
2. k-means 法の問題設定と手法を説明せよ。
3. 決定木による分析のモデルと手法を説明せよ。
4. サポートベクトルマシンの分析手法を説明せよ。
5. 集団学習またはアンサンブル学習の代表的手法と概要を説明せよ。

Kai

[小問 1]

教師あり学習は、入力 $x_i$ と正解ラベルまたは目的値 $y_i$ の組から、未知データの $y$ を予測する関数を学習する。分類と回帰が代表例である。

教師なし学習は正解 $y_i$ を用いず、入力データの分布、まとまり、低次元構造などを抽出する。クラスタリング、次元削減、密度推定が代表例である。

[小問 2]

$n$ 個のデータ $x_i\in\mathbb R^d$ を、あらかじめ与えた $K$ 個のクラスタへ分ける。目的関数はクラスタ内平方和

$$\boxed{ J=\sum_{k=1}^{K}\sum_{i:z_i=k} \lVert x_i-\mu_k\rVert^2 }$$

である。

1. $K$ 個の中心 $\mu_k$ を初期化する。
2. 各点を最も近い中心へ割り当てる。
3. 各クラスタの平均で中心を更新する。
4. 割当てまたは目的関数が収束するまで2と3を反復する。

各反復で $J$ は増加しないため有限個の割当てのいずれかへ収束するが、一般には局所最適解である。そこで k-means++ や複数回初期化を用いる。

[小問 3]

決定木は、各内部節点で「特徴量 $x_j$ がしきい値以下か」のような規則により特徴空間を再帰的に分割し、葉でクラスまたは予測値を出力するモデルである。

分類木では Gini 不純度やエントロピーの減少、回帰木では平方誤差の減少が最大となる分割を選ぶ。木を深くしすぎると過学習するため、最大深さ、葉の最小標本数、剪定などで複雑度を制御する。

[小問 4]

線形 SVM は、ラベル $y_i\in\{-1,1\}$ に対し、分離超平面 $w^{\mathsf T}x+b=0$ と最近傍点とのマージンを最大化する。ソフトマージンでは

$$\min_{w,b,\xi} \frac12\lVert w\rVert^2+C\sum_i\xi_i$$

subject to

$$y_i(w^{\mathsf T}x_i+b)\geq1-\xi_i,\qquad \xi_i\geq0$$

を解く。境界を決める点がサポートベクトルである。カーネル関数を用いれば、内積を高次元特徴空間の内積に置き換えて非線形境界を表現できる。

[小問 5]

• バギング：ブートストラップ標本ごとに学習器を作り、平均または多数決を取る。分散を下げる。ランダムフォレストは、決定木ごと・分割ごとに使う特徴もランダム化する。
• ブースティング：誤分類例や残差を重視しながら弱学習器を逐次追加する。AdaBoost、勾配ブースティング、GBDT が代表例である。
• スタッキング：複数モデルの予測値を新たな特徴とし、メタ学習器で統合する。

これらは学習器の誤りが完全には相関しないことを利用し、単独モデルより汎化性能を高める。