1
$\begingroup$

I am trying to derive kernel trick from linear regression, and I have a mistake in the very end, which leads to an expression too simple.

Basic linear regression

For a basic linear regression (with no regularisation for simplicity), let ${\bf x_i}$ be row-vectors of data of length $p$ (for instance, each coordinate $x_{i,j}$ might be the value of expression of gene $j$ in patient $i$).

Let the corresponding data matrix $X = \begin{pmatrix} {\bf x_1} \\ {\bf x_2} \\ ... \\ {\bf x_n} \end{pmatrix}$ be $n$ x $p$ matrix of data (e.g. n - number of patients, p - number of genes), ${\bf w}$ be the vector of weights (e.g. weight $w_j$ is the contribution of expression of gene $j$ to a patient's body mass index).

In case of a regular regression we would be trying to estimate body mass index of patient $i$ as:

$h({\bf x_i}) = {\bf x_i} {\bf w}$

Fitting this to measurements vector ${\bf y}^T = (y_1, ..., y_n)$ would imply minimization of sum of square errors:

$\hat{\bf w} = \underset{\bf w}{\arg \min} ({\bf y} - X {\bf w })^{T} ({\bf y} - X {\bf w})$ which results in:

${\hat{\bf w}} = (X^T X)^{-1} \cdot X^T{\bf y}$

Kernel regression

Now, we replace $n$ x $p$ matrix $X$ of basic features with an $n$ x $P$ matrix $\Phi = \begin{pmatrix} {\bf \varphi(x_1)} \\ {\bf \varphi(x_2)} \\ ... \\ {\bf \varphi(x_n)} \end{pmatrix}$ of feature maps, where, again, each row $\bf \varphi(x_i)$ corresponds to a single patient, but now has a different, possibly infinite, length $P$ instead of $p$.

Accordingly, our weights vector $\bf w$ is now going to be $P$-vector instead of $p$-vector.

Hence, our estimate function of BMI $h({\bf \varphi({\bf x_i})}) = {\bf \varphi(x_i)} \cdot {\bf w} = {\bf \varphi(x_i)} \cdot (\Phi^T \Phi)^{-1} \cdot \Phi^T{\bf y}$.

Now we change the representation of our pseudo-inverse matrix: $(\Phi^T \Phi)^{-1} \Phi^T = \Phi^T (\Phi \Phi^T)^{-1}$.

This results in a different representation of $h({\bf \varphi({\bf x_i})})$:

$h({\bf \varphi({\bf x_i})}) = {\bf \varphi(x_i)} \cdot \Phi^T (\Phi \Phi^T)^{-1} {\bf y}$

My question

What I don't quite understand here is the following.

Denote matrix $\Phi \Phi^T = K$.

Consider expression $h({\bf \varphi({\bf x_i})}) = {\bf \varphi(x_i)} \cdot \Phi^T (\Phi \Phi^T)^{-1} {\bf y}$.

The multiplier ${\bf \phi(x_i)}\Phi^T$ is essentially the i-th row of our matrix $K$.

The other multiplier is $(\Phi \Phi^T)^{-1} {\bf y} = K^{-1} y$.

What happens, if we multiply i-th row of a matrix $K$ by its inverse? We should get a one-hot vector $(0, 0, ..., \underbrace{1}_{i-th position}, ..., 0)$, right?

So I assume $h({\bf \varphi({\bf x_i})}) = (0, 0, ..., \underbrace{1}_{i-th position}, ..., 0) \cdot {\bf y} = y_i$.

I must be wrong somewhere, but I cannot find mistakes in my reasoning.

The correct answer does not allow for such a simplification and instead takes a more general form $h({\bf \varphi({\bf x_i})}) = \sum \limits_{j=1}^n \alpha_j {\bf \phi(x_i)} {\bf \phi(x_j)}$, where vector ${\bf \alpha} = (\Phi \Phi^T)^{-1} {\bf y}$.

$\endgroup$
1
  • $\begingroup$ Cross Validated seems a much more appropriate place to ask this $\endgroup$
    – desertnaut
    Oct 22 '21 at 21:01
0
$\begingroup$

Now we change the representation of our pseudo-inverse matrix $(\Phi^T\Phi)^{-1} \Phi^T = \Phi^T (\Phi \Phi^T)^{-1}$.

The above cannot be done as different representations rely on different assumptions about column rank and row rank and in fact are inequivalent in general.

In particular, when $A$ has linearly independent columns (and thus matrix $A^{*}A$ is invertible), $A^{+}$ can be computed as $A^{+}=\left(A^{*}A\right)^{-1}A^{*}$.

This particular pseudoinverse constitutes a left inverse, since, in this case, $A^{+}A=I$.

When $A$ has linearly independent rows (matrix $AA^{*}$ is invertible), $A^{+}$ can be computed as $A^{+}=A^{*}\left(AA^{*}\right)^{-1}$.

This is a right inverse, as $AA^{+}=I$.

The left and right pseudo-inverses coincide only in special cases (eg when actual matrix $A$ is indeed invertible).

References: Definition of Moore-Penrose Pseudo-Inverse

$\endgroup$
2
  • $\begingroup$ Nicos, thank you for your answer and sorry for my late response. You are right, if $N > p$, $\Phi^T \Phi$ matrix is not full-rank, and cannot be inverted. Moreover, even if $\Phi^T \Phi$ is full rank, $\Phi \Phi^T$ might not be. $\endgroup$ Oct 28 '21 at 6:20
  • 1
    $\begingroup$ Glad to be of help $\endgroup$
    – Nikos M.
    Oct 28 '21 at 8:36
1
$\begingroup$

After additional research I found out that my general direction was right, but required a more elaborate approach.

Indeed, if $P \gg n$, $\Phi^T \Phi$ is a non-full rank matrix with lots of zero eigenvalues, thus its inverse $(\Phi^T \Phi)^{-1}$ cannot exist.

However, in order to overcome this problem, we can add a Tikhonov regularisation term: $(\lambda I + \Phi^T \Phi)$, effectively increasing all the matrix eigenvalues by $\lambda$ and thus making it invertible.

After that we apply Woodbury-Sherman-Morrison formula to invert the regularized matrix and express the solution of kernel ridge regression through kernel matrix $K$:

$h(\varphi({\bf x_i})) = \varphi({\bf x_i}) \cdot (\lambda I + \Phi^T \Phi)^{-1} \Phi^T \cdot {\bf y} = \varphi({\bf x_i}) \cdot \Phi^T (\Phi \Phi^T + \lambda I)^{-1} \cdot {\bf y} = $

$= K_i \cdot (K + \lambda I)^{-1} \cdot {\bf y}$

So, yes, if not for the regularisation term, this formula would've just selected $y_i$ from outputs vector as an estimate of $h(\varphi(x_i))$. However, addition of regularisation to the kernel matrix complicates this expression.

Anyway, we end up with an explicit solution of KRR through kernel matrix $K$ and regression outputs ${\bf y}$ and through mathematical magic avoid (possibly infinite-dimensional) feature space vectors $\varphi({\bf x_i})$.


References:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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