・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
http://aidiary.hatenablog.com/entry/20100501/1272712699
上記事では、境界面の引き方を厳密に定義していませんが、
マージン（分類境界と訓練データ間の最短距離）を最大化する最適化問題で、
凸計画問題の双対問題を解けばいいことがわかります。
##2). 非線形SVM
http://aidiary.hatenablog.com/entry/20100502/1272804952
マージンを非線形関数にすることで、より複雑な分類が可能になりました。
しかし、これでも重なりがある場合分類は難しい。
##3). ソフトマージンSVM
http://aidiary.hatenablog.com/entry/20100503/1272889097
ここまでは、ハードマージン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
自分が上げたものですが、コンピュータ将棋における機械学習の活用方法は、こちらを参照。