Diferença entre regressão Primimal, Dual e Kernel Ridge

18

Qual é a diferença entre Regressão Primal , Dual e Kernel Ridge? As pessoas estão usando os três, e por causa da notação diferente que todo mundo usa em diferentes fontes é difícil para mim seguir.

Então, alguém pode me dizer em palavras simples qual é a diferença entre esses três? Além disso, quais poderiam ser algumas vantagens ou desvantagens de cada um e qual pode ser sua complexidade?

Jim Blum
fonte

Respostas:

39

Resposta curta: não há diferença entre Primal e Dual - é apenas a maneira de chegar à solução. A regressão do cume do kernel é essencialmente a mesma que a regressão do cume usual, mas usa o truque do kernel para se tornar não linear.

Regressão linear

Antes de tudo, uma regressão linear de mínimos quadrados usual tenta ajustar uma linha reta ao conjunto de pontos de dados de maneira que a soma dos erros ao quadrado seja mínima.

insira a descrição da imagem aqui

Nós parametrizar a melhor linha de ajuste com w e para cada ponto de dados (xi,yi) queremos wTxiyi . Seja ei=yiwTxi o erro - a distância entre os valores previstos e os verdadeiros. Assim, nosso objetivo é minimizar a soma dos erros quadrados ei2=e2=Xwy2 , onde X=[x1x2xn]- uma matriz de dados, com cadaxisendo uma linha, ey=(y1, ... ,yn)um vector com todosyi 's.

Assim, o objetivo é minwXwy2 , e a solução é w=(XTX)1XTy (conhecida como "Equação Normal").

Para um novo ponto de dados invisível x podemos prever o seu valor alvo y como y = w t x .y^y^=wTx

Regressão de Ridge

Quando existem muitas variáveis ​​correlacionadas nos modelos de regressão linear, os coeficientes w podem se tornar mal determinados e ter muita variação. Uma das soluções para este problema é restringir pesosw para que eles não excedam algum orçamentoC . Isso é equivalente a usarL2 -regularization, também conhecido como "peso decaimento": ele vai diminuir a variância ao custo de, por vezes, faltando os resultados correctos (isto é, através da introdução de alguns polarização).

O objetivo agora se torna minwXwy2+λw2 , comλ sendo a parâmetro de regularização. Analisando a matemática, obtemos a seguinte solução:w=(XTX+λI)1XTy . É muito semelhante à regressão linear de costume, mas aqui vamos adicionarλ a cada elemento diagonal deXTX .

Observe que podemos reescrever w como w=XT(XXT+λI)1y (vejaaquipara detalhes). Para um novo ponto de dados invisívelx podemos prever o seu valor alvo y como y = x T w = xy^y^=xTw=xTXT(XXT+λI)1y . Sejaα=(XXT+λI)1y . Em seguida, y = X T X T α = n Σ i = 1y^=xTXTα=i=1nαixTxi .

Regressão de Ridge Dual Form

Podemos ter uma visão diferente de nosso objetivo - e definir o seguinte problema quadrático do programa:

mine,wi=1nei2 stei=yiwTxi parai=1..n e w2C .

É o mesmo objetivo, mas expresso de maneira um pouco diferente, e aqui a restrição sobre o tamanho de w é explícita. Para resolver isto, nós definimos o Lagrangeanos Lp(w,e;C) - esta é a forma primitiva que contém variáveis primárias w e e . Em seguida, otimizamos o wrt e e w . Para obter a formulação dupla, colocamos e e w volta em Lp(w,e;C) .

Assim, Lp(w,e;C)=e2+βT(yXwe)λ(w2C) . Ao tomar derivados wrtw e e , obtemose=12βew=12λXTβ. Ao deixarα=12λβ, e colocandoeewvolta paraLp(w,e;C), obtemos dupla de LagrangeLd(α,λ;C)=λ2α2+2λαTyλXTαλC . Se tomarmos uma derivada wrtα , obtemosα=(XXTλI)1y - a mesma resposta que para a regressão usual de Kernel Ridge. Não há necessidade de usar uma derivada wrtλ - depende deC , que é um parâmetro de regularização - e também fazλ parâmetro de regularização.

Em seguida, coloque α na solução da forma primária para w e obtenha w=12λXTβ=XTα. Assim, a forma dupla fornece a mesma solução que a Regressão de Ridge usual, e é apenas uma maneira diferente de chegar à mesma solução.

Regressão de Kernel Ridge

Os kernels são usados ​​para calcular o produto interno de dois vetores em algum espaço de recurso sem sequer visitá-lo. Podemos visualizar um kernel k como k(x1,x2)=ϕ(x1)Tϕ(x2) , embora não saibamos o que ϕ() - apenas sabemos que ele existe. Existem muitos kernels, por exemplo, RBF, Polynonial, etc.

k(x1,x2)=ϕ(x1)Tϕ(x2)Φ(X)ϕ(xi)Φ(X)=[ϕ(x1)ϕ(x2)ϕ(xn)]

Now we can just take the solution for Ridge Regression and replace every X with Φ(X): w=Φ(X)T(Φ(X)Φ(X)T+λI)1y. For a new unseen data point x we predict its target value y^ as y^=ϕ(x)TΦ(X)T(Φ(X)Φ(X)T+λI)1y.

First, we can replace Φ(X)Φ(X)T by a matrix K, calculated as (K)ij=k(xi,xj). Then, ϕ(x)TΦ(X)T is i=1nϕ(x)Tϕ(xi)=i=1nk(x,xj). So here we managed to express every dot product of the problem in terms of kernels.

Finally, by letting α=(K+λI)1y (as previously), we obtain y^=i=1nαik(x,xj)

References

Alexey Grigorev
fonte
1
I am impressed by the well-organized discussion. However, your early reference to "outliers" confused me. It appears the weights w apply to the variables rather than the cases, so how exactly would ridge regression help make the solution robust to outlying cases, as suggested by the illustration?
whuber
Excellent answer, Alexey (though I wouldn't call it "simple words")! +1 with no questions asked. You like to write in LaTeX, don't you?
Aleksandr Blekh
2
I suspect you might be confusing some basic things here. AFAIK, ridge regression is neither a response to nor a way of coping with "noisy observations." OLS already does that. Ridge regression is a tool used to cope with near-collinearity among regressors. Those phenomena are completely different from noise in the dependent variable.
whuber
1
+1 whuber. Alexey you are right it is overfitting -ie too many parameters for the available data - not really noise. [ and add enough dimensions for fixed sample size and 'any' data set becomes collinear]. So a better 2-d picture for RR would be all the points clustered around (0,1) with a single point at (1,0) ['justifying' the slope parameter]. See ESL fig 3.9,page 67 web.stanford.edu/~hastie/local.ftp/Springer/OLD/…. also look at primal cost function: to increase weight by 1 unit, error must decrease by 1/λ unit
seanv507
1
I believe you meant add λ to diagonal elements of XTX not subtract(?) in the ridge regression section. I applied the edit.
Heteroskedastic Jim