Ho–Kashyap rule

Given a training set consisting of samples from two classes, the Ho–Kashyap algorithm seeks to find a weight vector $\backslash mathbf\{w\}$ and a margin vector $\backslash mathbf\{b\}$ such that:

$$\backslash mathbf\{Yw\}\; =\; \backslash mathbf\{b\}$$

where $\backslash mathbf\{Y\}$ is the augmented data matrix with samples from both classes (with appropriate sign conventions, e.g., samples from class 2 are negated), $\backslash mathbf\{w\}$ is the weight vector to be determined, and $\backslash mathbf\{b\}$ is a positive margin vector.

The algorithm minimizes the criterion function:

$$J(\backslash mathbf\{w\},\; \backslash mathbf\{b\})\; =\; ||\backslash mathbf\{Yw\}\; -\; \backslash mathbf\{b\}||^2$$subject to the constraint that $\backslash mathbf\{b\}\; >\; \backslash mathbf\{0\}$ (element-wise).

Given a problem of linearly separating two classes, we consider a dataset of elements $\backslash \{(\backslash mathbf\{x\_i\},\; y\_i)\backslash \}\_\{i\; \backslash in\; 1:N\}$ where $y\_i\; \backslash in\; \backslash \{-1,\; +1\backslash \}$. Linearly separating them by a perceptron is equivalent to finding weight and bias $\backslash mathbf\{w\},\; b$ for a perceptron, such that:$$\backslash begin\{bmatrix\}$$

y_1 \mathbf{x}_1 & 1 \\

\vdots & \vdots \\

y_N \mathbf{x}_N & 1 \\

\end{bmatrix}

\begin{bmatrix}

\mathbf{w} \\ b

\end{bmatrix} > 0

The idea of the Ho–Kashyap rule is as follows:

• Given any $\backslash mathbf\{b\}$, the corresponding $\backslash mathbf\{w\}$ is known: It is simply $\backslash mathbf\{w\}\; =\; \backslash mathbf\{Y\}^+\; \backslash mathbf\{b\}$, where $\backslash mathbf\{Y\}^+$ denotes the Moore–Penrose pseudoinverse of $\backslash mathbf\{Y\}$.
• Therefore, it only remains to find $\backslash mathbf\{b\}$ by gradient descent.
• However, the gradient descent may sometimes decrease some of the coordinates of $\backslash mathbf\{b\}$, which may cause some coordinates of $\backslash mathbf\{b\}$ to become negative, which is undesirable. Therefore, whenever some coordinates of $\backslash mathbf\{b\}$ would have decreased, those coordinates are unchanged instead. As for the coordinates of $\backslash mathbf\{b\}$ that would increase, those would increase without issue.

Formally, the algorithm is as follows:

1. Initialization: Set $\backslash mathbf\{b\}(0)$ to an arbitrary positive vector, typically $\backslash mathbf\{b\}(0)\; =\; \backslash mathbf\{1\}$ (a vector of ones). Set the iteration counter $k\; =\; 0$. Set $\backslash mathbf\{w\}(0)\; =\; \backslash mathbf\{Y\}^+\; \backslash mathbf\{b\}(0)$
2. Loop until convergence, or until iteration counter exceeds some $k\_\{max\}$.
3. Error calculation: Compute the error vector: $\backslash mathbf\{e\}(k)\; =\; \backslash mathbf\{Yw\}(k)\; -\; \backslash mathbf\{b\}(k)$.
4. Margin update: Update the margin vector: $\backslash mathbf\{b\}(k+1)\; =\; \backslash mathbf\{b\}(k)\; +\; 2\backslash eta\_k\; (\backslash mathbf\{e\}(k)\; +\; |\backslash mathbf\{e\}(k)|)$ where $\backslash eta\_k$ is a positive learning rate parameter, and $|\backslash mathbf\{e\}(k)|$ denotes the element-wise absolute value.
5. Weight calculation: Compute the weight vector using the pseudoinverse: $\backslash mathbf\{w\}(k+1)\; =\; \backslash mathbf\{Y\}^+\; \backslash mathbf\{b\}(k+1)$.
6. Convergence check: If $||\backslash mathbf\{e\}(k)||\; \backslash le\; \backslash theta$ for some predetermined threshold $\backslash theta$ (close to zero), then return $\backslash mathbf\{b\}(k+1),\; \backslash mathbf\{w\}(k+1)$.
7. if $\backslash mathbf\{e\}(k)\; \backslash le\; \backslash mathbf\{0\}$ (all components non-positive), return "Samples not separable.".
8. Return "Algorithm failed to converge in time.".

