8.1 Linear Classifier

8.1.1 A Theoretical Solution

• Limitations of Bayesian Methods: Bayesian methods (covered in Chapter 7) rely on accurate probability models. However, in real-world scenarios, data distributions are often unknown. Accurate model estimation requires a large number of training samples, which may not always be available, especially with high-dimensional data (like multimedia).

• Alternative Approach: Discriminant Functions: Instead of modeling the entire data distribution, we can assume a functional form for the decision boundary between classes. We then estimate the parameters of this function using training data. Linear classifiers are one type of such an approach.

• Linear Discriminant Function Formulation:

  • Let $x=(x_1,x_2,...,x_n)$ be an $n$-dimensional feature vector representing the data.

  • A linear discriminant function is defined as: $f(x)=w_0+w_1{x}_1+w_2{x}_2+...+w_n{x}_n$ (8.1) where:

    • $x_i$ are the variables (features).
    • $w_i$ are the coefficients or weights.

  • Letting $x_0=1$, the function can be rewritten as: $f(x)={\sum }_{j=0}^n{w}_j{x}_j$ (8.2)

• Geometric Interpretation:

  • The equation $f(x)=0$ represents a hyperplane in $n$-dimensional space. This hyperplane acts as the decision boundary.

  • Classification Criterion: A sample data point with feature vector $x$ is classified as follows:

    $$x\in \{\begin{array}{ll}\text{class 1}& \text{if }f(x)>0\\ \text{class 2}& \text{if }f(x)<0\end{array}$$

• Finding the Weights (Theoretical Solution):

  • Goal: Find the weights $w_0,w_1,w_2,...,w_n$ that minimize misclassifications in the training set.

  • Classical Approach: Solve a system of linear equations.

  • Requirement: For $n$-dimensional data, you need $n+1$ linear equations (or samples) to solve for the $n+1$ weights.

  • Let $d_i$ represent the class label: * $d_i=1$ (or $d_i>0$) for class 1. * $d_i=-1$ (or $d_i<0$) for class 2. *Given $n+1$ training sample. $(x_i,d_i)$. Where, $x_i=(x_{i1},x_{i2},...,x_{in})$, $i=1,2,...,n+1$

  • System of Equations: Substituting each training sample $x_i$ into equation (8.2), we get $n+1$ equations: ${\sum }_{j=0}^n{w}_j{x}_{ij}=d_i,i=1,2,...,n+1$ (8.3)

  • Matrix Form: Equation (8.3) can be expressed in matrix form:

    $$\left[\begin{array}{ccccc}1& x_{11}& x_{12}& \dots & x_{1n}\\ 1& x_{21}& x_{22}& \dots & x_{2n}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& x_{n1}& x_{n2}& \dots & x_{nn}\\ 1& x_{n+1,1}& x_{n+1,2}& \dots & x_{n+1,n}\end{array}\right]\left[\begin{array}{c}{w}_0\\ w_1\\ w_2\\ ⋮\\ w_n\end{array}\right]=\left[\begin{array}{c}{d}_1\\ d_2\\ ⋮\\ d_n\\ d_{n+1}\end{array}\right]$$

    (8.4)

  • Compact Matrix Notation: $X{w}^T=d^T$

    • $w^T$ and $d^T$ are the transposes of $w$ and $d$, respectively.

  • Solution: The solution for $w$ is: $w^T=X^{-1}{d}^T$ (8.5)

8.1.2 An Optimal Solution

• Limitations of the Theoretical Solution: The solution in 8.1.1 is based on only $n+1$ samples and is therefore not optimal for the entire training set.

• Optimal Solution Goal: Minimize the squared errors of $f(x)$ over the entire training dataset of $N$ data points $(x_i,d_i)$. Where, $x_i=(x_{i1},x_{i2},...,x_{in})$, $i=1,2,...,N$

• Total Squared Error: $E={\sum }_{i=0}^{N-1}(f(x_i)-d_i{)}^2$ $E={\sum }_{i=0}^{N-1}{\left({\sum }_{j=0}^n{w}_j{x}_{ij}-d_i\right)}^2$ (8.6)

• Minimization: Take the partial derivative of $E$ with respect to each $w_k$ ($k=0,1,2,...,n$) and set it to zero: $\frac{\partial E}{\partial w_k}=0$. This gives $n+1$ linear equations:

  ${\sum }_{i=0}^{N-1}{x}_{ik}\left({\sum }_{j=0}^n{w}_j{x}_{ij}-d_i\right)=0,k=0,1,2,...,n$ (8.7)

• Equivalent Form: ${\sum }_{j=0}^n{w}_j\left({\sum }_{i=0}^{N-1}{x}_{ik}{x}_{ij}\right)={\sum }_{i=0}^{N-1}{x}_{ik}{d}_i,k=0,1,2,...,n$ (8.8)

• Solving for Weights: Solve the $n+1$ linear equations in (8.8) using the same method as in (8.3). This results in an optimal hyperplane.

• Key Differences from (8.3):

  • $x_{ij}$ is replaced by ${\sum }_{i=0}^{N-1}{x}_{ik}{x}_{ij}$.
  • $d_i$ is replaced by ${\sum }_{i=0}^{N-1}{x}_{ik}{d}_i$.

• Solution in Matrix Form: $w^T=(X^{T}X{)}^{-1}(X^T{d}^T)$ (8.8a) Where $X$ is the $N\times (n+1)$ matrix representing the $N$ data, and d is a $1\times N$ vector representing the class values of the $N$ data.

8.1.3 A Suboptimal Solution

• Limitations of the Optimal Solution (8.8): While (8.8) is more optimal than (8.5), it involves processing very large matrices, which is computationally expensive and undesirable, especially for high-dimensional multimedia data.

• Iterative Optimization: An alternative is to use an iterative optimization algorithm to find a suboptimal solution to (8.2). This avoids large matrix operations.

• Error-Driven Weight Adaptation: A common practice is a trial-and-error technique, adjusting the weights based on misclassifications.

• Iterative Procedure:

  1. Initialization: Initialize the weights $w_0,w_1,w_2,...,w_n$ with small random values.
  2. Next Training Sample: Take the next training sample $\{x,d\}=\{(x_1,x_2,...,x_n),d\}$, where $d=1$ or $-1$.
  3. Compute $f(x)$: $f(x)=w_0+w_1{x}_1+w_2{x}_2+...+w_n{x}_n$.
  4. Update Weights (if misclassified):
     • If $f(x)\ne d$ (a misclassification), update the weights:
       • $w_0\leftarrow w_0+cdk$
       • $w_j\leftarrow w_j+cd{x}_j$, for $j=1,2,...,m$.
       • $k$ and $c$ are positive constants.
  5. Repeat: Repeat steps 2-4 for all remaining training samples, until all samples are correctly classified or the weights stop changing.

• Explanation of Weight Update:

  • Let $f_{new}$ be the updated value and $f_{old}$ be the old value of $f(x)$.

  • Since $k$, $c$, and $x_j$ are all positive:

    • If $d=1$, all $w_j$ become larger.
    • If $d=-1$, all $w_j$ become smaller.

  • This means the decision function is updated as follows:

    $$\{\begin{array}{ll}{f}_{new}>f_{old}& \text{if }d=1\\ f_{new}<f_{old}& \text{if }d=-1\end{array}$$

  • Therefore, the hyperplane $f(x)$ moves in the correct direction with the updated weights until the misclassified sample is on the correct side.