Question

You are given 6 training examples for a binary classification problem as follows:

Answer 1

Answer:To simplify the discussion, we will only consider two-class classifiers in this section and define a linear classifier as a two-class classifier that decides class membership by comparing a linear combination of the features to a threshold.

Figure 14.8: There are an infinite number of hyperplanes that separate two linearly separable classes.

\includegraphics[width=6cm]{vclassline.eps}

In two dimensions, a linear classifier is a line. Five examples are shown in Figure 14.8 . These lines have the functional form $w_1x_1+w_2x_2=b$. The classification rule of a linear classifier is to assign a document to $c$ if $w_1x_1+w_2x_2>b$ and to $\overline{c}$ if $w_1x_1+w_2x_2\leq b$. Here, $(x_1, x_2)^{T}$ is the two-dimensional vector representation of the document and $(w_1, w_2)^{T}$ is the parameter vector that defines (together with $b$) the decision boundary. An alternative geometric interpretation of a linear classifier is provided in Figure 15.7 (page [*]).

We can generalize this 2D linear classifier to higher dimensions by defining a hyperplane as we did in Equation 140, repeated here as Equation 144:

\begin{displaymath}

\vec{w}^{T}\vec{x} = b

\end{displaymath} (144)

The assignment criterion then is: assign to $c$ if $\vec{w}^{T}\vec{x} > b$ and to $\overline{c}$ if $\vec{w}^{T}\vec{x} \leq b$. We call a hyperplane that we use as a linear classifier a decision hyperplane .

Figure 14.9: Linear classification algorithm.

\begin{figure}\begin{algorithm}{ApplyLinearClassifier}{\vec{w},b,\vec{x}}

score ...

...in{IF}{score>b}

\RETURN{1}

\ELSE

\RETURN{0}

\end{IF}\end{algorithm}

\end{figure}

The corresponding algorithm for linear classification in $M$ dimensions is shown in Figure 14.9 . Linear classification at first seems trivial given the simplicity of this algorithm. However, the difficulty is in training the linear classifier, that is, in determining the parameters $\vec{w}$ and $b$ based on the training set.

Explanation: