・SVM(サポートベクターマシン)について
・また最後に、個人的な趣味でコンピュータ将棋における活用を
まとめてみました。
１．SVMの概要
SVM：Understanding Support Vector Machine algorithm from examples (along with code)
http://www.analyticsvidhya.com/blog/2015/10/understaing-support-vector-machine-example-code/?utm_content=buffer4951f&utm_medium=social&utm_source=twitter.com&utm_campaign=buffer
英語記事ですが、入りとしてはこちらが個人的なおすすめです。
数式での説明なしで、グラフィカルにSVMの概念を説明がしっかりとされていて、
非常にとっつきやすいと思います。
・境界面を引くことで分類を行う
・平均や分散を用いないため、データを挿入したり変更したりしても、
全体的な再計算の手間が生じない
ことが分かります。
２．SVMという手法について
PRML(パターン認識と機械学習)をまとめている
素晴らしい記事がすでにあるので、そちらを参照。
1). 線形SVM
上記事では、境界面の引き方を厳密に定義していませんが、
マージン（分類境界と訓練データ間の最短距離）を最大化する最適化問題で、
凸計画問題の双対問題を解けばいいことがわかります。
2). 非線形SVM
マージンを非線形関数にすることで、より複雑な分類が可能になりました。
しかし、これでも重なりがある場合分類は難しい。
3). ソフトマージンSVM
ここまでは、ハードマージンSVMといわれている、
入力空間xでデータを完全に分離できることを仮定してきた手法でした。
一方、ソフトマージンSVMは、上記のように重なりがある場合の分類を克服するために、
誤分類に対してペナルティを与える手法です。
誤分類が多いほど、最小化の妨げとなるようにペナルティを加えます。
結果、最小化しようとするとなるべく誤分類が少なくなるように
パラメータを調整しようとするようになります。
ペナルティを大きくするほど、正確な分類が可能となります。
分類境界がどんなに細かくなってしまいますが…
３．コンピュータ将棋でのSVMの活用
SVMによる詰み予測とその応用
三輪誠氏 東京大学大学院新領域創成科学研究科基盤情報学専攻(当時)
http://repository.dl.itc.u-tokyo.ac.jp/dspace/bitstream/2261/187/1/K-00177.pdf
将棋における詰みを予測するために、SVMが用いられています。
将棋において、詰みの有無を判断することはとても重要なのですが、
"SVMを用いた詰み予測を用いることで、探索時間を62%まで削減することができた。"
というのが、こちらの論文の主旨です。
コンピュータ将棋に対して、
・評価関数への機械学習の適用
・局面を探索する探索アルゴリズム
について詳しく書かれていますので、非常に勉強になるかと思います。
"２．SVMという手法について" において、段階を踏んで解説をしましたが、
実用的には、計算コストや簡易性から、おおよそ１．の線形SVMで十分だと思います。
非線形SVMを当てはめる研究もありますが、これは逆効果だと個人的には思います。
かかる計算コストに対して、得られる精度はわずかですので。
補足：コンピュータ将棋・囲碁における機械学習活用
http://www.slideshare.net/TakashiKato2/ss-57966067
自分が上げたものですが、コンピュータ将棋における機械学習の活用方法は、こちらを参照。