Stochastic Methods in Machine Learning: Outline

几个细分topics之间的关系和逻辑。
首先，介绍了待解决问题的背景，机器学习的问题。机器学习中的优化问题是什么？

优化的方法：

• Coordinate Descent：坐标下降法
• Stochastic Gradient Descent：随机梯度下降法
  • 解决Binary Classification问题
  • Over-Paramaterization
  • Minibatch SGD
• SVRM(Stochastic Variance Reduction Method)
• Perceptron方法

机器学习

机器学习有三个维度：

• 数据：数据之间有输入和输出，输入和输出之间有隐藏关系。
• 模型：给定输入，经过模型，有相应预测输出$\hat{y}$。
• 优化：找到模型的最优参数。

Loss function: $l(y,\hat{y})$损失函数测量了真实值$y$和预测值$\hat{y}$之间的距离，是一个非负的值。

• 平方损失：$l(y,\hat{y})={1\over 2}(y-\hat{y})^2$，用在回归问题。
• 0-1损失：用在分类问题。 $$l(y,\hat{y})= \begin{cases} 0, & otherwise \\ 1, & if\ y \neq \hat{y}. \end{cases}$$

机器学习中的优化问题是什么？

$$\min_{x\in \Omega} \{f(x)={1\over m}\sum_{i=1}^m l(y^i,h_x(s^i))+\lambda \cdot r(x)\}$$

• ${1\over m}\sum_{i=1}^m l(y^i,h_x(s^i))$是数据拟合项(data fitting term)。
• $\lambda \cdot r(x)$是正则化项，防止数据过拟合。
• 如果数据$x=(x_1,x_2,…,x_n)$是高维度$n$：采用一阶算法，例如梯度下降(gradient descent)。
• 如果是大规模数据$m$：采用随机算法，例如随机梯度下降(stochastic gradient descent)。

解决优化问题的算法

坐标下降(Coordinate Descent, CD)

坐标下降指沿着一个坐标轴（维度）下降，保持其他坐标轴（维度）数据不变。

$e^i=(0,…,0,1,0,…,0)^\mathrm{T}$指的是标准基向量，其中第$i$个位置是1，其他位置是0。

坐标下降公式：在第$k$次迭代中，我们选择$i_k \in {1,2,…,n}$（$x$有$n$个维度，即选择沿着第$i_k$个坐标轴下降）：

$$x^{k+1}=x^k+\eta_ke^{i_k}$$

如何计算$\eta_k$呢？可以选择exact coordinate minimization，即选择让$f(x^k+\eta e^{i_k})$最小的$\eta$。

$$\eta_k=arg\min_\eta f(x^k+\eta e^{i_k})$$

Exact Coordinate Minimization解决Linear Regression问题

我们选择$ik \in {1,…,n}$，可得到：
<!— $$
x{ik}={s{ik}^\mathrm{T}(y-v{ik})}\over {s{ik}^\mathrm{T}s{ik}}},\ v{ik}=\sum{j:j\neq i_k} x_js_j

$$--> 有三种$i_k$的选择方式？（$i_k$是选择下降的维度） * 循环坐标下降 * 随机坐标下降(Randomized coordinate descent, RCD) * uniform sampling: select $i_k=i$ with probability $1/n$ * non-uniform sampling: select $i_k=i$ with probability $p_i$ * 贪心选择坐标 为什么使用坐标下降法：简单；不需要保存所有数据。 ### 随机梯度下降方法(Stochastic Gradient Descent, SGD) 解决数据量很大的优化问题，优化问题的形式如下：$$

arg\min{x\in R^n} {f(x)={1\over m}\sum{i=1}^m f_i(x)}

$$其中，$f_i$是测量第$i$个训练样本$(s^i,y^i)$的误差，例如对于平方差损失$f_i(x)=1/m \sum_{i=1}^m f_i(x)$。 如果$m$很大的时候，需要计算$m$个$\nabla f_i(x)$，所以计算量很大。 #### GD vs SGD 梯度下降Gradient Descent: $$x^{k+1}=x^k-\eta_k \nabla f(x^k)=x^k-{\eta_k \over m}\sum_{i=0}^m \nabla f_i(x^k)$$

随机梯度下降，即随机选择一个维度的梯度下降，不需要求出所有维度的梯度：

$$x^{k+1}=x^k-\eta_k \nabla f_{i_k}(x^k)$$

SGD for Binary Classification

1. SVM：找到一个超平面（或边界），最大化不同类别之间的间隔（margin）。它可以用于线性和非线性分类。

SVM问题的优化问题，一共有$m$组数据：

$$\min_x {f(x)={1\over m}\sum_{i=0}^m f_i(x)}.$$

其中，对于第$i$组训练数据，有

$$f_i(x)={\lambda \over 2}\|x\|^2+\max\{0,1-y^ix^\mathrm{T}s^i\}.$$

所以，SVM的优化问题可以改写为：

$$\min_x {\lambda \over 2}\|x\|^2 + {1\over m}\sum_{i=1}^m \max\{0,1-y^ix^\mathrm{T}s^i\}.$$

第一步需要计算$\nabla f_i(x)$：

• 如果预测正确，即$$

1. Logistic Regression：

神经元法(Perceptron)

本质上是神经网络方法，perceptron是神经网络的一个结点。

---

• ← Previous Post
• Next Post →