Using kernels with Fisher's linear discriminant analysis

Question

I am a bit stuck implementing the Kernel Fisher Discriminant.

$$ J(\mathbf{w}) = \frac{\mathbf{w}^{\text{T}}\mathbf{S}_B^{\phi}\mathbf{w}}{\mathbf{w}^{\text{T}}\mathbf{S}_W^{\phi}\mathbf{w}} $$ $$ J(\mathbf{\alpha}) = \frac{\mathbf{\alpha}^{\text{T}}\mathbf{M}\mathbf{\alpha}}{\mathbf{\alpha}^{\text{T}}\mathbf{N}\mathbf{\alpha}}. $$

As far as I understand what I have to do is calculate the $\alpha$ which depends on $\mathbf{M}$ and $\mathbf{N}$

$$\mathbf{\alpha} = \mathbf{N}^{-1}(\mathbf{M}_2- \mathbf{M}_1).$$

In the case of $\mathbf{N}$, $\mathbf{N} = \displaystyle \sum_{j=1,2}\mathbf{K}_j(\mathbf{I}-\mathbf{1}_{l_j})\mathbf{K}_j^{\text{T}}$, with the $n^{\text{th}}, m^{\text{th}}$ component of $\mathbf{K}_j$ defined as $k(\mathbf{x}_n,\mathbf{x}_m^j)$ where $\mathbf{x_n}$ is all the observations and $\mathbf{x_m^j}$ is all the observations that belong to the class $j$

In the case of $\mathbf{M}_i$, $ (\mathbf{M}_i)_j = \frac{1}{l_i}\sum_{k=1}^{l_i}k(\mathbf{x}_j,\mathbf{x}_k^i).$ where $\mathbf{x_j}$ is all the observations and $\mathbf{x_k^i}$ is all the observations that belong to the class $i$.

Assuming that I understand that part, the big problem that I have is when I would like to use the $\alpha$ to assign a new observation in some class.

$$y(\mathbf{x}) = (\mathbf{w}\cdot\phi(\mathbf{x})) = \sum_{i=1}^l\alpha_ik(\mathbf{x}_i,\mathbf{x}).$$

However, when I try to implement this part, $\alpha$ has the dimensions of the total observations and as $x_i$ is a new observation the size of this vector is in the previous space and I really don't understand this part.

There are something that I am misunderstanding? How I have to use the $\alpha$ or $\mathbf{x}$?

What is the real meaning of $\mathbf{x}$ because I believe it has sometimes that has different meanings?

Answer 1

It doesn't matter that the dimensions of $\alpha$ and $x$ are different, because they never come into contact directly. Your new $x$ only enters the equation for $y(x)$ in the terms $k(x_i, x)$ (here the left argument is a point in the training dataset, and the right argument is a point you're trying to classify). Since the left argument ranges over all points in the training dataset, there's one term $k(x_i, x)$ for each observation, just like there's one $\alpha_i$ for each observation (as you noted). Here's how you would compute this in pseudocode:

def classify(kernel, train_data, alpha, new_x):
    y = 0
    for i in 1:length(train_data)
        y += alpha[i] + kernel(train_data[i], new_x)
    return y

As you can see, there are no dimensionality mismatches--alpha and train_data have the same length, as do new_x and train_data[i].