正则化

原创 人工智能 机器学习

1. 正则化

在统计机器学习中，我们常常希望将我们的变量或者权重进行一定的约束，假设我们的模型为 y=ax+b，我们希望对 a 加以限制，一般有两种选择：

注意这两种选择中要求的值都是\(a \& b\)，而不是\(x\)，所以对\(a\)进行了约束

约束问题：对 a 的取值加以限制，然后用最小二乘法进行求解，分为等式约束、大小于号约束

constraint form: \((\hat a, \hat b) = \underset {\theta}{\operatorname {arg\,min}} \underset {i}{\sum}(y_{i}-(ax_{i}+b))^2~~s.t~~a^{2} \leqslant c~~or~~g(a)=0\)

其中\(\hat a=\frac{N\sum_{i}x_{i}y_{i}-\sum_{i}x_{i}\sum_{i}y_{i}}{N\sum_{i}x_{i}^{2}-(\sum_{i}x_{i})^{2}}\)，\(\hat b=\frac{\sum_{i}y_{i}-\hat a\sum_{i}x_{i}}{N}\)

无约束问题：同时对最小二乘法和参数 a 进行最小化

Unconstrained form: \((\hat a, \hat b) = \underset {\theta}{\operatorname {arg\,min}} \underset {i}{\sum}(y_{i}-(ax_{i}+b))^2+\lambda a^{2}\)

其中\(\hat a=\frac{N\sum_{i}x_{i}y_{i}-\sum_{i}x_{i}\sum_{i}y_{i}}{N\sum_{i}x_{i}^{2}-(\sum_{i}x_{i})^{2}+N\lambda}\)，\(\hat b=\frac{\sum_{i}y_{i}-\hat a\sum_{i}x_{i}}{N}\)

约束与无约束问题的解区别在于\(\hat a\)的分母是否有\(N\lambda\)，进行正则化的原因是希望引入额外的信息能够帮助解决不适定的问题

2. 约束问题

2.1 转化为广义拉格朗日函数

考虑一个最优化问题，对于任意的\(x\in c\)，原始问题可以表述为
\[ \underset {x}{\operatorname {min}} f(x),~~s.t~~g(x)=0,h(x) \leqslant 0 \]
我们引入广义拉格朗日函数，其中\(\eta \geq 0\)：
\[ L(x, \lambda, \eta) = f(x)+\lambda g(x)+\eta h(x) \]
将上述公式进行转化为\(\Theta_{p}(x)\)，其中\(p\)表示原始问题：

\[ \Theta_{p}(x) = \underset {\lambda, \eta:\eta \geq0}{\operatorname {max}} L(x, \lambda, \eta) = \left\{\begin{matrix} \begin{aligned} f(x), & x statisfied the constraint \\ +\infty, & others \end{aligned} \end{matrix}\right. \]

考虑极小值问题\(\underset {x}{\operatorname {min}} \Theta_{p}(x) =\underset {x}{\operatorname {min}} \underset {\lambda, \eta:\eta \geq0}{\operatorname {max}} L(x, \lambda, \eta)\)，注意此问题与\(\underset {x}{\operatorname {min}} f(x)\)等价，\(\underset {x}{\operatorname {min}} \underset {\lambda, \eta:\eta \geq0}{\operatorname {max}} L(x, \lambda, \eta)\)问题被称为广义拉格朗日函数的极小极大问题，定义其最优解：

\[ p^{*} = \underset {x}{\operatorname {min}} \Theta_{p}(x) \]

2.2 引入对偶解拉格朗日函数

对偶问题：

注意对偶问题和上述问题不同，上述问题是求\(L\)的最大值，这里是求最小值

\[ \Theta_{d}(\lambda, \eta) = \underset {x}{\operatorname {min}} L(x, \lambda,\eta) \]

考虑极大值问题\(\underset {\lambda, \eta}{\operatorname {max}} \Theta_{d}(\lambda, \eta) =\underset {\lambda, \eta}{\operatorname {max}} \underset {x}{\operatorname {min}} L(x, \lambda, \eta)\)，\(\underset {\lambda, \eta}{\operatorname {max}} \underset {x}{\operatorname {min}} L(x, \lambda, \eta)\)问题被称为广义拉格朗日函数的极大极小问题，定义其最优解：
\[ d^{*} = \underset {\lambda, \eta}{\operatorname {min}} \Theta_{d}(\lambda, \eta) \]

2.3 拉格朗日与其对偶问题的关系

上面我们已经写出了拉格朗日问题的最优解\(p^{*}\)以及其对偶问题的最优解\(d^{*}\)，二者关系：
\[ \underset {\lambda, \eta}{\operatorname {max}} \underset {x}{\operatorname {min}} L(x, \lambda, \eta) = d^{*} \leq p^{*} = \underset {x}{\operatorname {min}} \underset {\lambda, \eta:\eta \geq0}{\operatorname {max}} L(x, \lambda, \eta) \]
上述关系\(d^{*} \leq p^{*}\)是弱对偶条件，当“\(=\)“成立时，变成强对偶条件，此时\(d^{*} = p^{*}\)，可以用此结论来通过求解对偶问题得到拉格朗日函数的答案

对于可微函数，在KKT条件下强对偶成立，此时：

\[ \left\{\begin{matrix} \bigtriangledown_{x}f(x)+\bigtriangledown_{x}\lambda g(x)+\bigtriangledown_{x}\eta h(x) = 0 \\ g(x) = 0 \\ h(x) \leq 0 \\ \eta \geq 0 \\ \eta h(x) = 0 \end{matrix}\right. \]

**KKT条件：**分为三种，一种是无约束，一种是等式约束\(g(x)=0\)，另一种是不等式约束\(h(x)\leq 0\)

本文由 Yonghui Wang 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Dec 19, 2024 12:13 pm