IEEE ICDMDMC2007 その2

Machine Learning初心者によるまったりゆるゆるDMC,二回目.とりあえず前回学習一切無しで76.8%の正答率というベンチマークが出たので,これを超えたい.

k-means

普通のk-meansでは初期ラベルをランダムに割り当てるのだが,半教師あり学習なのでちょっと手順を修正する.もっといいやり方があるかもしれない.

1.ラベルありデータを使って各ラベルの重心V_j(j=1..247)を求める.
2.ラベルなしデータx_iV_jの距離を計算し,最も近いラベルをx_iに割り当てる.
3.新しい割り当てに基づいて各ラベルの重心V_jを再計算する.
4.2.でラベルを割り当てたデータについて再度V_jとの距離を計算し,最も近いラベルを割り当て直す.
5.ラベルが変化しなければ終了.変化した場合は3.に戻る.

結果

ノルムを数通りに振って,一番良いケースで1183/2137(55.3%).
重心計算時に小手先の修正(スレッショルド以下の軸を切り捨てるなど)を加えても改善しなかった.

なんでこんなに悪いのか

重心からの距離を評価に用いるので,各ラベル付きデータが超平面上で球形ではない場合k-meansがあまり有効ではなくなる.データが超平面上で球形ということは「各アクセスポイントからの信号に同程度のバラツキが乗っている」ということなので,この仮定が今回のケースではあまり正しく無いかもしれない.

もうちょっと別の方法

  • ラベルなしの訓練データについて尤度関数を以下に定義し,最尤のものをラベルとする.wはp-ノルム.

f^i(c) = \sum_j \frac{f_j(c)}{1+w_{ij}}
ただし,ラベルありデータに対して
f^i(c) = 1(c = labbel)
f^i(c) = 0

  • j番目のテストデータにはmin:w_{ij}となる訓練データiを探し,ラベルc_iを付与

という方法を採ってみる.学習無しの際に用いてk-meansより良くクラスタリングできた,「もっとも近いデータからラベルを貰う」という発想を拡張している.分母がなぜか1+w_{ij}になっているのは,本当はexp{-w_{ij}}にしたかったけど計算時間がかかり過ぎたので妥協したというだけ.

結果

1626/2137(76.1%).良くならない…

なんで

信号強度のノルムは雑音が強すぎる?

時系列を評価に組み込む

「テストデータの全部と訓練データの一部は,時系列順に並んでいる」という情報も使えるので,こちらを使わない手は無い.
f^j(c) =w_{ij}\sum_k \lambda_1(c_{j-k},c)
 \lambda_1 = const > 1 ,if c_{j-k} == c
前後数ステップでの推定値と同じラベルに対して定数倍の重みをつけてやる.

結果

重みのパラメータを幾らか振り,一番良いケースで1724/2137(80.67%).だいぶ改善された.

Graph basedな何かを追加

今回の問題では,「クライアントがグリッド上をどう移動するか」を推定する.グリッドが具体的にどういう並びなのかは与えられていないが,あるグリッドにいるクライアントが次の時間にどこにいそうなのかは,訓練データからある程度絞り込めそうではある.
学習の際にあるスレッショルドkを設定し,i番目とi+1番目のデータについて,
\left( c_i \not= c_{i+1} \right) && \left( f^i(c_i),f^{i+1}(c_{i+1}) > k \right)
が成立したとき,ラベルc_ic_{i+1}は隣接している可能性が高い.そこで,学習中にこのようなケースに遭遇したとき,
1.c_i,c_{i+1}の間に重み付きのbranchを追加する
2.既にbranchが形成されていた場合は重みを増やす
という操作を行う.そして,推定のフェーズではこの重みをf^j(c)に対して付与してやればよい.

結果

1759/2137(82.31%). コンテスト優勝者の成績が1756/2137(82.17%)なので,誤差の範囲とはいえわずかに超えることができた.目標の一つを達成したのでこれで閉じてもいいのだけど,Graph-based SSLやら色々試してみたら面白そうなので,後日取り組んでみる予定.