Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Regularization by spectral filtering
open-in-new
<h2 id="notation">Notation</h2> <p>The training set is defined as S = { ( x 1 , y 1 ) , … , ( x n , y n ) } {\displaystyle S=\{(x_{1},y_{1}),\dots ,(x_{n},y_{n})\}} , where X {\displaystyle X} is the n × d {\displaystyle n\times d} input matrix and Y = ( y 1 , … , y n ) {\displaystyle Y=(y_{1},\dots ,y_{n})} is the output vector. Where applicable, the kernel function is denoted by k {\displaystyle k} , and the n × n {\displaystyle n\times n} kernel matrix is denoted by K {\displaystyle K} which has entries K i j = k ( x i , x j ) {\displaystyle K_{ij}=k(x_{i},x_{j})} and H {\displaystyle {\mathcal {H}}} denotes the <a href="/facts/RKHS/VegkYAXb">Reproducing Kernel Hilbert Space</a> (RKHS) with kernel k {\displaystyle k} . The regularization parameter is denoted by λ {\displaystyle \lambda } . </p><p><i>(Note: For g ∈ G {\displaystyle g\in G} and f ∈ F {\displaystyle f\in F} , with G {\displaystyle G} and F {\displaystyle F} being Hilbert spaces, given a linear, continuous operator L {\displaystyle L} , assume that g = L f {\displaystyle g=Lf} holds. In this setting, the direct problem would be to solve for g {\displaystyle g} given f {\displaystyle f} and the inverse problem would be to solve for f {\displaystyle f} given g {\displaystyle g} . If the solution exists, is unique and stable, the inverse problem (i.e. the problem of solving for f {\displaystyle f} ) is well-posed; otherwise, it is ill-posed.) </i> </p> <h2 id="relation-to-the-theory-of-ill-posed-inverse-problems">Relation to the theory of ill-posed inverse problems</h2> <p>The connection between the regularized least squares (RLS) estimation problem (Tikhonov regularization setting) and the theory of ill-posed inverse problems is an example of how spectral regularization algorithms are related to the theory of ill-posed inverse problems. </p><p>The RLS estimator solves min f ∈ H 1 n ∑ i = 1 n ( y i − f ( x i ) ) 2 + λ ‖ f ‖ H 2 {\displaystyle \min _{f\in {\mathcal {H}}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}+\lambda \left\|f\right\|_{\mathcal {H}}^{2}} and the RKHS allows for expressing this RLS estimator as f S λ ( X ) = ∑ i = 1 n c i k ( x , x i ) {\displaystyle f_{S}^{\lambda }(X)=\sum _{i=1}^{n}c_{i}k(x,x_{i})} where ( K + n λ I ) c = Y {\displaystyle (K+n\lambda I)c=Y} with c = ( c 1 , … , c n ) {\displaystyle c=(c_{1},\dots ,c_{n})} .<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> The penalization term is used for controlling smoothness and preventing overfitting. Since the solution of empirical risk minimization min f ∈ H 1 n ∑ i = 1 n ( y i − f ( x i ) ) 2 {\displaystyle \min _{f\in {\mathcal {H}}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}} can be written as f S λ ( X ) = ∑ i = 1 n c i k ( x , x i ) {\displaystyle f_{S}^{\lambda }(X)=\sum _{i=1}^{n}c_{i}k(x,x_{i})} such that K c = Y {\displaystyle Kc=Y} , adding the penalty function amounts to the following change in the system that needs to be solved:<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> { min f ∈ H 1 n ∑ i = 1 n ( y i − f ( x i ) ) 2 → min f ∈ H 1 n ∑ i = 1 n ( y i − f ( x i ) ) 2 + λ ‖ f ‖ H 2 } ≡ { K c = Y → ( K + n λ I ) c = Y } . {\displaystyle \left\{\min _{f\in {\mathcal {H}}}{\frac {1}{n}}\sum _{i=1}^{n}\left(y_{i}-f(x_{i})\right)^{2}\rightarrow \min _{f\in {\mathcal {H}}}{\frac {1}{n}}\sum _{i=1}^{n}\left(y_{i}-f(x_{i})\right)^{2}+\lambda \left\|f\right\|_{\mathcal {H}}^{2}\right\}\equiv {\biggl \{}Kc=Y\rightarrow \left(K+n\lambda I\right)c=Y{\biggr \}}.} </p><p>In this learning setting, the kernel matrix can be decomposed as K = Q Σ Q T {\displaystyle K=Q\Sigma Q^{T}} , with σ = diag ( σ 1 , … , σ n ) , σ 1 ≥ σ 2 ≥ ⋯ ≥ σ n ≥ 0 {\displaystyle \sigma =\operatorname {diag} (\sigma _{1},\dots ,\sigma _{n}),~\sigma _{1}\geq \sigma _{2}\geq \cdots \geq \sigma _{n}\geq 0} and q 1 , … , q n {\displaystyle q_{1},\dots ,q_{n}} are the corresponding eigenvectors. Therefore, in the initial learning setting, the following holds: c = K − 1 Y = Q Σ − 1 Q T Y = ∑ i = 1 n 1 σ i ⟨ q i , Y ⟩ q i . {\displaystyle c=K^{-1}Y=Q\Sigma ^{-1}Q^{T}Y=\sum _{i=1}^{n}{\frac {1}{\sigma _{i}}}\langle q_{i},Y\rangle q_{i}.} </p><p>Thus, for small eigenvalues, even small perturbations in the data can lead to considerable changes in the solution. Hence, the problem is ill-conditioned, and solving this RLS problem amounts to stabilizing a possibly ill-conditioned matrix inversion problem, which is studied in the theory of ill-posed inverse problems; in both problems, a main concern is to deal with the issue of numerical stability. </p> <h2 id="implementation-of-algorithms">Implementation of algorithms</h2> <p>Each algorithm in the class of spectral regularization algorithms is defined by a suitable filter function, denoted here by G λ ( ⋅ ) {\displaystyle G_{\lambda }(\cdot )} . If the Kernel matrix is denoted by K {\displaystyle K} , then λ {\displaystyle \lambda } should control the magnitude of the smaller eigenvalues of G λ ( K ) {\displaystyle G_{\lambda }(K)} . In a filtering setup, the goal is to find estimators f S λ ( X ) := ∑ i = 1 n c i k ( x , x i ) {\displaystyle f_{S}^{\lambda }(X):=\sum _{i=1}^{n}c_{i}k(x,x_{i})} where c = G λ ( K ) Y {\displaystyle c=G_{\lambda }(K)Y} . To do so, a scalar filter function G λ ( σ ) {\displaystyle G_{\lambda }(\sigma )} is defined using the eigen-decomposition of the kernel matrix: G λ ( K ) = Q G λ ( Σ ) Q T , {\displaystyle G_{\lambda }(K)=QG_{\lambda }(\Sigma )Q^{T},} which yields G λ ( K ) Y = ∑ i = 1 n G λ ( σ i ) ⟨ q i , Y ⟩ q i . {\displaystyle G_{\lambda }(K)Y~=~\sum _{i=1}^{n}G_{\lambda }(\sigma _{i})\langle q_{i},Y\rangle q_{i}.} </p><p>Typically, an appropriate filter function should have the following properties:<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> </p> <ol><li>As λ {\displaystyle \lambda } goes to zero, G λ ( σ ) → 1 / σ {\displaystyle G_{\lambda }(\sigma )~\rightarrow ~1/\sigma } .</li> <li>The magnitude of the (smaller) eigenvalues of G λ {\displaystyle G_{\lambda }} is controlled by λ {\displaystyle \lambda } .</li></ol> <p>While the above items give a rough characterization of the general properties of filter functions for all spectral regularization algorithms, the derivation of the filter function (and hence its exact form) varies depending on the specific regularization method that spectral filtering is applied to. </p> <h3>Filter function for Tikhonov regularization</h3> <p>In the Tikhonov regularization setting, the filter function for RLS is described below. As shown in,<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> in this setting, c = ( K + n λ I ) − 1 Y {\displaystyle c=\left(K+n\lambda I\right)^{-1}Y} . Thus, c = ( K + n λ I ) − 1 Y = Q ( Σ + n λ I ) − 1 Q T Y = ∑ i = 1 n 1 σ i + n λ < q i , Y > q i . {\displaystyle c=(K+n\lambda I)^{-1}Y=Q(\Sigma +n\lambda I)^{-1}Q^{T}Y=\sum _{i=1}^{n}{\frac {1}{\sigma _{i}+n\lambda }}<q_{i},Y>q_{i}.} </p><p>The undesired components are filtered out using regularization: </p> <ul><li>If σ ≫ λ n {\displaystyle \sigma \gg \lambda n} , then 1 σ i + n λ ∼ 1 σ i {\displaystyle {\frac {1}{\sigma _{i}+n\lambda }}\sim {\frac {1}{\sigma _{i}}}} .</li> <li>If σ ≪ λ n {\displaystyle \sigma \ll \lambda n} , then 1 σ i + n λ ∼ 1 λ n {\displaystyle {\frac {1}{\sigma _{i}+n\lambda }}\sim {\frac {1}{\lambda n}}} .</li></ul> <p>The filter function for Tikhonov regularization is therefore defined as:<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> G λ ( σ ) = 1 σ + n λ . {\displaystyle G_{\lambda }(\sigma )={\frac {1}{\sigma +n\lambda }}.} </p> <h3>Filter function for Landweber iteration</h3> <p>The idea behind the Landweber iteration is <a href="/facts/Gradient_descent/pFFrek0F">gradient descent</a>:<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> </p> c0 := 0 for <i>i</i> = 1, ..., <i>t</i> − 1 <i>c</i><i>i</i> := <i>c</i><i>i</i>−1 + <i>η</i>(<i>Y</i> − <i>Kc</i><i>i</i>−1) end <p>In this setting, if n {\displaystyle n} is larger than K {\displaystyle K} 's largest eigenvalue, the above iteration converges by choosing η = 2 / n {\displaystyle \eta =2/n} as the step-size:.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> The above iteration is equivalent to minimizing 1 n ‖ Y − K c ‖ 2 2 {\displaystyle {\frac {1}{n}}\left\|Y-Kc\right\|_{2}^{2}} (i.e. the empirical risk) via gradient descent; using induction, it can be proved that at the t {\displaystyle t} -th iteration, the solution is given by <a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> c = η ∑ i = 0 t − 1 ( I − η K ) i Y . {\displaystyle c=\eta \sum _{i=0}^{t-1}\left(I-\eta K\right)^{i}Y.} </p><p>Thus, the appropriate filter function is defined by: G λ ( σ ) = η ∑ i = 0 t − 1 ( I − η σ ) i . {\displaystyle G_{\lambda }(\sigma )=\eta \sum _{i=0}^{t-1}\left(I-\eta \sigma \right)^{i}.} </p><p>It can be shown that this filter function corresponds to a truncated power expansion of K − 1 {\displaystyle K^{-1}} ;<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> to see this, note that the relation ∑ i ≥ 0 x i = 1 / ( 1 − x ) {\displaystyle \sum _{i\geq 0}x^{i}=1/(1-x)} , would still hold if x {\displaystyle x} is replaced by a matrix; thus, if K {\displaystyle K} (the kernel matrix), or rather I − η K {\displaystyle I-\eta K} , is considered, the following holds: K − 1 = η ∑ i = 0 ∞ ( I − η K ) i ∼ η ∑ i = 0 t − 1 ( I − η K ) i . {\displaystyle K^{-1}=\eta \sum _{i=0}^{\infty }\left(I-\eta K\right)^{i}\sim \eta \sum _{i=0}^{t-1}\left(I-\eta K\right)^{i}.} </p><p>In this setting, the number of iterations gives the regularization parameter; roughly speaking, t ∼ 1 / λ {\displaystyle t\sim 1/\lambda } .<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a> If t {\displaystyle t} is large, overfitting may be a concern. If t {\displaystyle t} is small, oversmoothing may be a concern. Thus, choosing an appropriate time for early stopping of the iterations provides a regularization effect. </p> <h3>Filter function for TSVD</h3> <p>In the TSVD setting, given the eigen-decomposition K = Q Σ Q T {\displaystyle K=Q\Sigma Q^{T}} and using a prescribed threshold λ n {\displaystyle \lambda n} , a regularized inverse can be formed for the kernel matrix by discarding all the eigenvalues that are smaller than this threshold.<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a> Thus, the filter function for TSVD can be defined as G λ ( σ ) = { 1 / σ , if σ ≥ λ n 0 , otherwise {\displaystyle G_{\lambda }(\sigma )={\begin{cases}1/\sigma ,&{\text{if }}\sigma \geq \lambda n\\[1ex]0,&{\text{otherwise}}\end{cases}}} </p><p>It can be shown that TSVD is equivalent to the (unsupervised) projection of the data using (kernel) <a href="/facts/Principal_component_analysis/pCbVTqdR">Principal Component Analysis</a> (PCA), and that it is also equivalent to minimizing the empirical risk on the projected data (without regularization).<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a> Note that the number of components kept for the projection is the only free parameter here. </p> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>H. W. Engl, M. Hanke, and A. Neubauer. Regularization of inverse problems. Kluwer, 1996. <a href="/wiki/Heinz_Engl" target="_blank">/wiki/Heinz_Engl</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>L. Lo Gerfo, L. Rosasco, F. Odone, E. De Vito, and A. Verri. Spectral Algorithms for Supervised Learning, Neural Computation, 20(7), 2008. <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>L. Lo Gerfo, L. Rosasco, F. Odone, E. De Vito, and A. Verri. Spectral Algorithms for Supervised Learning, Neural Computation, 20(7), 2008. <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>L. Lo Gerfo, L. Rosasco, F. Odone, E. De Vito, and A. Verri. Spectral Algorithms for Supervised Learning, Neural Computation, 20(7), 2008. <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>P. C. Hansen, J. G. Nagy, and D. P. O'Leary. Deblurring Images: Matrices, Spectra, and Filtering, Fundamentals of Algorithms 3, SIAM, Philadelphia, 2006. <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>L. Rosasco. Lecture 6 of the Lecture Notes for 9.520: Statistical Learning Theory and Applications. Massachusetts Institute of Technology, Fall 2013. Available at https://www.mit.edu/~9.520/fall13/slides/class06/class06_RLSSVM.pdf <a href="https://www.mit.edu/~9.520/fall13/slides/class06/class06_RLSSVM.pdf" target="_blank">https://www.mit.edu/~9.520/fall13/slides/class06/class06_RLSSVM.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>L. Rosasco. Lecture 7 of the Lecture Notes for 9.520: Statistical Learning Theory and Applications. Massachusetts Institute of Technology, Fall 2013. Available at https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf <a href="https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf" target="_blank">https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>L. Rosasco. Lecture 7 of the Lecture Notes for 9.520: Statistical Learning Theory and Applications. Massachusetts Institute of Technology, Fall 2013. Available at https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf <a href="https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf" target="_blank">https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>L. Rosasco. Lecture 6 of the Lecture Notes for 9.520: Statistical Learning Theory and Applications. Massachusetts Institute of Technology, Fall 2013. Available at https://www.mit.edu/~9.520/fall13/slides/class06/class06_RLSSVM.pdf <a href="https://www.mit.edu/~9.520/fall13/slides/class06/class06_RLSSVM.pdf" target="_blank">https://www.mit.edu/~9.520/fall13/slides/class06/class06_RLSSVM.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>L. Rosasco. Lecture 7 of the Lecture Notes for 9.520: Statistical Learning Theory and Applications. Massachusetts Institute of Technology, Fall 2013. Available at https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf <a href="https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf" target="_blank">https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>L. Rosasco. Lecture 7 of the Lecture Notes for 9.520: Statistical Learning Theory and Applications. Massachusetts Institute of Technology, Fall 2013. Available at https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf <a href="https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf" target="_blank">https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>L. Rosasco. Lecture 7 of the Lecture Notes for 9.520: Statistical Learning Theory and Applications. Massachusetts Institute of Technology, Fall 2013. Available at https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf <a href="https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf" target="_blank">https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>L. Rosasco. Lecture 7 of the Lecture Notes for 9.520: Statistical Learning Theory and Applications. Massachusetts Institute of Technology, Fall 2013. Available at https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf <a href="https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf" target="_blank">https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>L. Rosasco. Lecture 7 of the Lecture Notes for 9.520: Statistical Learning Theory and Applications. Massachusetts Institute of Technology, Fall 2013. Available at https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf <a href="https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf" target="_blank">https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>L. Rosasco. Lecture 7 of the Lecture Notes for 9.520: Statistical Learning Theory and Applications. Massachusetts Institute of Technology, Fall 2013. Available at https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf <a href="https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf" target="_blank">https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>L. Rosasco. Lecture 7 of the Lecture Notes for 9.520: Statistical Learning Theory and Applications. Massachusetts Institute of Technology, Fall 2013. Available at https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf <a href="https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf" target="_blank">https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>L. Rosasco. Lecture 7 of the Lecture Notes for 9.520: Statistical Learning Theory and Applications. Massachusetts Institute of Technology, Fall 2013. Available at https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf <a href="https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf" target="_blank">https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> </ol>