<commit_before>---
layout: post
title: "核方法"
date: 2017-11-25
excerpt: "核方法"
tags: [Machine Learning, SVM]
comments: true
---

将低维数据映射到高维数据对分类可能是有益的，例如：

<figure >
    <img src="{{ site.url }}/posts/kernel-methods/feature-mapping.png">
</figure>

原SVM的优化问题为：

\\[\textrm{min }\frac{1}{2}\|w\|^2 + C\sum{\xi_i}\\]
\\[ \textrm{ s.t. } y_i(w^T x_i + b) \geq 1 - \xi_i, \xi_i \geq 0, \forall i\\]

设\\(\psi(x)\\)将\\(x\\)映射为另一个向量，特征映射之后的决策函数变为\\(h'(x) = \hat{w} \psi(x) + \hat{b}\\)，则优化问题变为：

\\[\textrm{min }\frac{1}{2}\|\hat{w}\|^2 + C\sum{\xi_i}\\]
\\[ \textrm{ s.t. } y_i(\hat{w}^T \psi(x_i) + \hat{b}) \geq 1 - \xi_i, \xi_i \geq 0, \forall i\\]

对偶问题变为：

\\[\textrm{min } Q(\alpha)=\frac{1}{2}\sum\sum{\alpha_i \alpha_j y_i y_j \psi(x_i)^T \psi(x_j)} - \sum{\alpha_i} \\]
\\[\textrm{  s.t. } \sum{\alpha_i y_i}=0, C \geq \alpha_i \geq 0, \forall i\\]

定义核函数：\\(\kappa(x_i, x_j) = \psi(x_i)^T \psi(x_j)\\)

定义正定核函数：对于\\(K_{ij} = \kappa(x_i, x_j)\\), 若\\(K_{ij} = K_{ji}\\)且\\(K\\)是半正定的（\\(\forall \theta, \theta^T K \theta \geq 0\\)），则称\\(\kappa\\)是正定核函数。

Mercer's Condition: 若\\(\kappa\\)是正定核函数，则一定能找到一个Hilbert空间\\(H\\)和特征映射函数\\(\psi\\)，使得\\(\kappa(x_i, x_j)=\langle \psi(x_i), \psi(x_j) \rangle_{H}\\)


>常用核函数：
* 多项式核，\\(\kappa(x_i, x_j) = (1 + \langle x_i, x_j \rangle)^m, m \in \mathbb{N}\\)
* 高斯核，\\(\kappa(x_i, x_j) = \exp(-\frac{\|x_i - x_j\|^2}{2 \sigma^2})\\)
* 核函数的线性组合，\\(\kappa(x_i, x_j) = \sum_{p=1}^m {\gamma_p \kappa_p(x_i, x_j)}, \gamma_p \geq 0\\)



此时的对偶问题记作：

\\[\min_\alpha \frac{1}{2}(\alpha \odot y)^T K (\alpha \odot y) + \alpha^T e\\]
\\[\textrm{s.t. } \alpha^T y = 0, \alpha \geq 0\\]

其中，\\(\alpha\\)是拉格朗日乘子，\\(y = [y_1, y_2, ..., y_n]^T\\)，\\(K_{ij} = \kappa(x_i, x_j)\\)，\\(e=[1, 1, ..., 1]^T\\) <commit_msg>Add content<commit_after>---
layout: post
title: "核方法"
date: 2017-11-25
excerpt: "核方法"
tags: [Machine Learning, SVM]
comments: true
---

将低维数据映射到高维数据对分类可能是有益的，例如：

<figure >
    <img src="{{ site.url }}/posts/kernel-methods/feature-mapping.png">
</figure>

原SVM的优化问题为：

\\[\textrm{min }\frac{1}{2}\|w\|^2 + C\sum{\xi_i}\\]
\\[ \textrm{ s.t. } y_i(w^T x_i + b) \geq 1 - \xi_i, \xi_i \geq 0, \forall i\\]

设\\(\psi(x)\\)将\\(x\\)映射为另一个向量，特征映射之后的决策函数变为\\(h'(x) = \hat{w} \psi(x) + \hat{b}\\)，则优化问题变为：

\\[\textrm{min }\frac{1}{2}\|\hat{w}\|^2 + C\sum{\xi_i}\\]
\\[ \textrm{ s.t. } y_i(\hat{w}^T \psi(x_i) + \hat{b}) \geq 1 - \xi_i, \xi_i \geq 0, \forall i\\]

对偶问题变为：

\\[\textrm{min } Q(\alpha)=\frac{1}{2}\sum\sum{\alpha_i \alpha_j y_i y_j \psi(x_i)^T \psi(x_j)} - \sum{\alpha_i} \\]
\\[\textrm{  s.t. } \sum{\alpha_i y_i}=0, C \geq \alpha_i \geq 0, \forall i\\]

定义核函数：\\(\kappa(x_i, x_j) = \psi(x_i)^T \psi(x_j)\\)

定义正定核函数：对于\\(K_{ij} = \kappa(x_i, x_j)\\), 若\\(K_{ij} = K_{ji}\\)且\\(K\\)是半正定的（\\(\forall \theta, \theta^T K \theta \geq 0\\)），则称\\(\kappa\\)是正定核函数。

Mercer's Condition: 若\\(\kappa\\)是正定核函数，则一定能找到一个Hilbert空间\\(H\\)和特征映射函数\\(\psi\\)，使得\\(\kappa(x_i, x_j)=\langle \psi(x_i), \psi(x_j) \rangle_{H}\\)


>常用核函数：
* 多项式核，\\(\kappa(x_i, x_j) = (1 + \langle x_i, x_j \rangle)^m, m \in \mathbb{N}\\)
* 高斯核，\\(\kappa(x_i, x_j) = \exp(-\frac{\|x_i - x_j\|^2}{2 \sigma^2})\\)
* 核函数的线性组合，\\(\kappa(x_i, x_j) = \sum_{p=1}^m {\gamma_p \kappa_p(x_i, x_j)}, \gamma_p \geq 0\\)



此时的对偶问题记作：

\\[\min_\alpha \frac{1}{2}(\alpha \odot y)^T K (\alpha \odot y) + \alpha^T e\\]
\\[\textrm{s.t. } \alpha^T y = 0, \alpha \geq 0\\]

其中，\\(\alpha\\)是拉格朗日乘子，\\(y = [y_1, y_2, ..., y_n]^T\\)，\\(K_{ij} = \kappa(x_i, x_j)\\)，\\(e=[1, 1, ..., 1]^T\\) 

如果加了一些内容呢？ 
{'fraction_non_alphanumeric': 0.31918554631488383, 'fraction_numerical': 0.021795239460854602, 'mean_word_length': 2.80370774263904, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5261192', 'n_tokens_mistral': 2046, 'n_tokens_neox': 2096, 'n_words': 306}