ホー・カシャップアルゴリズムは、機械学習において線形分類器を訓練するための反復手続きである。1965年にYu-Chi HoとRangasami L. Kashyapによって開発され、特徴空間内でクラスを分離する超平面を見つける判別ベースの学習手法の一族に属する。重みベクトルのみを調整する初期のパーセプトロン型規則とは異なり、ホー・カシャップアルゴリズムはマージンベクトルも調整し、訓練データが厳密に線形分離可能でない場合でも、緩和された意味で解が存在するならば収束することができる。
このアルゴリズムは二乗誤差基準関数を最小化する。訓練サンプルの集合が与えられ、各サンプルは特徴ベクトルで表される。目標は、特徴行列と重みベクトルの積が正のマージンベクトルに等しくなるような重みベクトルとマージンベクトルを見つけることである。この手続きは、勾配降下ステップを用いたマージンベクトルの更新と、最小二乗解による重みベクトルの更新を交互に行う。この二重更新により、各反復で重み更新が閉形式となり、計算効率が良く、基準の単調減少が保証される。
数学的定式化
訓練データが\(n\)個のサンプルから構成され、各サンプルが\(d\)個の特徴を持ち、\(n \times d\)行列\(X\)に配置されるとする。各サンプルは2つのクラスのいずれかに属するとラベル付けされ、ラベルは+1または-1として符号化される。アルゴリズムは、\(Xw = b\)となるような重みベクトル\(w\)とマージンベクトル\(b\)（すべての成分が正）を求める。最小化すべき基準は\(J(w, b) = \|Xw - b\|^2\)である。
更新規則は以下の通りである：
- \(b_{k+1} = b_k + \rho (Xw_k - b_k)\)。ここで\(\rho\)は学習率であり、\(b\)の負の成分は正を維持するためにゼロに設定される。
- \(w_{k+1} = (X^T X)^{-1} X^T b_{k+1}\)。これは現在のマージンベクトルに対する最小二乗解である。
この2段階のプロセスは、基準が閾値を下回るか、最大反復回数に達するまで繰り返される。データが線形分離可能であれば、アルゴリズムは解に収束することが保証される。そうでない場合は振動する可能性があり、非分離の場合に収束を強制するために、マージンベクトルに小さな正の定数を加えるのが一般的な手法である。
歴史的背景
このアルゴリズムは、パターン認識とニューラルネットワークが急速に発展した1960年代半ばに導入された。Yu-Chi HoとRangasami L. Kashyapは、1965年にIEEE Transactions on Electronic Computersにその研究を発表した。当時、線形分類器は文字認識や信号分類などのタスクにおける主要なツールであった。ホー・カシャップアルゴリズムは、データが完全に分離可能でない場合に収束に失敗する可能性があったパーセプトロン学習規則に対する改良を提供した。マージンベクトルを導入することで、ノイズや重なりを含むデータを扱える、より頑健なアプローチを実現した。
この手法は、同じ時期にBernard Widrowとその同僚によって開発された最小平均二乗（LMS）アルゴリズムやウィドロー・ホフ規則と密接に関連している。しかし、ホー・カシャップアルゴリズムはマージンを明示的にモデル化しており、より良い汎化のためにマージンを重視する現代のサポートベクターマシン（SVM）の先駆けとなっている。
応用と拡張
元の形式では、ホー・カシャップアルゴリズムは手書き数字の分類やノイズ中の信号検出などのパターン認識問題に適用された。数十年にわたり、いくつかの方法で拡張されてきた：
- 非線形拡張：カーネル関数を通じて入力をマッピングすることで、カーネル化されたSVMと同様に、非線形分離可能なデータに適用できる。
- 正則化：\(\lambda \|w\|^2\)などのペナルティ項を基準に追加することで、汎化が向上し、悪条件の行列を扱える。
- 多クラス問題：二値定式化は、一対他または一対一戦略を用いて複数クラスに拡張できる。
- オンライン学習：サンプルが逐次到着するストリーミングデータ用の変種が開発されている。
これらの拡張により、このアルゴリズムは現代の機械学習カリキュラムにおいても関連性を保ち、線形判別分析における反復最適化の例としてしばしば教えられている。
他の手法との関係
ホー・カシャップアルゴリズムは、他のいくつかの学習手法と概念的に類似点を共有している。1958年にFrank Rosenblattによって導入されたパーセプトロンアルゴリズムも分離超平面を見つけるが、非分離データに対する収束は保証しない。ホー・カシャップアルゴリズムの最小二乗更新の使用は、Adamオプティマイザと類似している。両者は適応的調整を含むが、Adamは確率的勾配を用いた深層学習用に設計されている。対照的に、ホー・カシャップアルゴリズムは決定的でバッチベースである。
もう一つの関連手法は緩和法であり、これもマージンを調整するが、異なる更新規則を用いる。ホー・カシャップアルゴリズムは、正のマージンを強制せずに二乗誤差を最小化する最小二乗分類器としばしば比較される。マージン制約がホー・カシャップアルゴリズムに収束特性を与えている。
実践的考慮事項
ホー・カシャップアルゴリズムを実装する際には、いくつかの実践的な問題が生じる。\((X^T X)^{-1}\)の計算は大きな\(d\)に対して高価になる可能性があり、特徴が冗長な場合は行列が特異になることがある。そのような場合には、擬似逆行列や正則化手法が用いられる。学習率\(\rho\)は慎重に選ぶ必要があり、大きすぎると振動を引き起こし、小さすぎると収束が遅くなる。一般的な選択は\(\rho = 1\)であり、実際にはしばしば良好に機能する。
このアルゴリズムは特徴のスケーリングに敏感である。大きな大きさの特徴による支配を避けるために、特徴をゼロ平均と単位分散に標準化することが推奨される。テキスト分類などの高次元データでは、アルゴリズムが過学習する可能性があり、正則化が不可欠になる。
数十年が経過したにもかかわらず、ホー・カシャップアルゴリズムは貴重な教育ツールであり続けている。これは最適化と学習の相互作用を示しており、その収束証明はパターン認識理論における古典的な結果である。現代の機械学習の教科書では、単純なパーセプトロンとより高度なマージンベースの分類器の間の橋渡しとしてしばしば取り上げられている。