| 講演抄録／キーワード |
| 講演名 |
2005-10-18 11:00
マージンを保存するランダム性を限定したプロジェクションとブール空間への埋め込み
○渡邊辰也・瀧本英二・天野一幸・丸岡 章（東北大） |
| 抄録 |
（和） |
マージンが最大となる仮説を求めることは機械学習の分野における最も重要な問題のひとつである．
しかし，与えられたデータを分離する大きなマージンを持った超平面を見つけることは難しい．
本稿では，高次元空間でのマージンをほぼ保存したまま低次元空間へのランダムな写像を行うような，3つのランダムプロジェクションの手法を提案する．
これらの手法により写像された低次元空間内でパーセプトロン等のアルゴリズムを用いることで，高速に適切な仮説を探すことができる．
我々の手法は，Johnson-Lindenstrauss の補題に基づく既存の手法に比べ，マージンの保存という点では，より効果的である．
JL補題に基づく手法が任意の2点間の距離を保存するという強い性質を持つのに対し，我々の手法はマージンの保存のみを目的とするからである．
具体的には，マージンの保存性能をほぼ維持したままランダムビットを削減する写像を与え，さらに，ブール空間へのマージンを保存した写像も与える． |
| （英） |
Learning large margin classifiers is one of the most important problems in machine learning.
However, it is hard to find a hyperplane that separates two classes of given data with a large margin.
We propose three methods of random projection which randomly maps the data to a low dimensional space with the property that the margin is approximately preserved, so that a simple algorithm such as the Perceptron can be employed on the low dimensional space to quickly find a good hypothesis.
In some respects, our algorithms are more efficient than the well known random projection method based on the Johnson-Lindenstrauss Lemma.
The latter has a too strong property for our purpose that the length of any two points is preserved, while our mapping is designed only to preserve the margin.
In particular, we show that a similar performance is achieved when significantly reducing the number of random bits.
Moreover, we show that a mapping to the Boolean space serves as the margin preserving projection. |
| キーワード |
（和） |
計算学習理論 / 計算幾何学 / ランダムプロジェクション / k限定独立 / マージン / / / |
| （英） |
computational learning theory / computational geometry / random projection / k-wise independence / large margin classifier / / / |
| 文献情報 |
信学技報, vol. 105, no. 343, COMP2005-39, pp. 21-28, 2005年10月. |
| 資料番号 |
COMP2005-39 |
| 発行日 |
2005-10-11 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|