Ho–Kashyap算法是机器学习中用于训练线性分类器的一种迭代过程。该算法由何毓琦（Yu-Chi Ho）和Rangasami L. Kashyap于1965年提出，属于基于判别式学习方法的家族，旨在特征空间中寻找一个超平面以分离不同类别。与早期仅调整权重向量的感知机风格规则不同，Ho–Kashyap算法还调整一个边距向量，使其即使训练数据并非严格线性可分时也能收敛，前提是在放宽意义上存在解。
该算法最小化一个平方误差准则函数。给定一组训练样本，每个样本用一个特征向量表示，目标是找到一个权重向量和一个边距向量，使得特征矩阵与权重向量的乘积等于一个正边距向量。该过程交替进行：使用梯度下降步骤更新边距向量，以及通过最小二乘解更新权重向量。这种双重更新使得算法在每次迭代中都能获得闭式权重更新，从而计算效率高，并确保准则的单调递减。
数学表述
设训练数据由 \(n\) 个样本组成，每个样本具有 \(d\) 个特征，排列成一个 \(n \times d\) 的矩阵 \(X\)。每个样本被标记为属于两个类别之一，标签编码为+1或-1。算法寻求一个权重向量 \(w\) 和一个边距向量 \(b\)（所有分量均为正），使得 \(Xw = 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}\)，这是当前边距向量的最小二乘解。
此两步过程重复进行，直到准则低于阈值或达到最大迭代次数。如果数据线性可分，则该算法保证收敛到解；否则，它可能会振荡，常见做法是向边距向量添加一个小正常数，以强制在不可分情况下收敛。
历史背景
该算法于20世纪60年代中期提出，那是模式识别和神经网络快速发展的时期。何毓琦和Rangasami L. Kashyap于1965年在《IEEE电子计算机汇刊》上发表了他们的工作。当时，线性分类器是字符识别和信号分类等任务的主要工具。Ho–Kashyap算法相对于感知机学习规则提供了改进，因为后者在数据并非完全可分时可能无法收敛。通过引入边距向量，该算法提供了一种更稳健的方法，能够处理噪声或重叠数据。
该方法与最小均方（LMS）算法以及Widrow-Hoff规则密切相关，后者大约在同一时期由Bernard Widrow及其同事开发。然而，Ho–Kashyap算法显式建模了边距，使其成为现代支持向量机（SVM）的前身，后者也强调边距以增强泛化能力。
应用与扩展
在其原始形式中，Ho–Kashyap算法被应用于模式识别问题，例如手写数字分类和噪声中的信号检测。几十年来，它以多种方式得到扩展：
- 非线性扩展：通过核函数映射输入，该算法可应用于非线性可分数据，类似于核化SVM。
- 正则化：向准则中添加惩罚项，例如 \(\lambda \|w\|^2\)，可改善泛化并处理病态矩阵。
- 多类问题：二分类公式可通过一对多或一对一策略扩展到多类。
- 在线学习：已开发出适用于流式数据（样本依次到达）的变体。
这些扩展使该算法在现代机器学习课程中保持相关性，通常作为线性判别分析中迭代优化的示例进行教学。
与其他方法的关系
Ho–Kashyap算法在概念上与几种其他学习技术有相似之处。Frank Rosenblatt于1958年提出的感知机算法也寻找分离超平面，但不保证对不可分数据收敛。Ho–Kashyap算法使用最小二乘更新的方式类似于Adam优化器，因为两者都涉及自适应调整，尽管Adam是为带有随机梯度的深度学习而设计的。相比之下，Ho–Kashyap算法是确定性的且基于批处理。
另一种相关方法是松弛法，它也调整边距但使用不同的更新规则。Ho–Kashyap算法常与最小二乘分类器进行比较，后者最小化平方误差而不强制正边距；边距约束正是赋予Ho–Kashyap算法其收敛性质的关键。
实践注意事项
在实现Ho–Kashyap算法时，会出现几个实际问题。对于较大的 \(d\)，计算 \((X^T X)^{-1}\) 可能代价高昂，并且如果特征冗余，矩阵可能奇异。在这种情况下，会使用伪逆或正则化技术。学习率 \(\rho\) 必须谨慎选择；过大可能导致振荡，而过小则减慢收敛。常见选择是 \(\rho = 1\)，在实践中通常效果良好。
该算法对特征的缩放敏感。建议将特征标准化为零均值和单位方差，以避免大量级特征主导。对于高维数据（如文本分类），算法可能过拟合，此时正则化变得至关重要。
尽管已有数十年历史，Ho–Kashyap算法仍然是一个宝贵的教学工具。它说明了优化与学习之间的相互作用，其收敛证明是模式识别理论中的经典结果。现代机器学习教材通常将其作为简单感知机与更高级的基于边距的分类器之间的桥梁。