4
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
+50
$\begingroup$

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].

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.