• If the training data is linearly separable, the algorithm converges to a solution (where $\backslash mathbf\{e\}(k)\; =\; \backslash mathbf\{0\}$) in a finite number of iterations.
• If the data is not linearly separable, the algorithm may or may not ever reach the point where $\backslash mathbf\{e\}(k)\; =\; \backslash mathbf\{0\}$. However, if it does happen that $\backslash mathbf\{e\}(k)\; \backslash le\; \backslash mathbf\{0\}$ at some iteration, this proves non-separability.
• The convergence rate depends on the choice of the learning rate parameter $\backslash rho$ and the degree of linear separability of the data.

• Perceptron algorithm: Both seek linear separators. The perceptron updates weights incrementally based on individual misclassified samples, while Ho–Kashyap is a batch method that processes all samples to compute the pseudoinverse and updates based on an overall error vector.
• Linear discriminant analysis (LDA): LDA assumes underlying Gaussian distributions with equal covariances for the classes and derives the decision boundary from these statistical assumptions. Ho–Kashyap makes no explicit distributional assumptions and instead tries to solve a system of linear inequalities directly.
• Support vector machines (SVM): For linearly separable data, SVMs aim to find the maximum-margin hyperplane. The Ho–Kashyap algorithm finds a separating hyperplane but not necessarily the one with the maximum margin. If the data is not separable, soft-margin SVMs allow for some misclassifications by optimizing a trade-off between margin size and misclassification penalty, while Ho–Kashyap provides a least-squares solution.

Modified Ho–Kashyap algorithm changes weight calculation step $\backslash mathbf\{w\}(k+1)\; =\; \backslash mathbf\{Y\}^+\; \backslash mathbf\{b\}(k+1)$ to $\backslash mathbf\{w\}(k+1)\; =\; \backslash mathbf\{w\}(k)\; +\; \backslash eta\_k\; \backslash mathbf\{Y\}^+\; |\backslash mathbf\{e\}(k)|$.

Kernel Ho–Kashyap algorithm: Applies kernel methods (the "kernel trick") to the Ho–Kashyap framework to enable non-linear classification by implicitly mapping data to a higher-dimensional feature space.{{cite journal |last=Łęski |first=Jacek |date=2004 |title=Kernel Ho–Kashyap classifier with generalization control. |journal=International Journal of Applied Mathematics and Computer Science |volume=14 |issue=1 |pages=53–61}}

• Linear classifier
• Perceptron
• Pattern recognition
• Machine learning
• Support vector machine
• Moore–Penrose pseudoinverse

• {{cite book |last1=Duda |first1=R. O. |last2=Hart |first2=P. E. |last3=Stork |first3=D. G. |year=2001 |title=Pattern Classification |edition=2nd |chapter=5.9. The Ho–Kashyap Procedures |publisher=Wiley-Interscience |isbn=978-0-471-05669-0}}
• {{cite book |last1=Bishop |first1=C. M. |year=2006 |title=Pattern Recognition and Machine Learning |publisher=Springer |isbn=978-0-387-31073-2}}
• {{cite book |last1=Theodoridis |first1=S. |last2=Koutroumbas |first2=K. |year=2008 |title=Pattern Recognition |edition=4th |publisher=Academic Press |isbn=978-1-59749-272-0}}

Category:Classification algorithms

Category:Machine learning algorithms

Category:Statistical classification