07 - Kernels - lec. 9,10

ucla | CS M146 | 2023-05-01T13:59

---

Table of Contents

• Supplemental
• Lecture
  • Feature Maps (Basis Functions)
    • Gradient descent w/ feature maps
    • Regularization w/ feature maps
  • Representor Theorem
  • Reparametrized Risk
  • Kernel Trick
    • Kernelized Linear Model
    • Kernalized Ridge Regression
  • Valid Kernels
    • Is a Kernel Valid?
    • Mercer’s Theorem
    • Kernel Composition Rules
    • Example: Gaussian Kernel (RBF)
• Discussion
• Resources

Supplemental

• Linear Model regularization review

Lecture

Feature Maps (Basis Functions)

• any function $\varphi :X\to \hat{X}$

• e.g. for features $\text{bm}x\in {\text{R}}^2$, we have a feature map $\varphi :{\text{R}}^2\to {\text{R}}^6$

$\varphi (\text{bm}x)=\varphi ([x_1,x_2])=[1,x_1,x_2,x_1^2,x_2^2,x_1,x_2]$

• with this, we can still use a linear hypothesis class: $h_{\text{bm}\theta }(\text{bm}x)=\text{bm}{\theta }^T\varphi (\text{bm}{x}^{(i)})$

Gradient descent w/ feature maps

• each update requires computing the hypothesis → high dimensions feature maps require more computation

• very expressive feature map (high dimension) tend to overfit → need regularization

Regularization w/ feature maps

• Linear Model regularization review

• for linear models with possible feature maps, we can express them as

Representor Theorem

• used to efficiently train and evaluate expresive feature mapd
• theorem (special case): for any $\lambda >0$, there exists some ral-valued coefficients ${\beta }_i\in \text{R}$ (scalars) such that the minimizer of the regularized loss function is:
• i.e. the optimal gradient for the regularized loss is

$\widehat{\text{bm}\theta }=\sum _{i=1}^n{\beta }_i\varphi (\text{bm}{x}^{(i)})$

${\beta }_i=-\frac{1}{2\lambda n}{L}^{\prime }(\text{bm}{\theta }^T\varphi (\text{bm}{x}^{(i)}),y^{(i)})$

• proof

Reparametrized Risk

• representor theorem allows us to reparametrize the ${\ell }_2$ regularized loss:

$J(\text{bm}\theta )\frac{1}{n}\sum _{i=1}^{n}L(\text{bm}{\theta }^T\varphi (\text{bm}{x}^{(i)}),y^{(i)})+\lambda |\text{bm}\theta {|}_2^2$

• thus, by representor theorem, we can use the minimized gradient into the loss function above to obtaain a reparametriz objective (loss) function w.r.t. $\text{bm}\beta$

• the kernel function can be precomputed for all training instances during training → we only optimize over $\text{bm}\beta$ insteaad of computing th hypothesis (dot product) for each iteration

Kernel Trick

• thus, we can (in some situations) compute the kernel dot product faster than the fature map itself

Kernelized Linear Model

• apply kernel trick: only compute kernel function instad of feature map → kernelized linear models
• thus, given a kernel function on a set of training intances of cardinallity $m$, we can dfine a kernell matrix $K\in {\text{R}}^{m\times m}$

$K_{ij}=k(\text{bm}{x}^{(i)},\text{bm}{x}^{(j)})$

Kernalized Ridge Regression

Valid Kernels

• given a feature map, a kernel function defined as the dot product of the feature map with itself → defines a notion of similrity between the two vectors (data points)
• e.g. $K_{ij}=k(\text{bm}{x}^{(i)},\text{bm}{x}^{(j)})$ shows similarity between $\text{bm}{x}^{(i)}$ and $\text{bm}{x}^{(j)}$
• other form of similarity include: euclidean distance, cosine similarity, any similar kernel function
• but any arbitrary kernel function does NOT imply a feature map

Is a Kernel Valid?

Mercer’s Theorem

• e.g. $k(\text{bm}u,\text{bm}v)=(\text{bm}{u}^T\text{bm}v{)}^2$

Kernel Composition Rules

• algebraic operation on known valid kernels → result in valid kernels

Example: Gaussian Kernel (RBF)

$k(\text{bm}{x}^{(i)},\text{bm}{x}^{(j)})=\exp (-\frac{|\text{bm}{x}^{(i)}-\text{bm}{x}^{(j)}{|}_2^2}{2{\sigma }^2})$

• has. val 1 when $\text{bm}{x}^{(i)}=\text{bm}{x}^{(j)}$
• value falls off to 0 w/ increasing distance
• note: needs feature scaling before using RBF
• $\sigma$ is the bandwidth hyperparameter → determines how much L2 norm affects the kernel

Discussion

Resources

---

📌

**SUMMARY
**