Logistic回归与最大熵模型-优化算法

2019-07-25 本文已影响17人 To_QT

Logistic回归与最大熵模型-理论推导中提到了4个优化算法：分别是：

梯度下降算法
拟牛顿法（牛顿法）
通用迭代尺度法（GIS: Generalized Iterative Scaling）。
改进的迭代尺度法（IIS: Improved Iterative Scaling）。

logistics和最大熵模型的表达式和目标函数为：

logistics模型

表达式
$\begin{align} h_w(x_i) =\frac{e^{w·x_i}} {1+e^{w·x_i}}\tag{1.1} \end{align}$
目标函数
$\begin{align} J(w) = \underset{w}{max}\ log L(w) =&\sum_{i=1}^{N} [y_i(w·x) - log(1+exp(w·x))]\tag{1.2} \end{align}$

最大熵模型

表达式
$\begin{align} p_w(y|x) =& \frac{exp (\sum_{i=1}^{n} w_i f_i(x,y))} {Z_w(x)} \tag{1.3} \end{align}$
目标函数
$\begin{align} \underset{w}{max}\ \Psi(w)=& \sum_{i=1}^{n}w_i ·\sum_{x,y} \widetilde{P}(x,y)f_i(x,y) - logZ_w(x) ·( \sum_{x}\widetilde{P}(x)) \tag{1.4} \end{align}$
其中
$Z_w(x) = \sum_{y} exp (\sum_{i=1}^{n} w_i f_i(x,y))\tag{1.5}$

大前提

对于数据集 $T=\{(x_1,y_1),...,(x_N,y_N)\}$ ， $y_i$ 代表第 $i$ 条数据的类标签， $x_i$ 代表第 $i$ 条数据的特征， $x_i^{(j)}$ 代表第 $i$ 条数据的 $j$ 个特征。

假定目标函数 $f$ 为凸函数，且两阶连续可微，函数的最小值为 $x^*$ 。

1.梯度下降算法

1.1 梯度

梯度在数学上的定义是：梯度的方向是变化速度最快的方向。
这样的意义在于，沿着梯度的方向，更加容易找到函数的最大值；若相反，梯度减少也最快，更容易找到最小值。

1.2 应用

在logistics 模型中，计算目标函数对每个特征的权重的偏导数。
$\begin{align} \frac{\partial{J(w)}}{\partial{w^{(j)}}} =& \sum_{i=1}^{N} [y_i·x_i^{(j)} - h_w(x_i)·x_i^{(j)}] \end{align}$
则权重的更新为：
$\begin{align} J(w) =J(w)+\alpha \frac{\partial{J(w)}}{\partial w^{(j)}} \end{align}$

算法流程-《梯度下降法、牛顿法和拟牛顿法》

1.3 不足

每一步走的距离在极值点附近非常重要，如果走的步子过大，容易在极值点附近震荡而无法收敛。

解决办法：将 $\alpha$ 设定为随着迭代次数而不断减小的变量，但是也不能完全减为零。

1.4 各种梯度下降

1.4.1 批量梯度下降法（Batch Gradient Descent）
批量梯度下降法，是梯度下降法最常用的形式，具体做法也就是在更新参数时使用所有的样本来进行更新。
1.4.2 随机梯度下降法（Stochastic Gradient Descent）
随机梯度下降法，其实和批量梯度下降法原理类似，区别在与求梯度时没有用所有的样本的数据，而是仅仅选取一个样本来求梯度。
随机梯度下降法，和批量梯度下降法是两个极端，一个采用所有数据来梯度下降，一个用一个样本来梯度下降。自然各自的优缺点都非常突出。对于训练速度来说，随机梯度下降法由于每次仅仅采用一个样本来迭代，训练速度很快，而批量梯度下降法在样本量很大的时候，训练速度不能让人满意。对于准确度来说，随机梯度下降法用于仅仅用一个样本决定梯度方向，导致解很有可能不是最优。对于收敛速度来说，由于随机梯度下降法一次迭代一个样本，导致迭代方向变化很大，不能很快的收敛到局部最优解。
1.4.3 小批量梯度下降法（Mini-batch Gradient Descent）
小批量梯度下降法是批量梯度下降法和随机梯度下降法的折衷，也就是对于 $m$ 个样本，我们采用 $x$ 个样本来迭代， $1<x<m$ ，一般 $x=16,32,64...$ ，当然根据样本的数据，可以调整这个值。

1.5 代码实现

    #==============梯度上升优化算法=======================#
    def _batchGradientAscent(self, nums, lr):
        '''
        梯度上升优化算法
        ------
        :param nums: <np.ndarray>迭代次数
        :param lr: <np.ndarray>学习率
        :return:
        '''
        for k in range(nums):
            print('%d th iterations' % k)
            output = self.predict(self.input_vecs)
            delta = lr * (self.labels - output.T)
            delta_weight = np.dot(self.input_vecs.T, delta)
            self.weight += delta_weight.T

    # ==============随机梯度上升优化算法=======================#
    def _StochasticGradientAscent0(self, lr):
        '''
        随机梯度上升优化算法
        ------
        :param lr: <np.ndarray>学习率
        :return:
        '''
        for inum in range(self.n_nums):
            output = self.predict(self.input_vecs[inum])
            delta = lr * (self.labels[inum] - output.T)
            delta_weight = self.input_vecs[inum] * delta
            self.weight += delta_weight.T

    # ==============随机梯度上升优化算法=======================#
    def _StochasticGradientAscent1(self, nums):
        '''
        随机梯度上升优化算法
        ------
        :param nums: <np.ndarray>迭代次数
        :return:
        '''
        for iteration in range(nums):
            for inum in range(self.n_nums):
                data_index = [_ for _ in range(self.n_nums)]
                lr = 4 / (iteration + inum + 1) + 0.01
                rand_index = int(random.uniform(0, self.n_nums))
                output = self.predict(self.input_vecs[rand_index])
                delta = lr * (self.labels[rand_index] - output.T)
                delta_weight = self.input_vecs[rand_index] * delta
                self.weight += delta_weight.T
                del(data_index[rand_index])

    # ==============小批量梯度上升优化算法=======================#
    def _MiniBatchGradientAscent(self, nums, lr, batch_size=16):
        '''
        小批量梯度上升优化算法
        ------
        :param nums: <np.ndarray>迭代次数
        :param lr: <np.ndarray>学习率
        :param batch_size: <np.ndarray>批学习大小
        :return:
        '''
        for iteration in range(nums):
            for ibatch in range(1, self.n_nums // batch_size):
                start_index = (ibatch-1) * batch_size
                end_index = ibatch * batch_size

                mini_train_data = self.input_vecs[start_index: end_index, ]
                mini_label = self.labels[start_index: end_index, ]

                output = self.predict(mini_train_data)
                delta = lr * (mini_label - output.T)
                delta_weight = np.dot(mini_train_data.T, delta)
                self.weight += delta_weight.T

    def train(self, nums, optimization='gradAscent', lr=0.001):
        '''
        训练logistics模型
        :param nums: 迭代次数
        :param input_vecs: 训练样本的特征值
        :return:
        '''
        if optimization == 'gradAscent':
            self._batchGradientAscent(nums, lr)
        elif optimization == 'SGA0':
            self._StochasticGradientAscent0(lr)
        elif optimization == 'SGA1':
            self._StochasticGradientAscent1(nums)
        elif optimization == 'MGA':
            self._MiniBatchGradientAscent(nums, lr, batch_size=16)

2. 牛顿法

2.1 基本思想(先考虑单值的情况)

利用牛顿法判断函数的解。设在 $x_k$ 为当前极小值的估计点，由泰勒公式可知
$\begin{align} \psi(x) = f(x_k)+f'(x_k)(x-x_k)+\frac{1}{2}f''(x_k)(x-x_k)^2\tag{2.2} \end{align}$
令 $\psi(x)=0$ ，若 $x_k$ 不满足条件，则迭代式可为
$\begin{align} x_{k+1}=x_k-\frac{f'(x_k)}{f''(x_k)} \end{align}$
此时可认定为 $f(x_{k+1})$ 比 $f(x_k)$ 更接近与0，当 $f(x^*)=0$ 的时候收敛。

2.1 基本思想(矩阵的情况)

$\begin{align} \psi(x) = f(x_k)+\bigtriangledown f(x_k)(x-x_k)+\frac{1}{2}\bigtriangledown^2f(x_k)(x-x_k)^2\tag{2.2} \end{align}$

若要 $\psi(x)$ 有极值点，则需要 $\bigtriangledown \psi(x)=0$ ，故有
$\bigtriangledown f(x_k) + \bigtriangledown^2 f(x_k)(x-x_k) = 0 \tag{2.3}$
当矩阵 $H_k$ 非奇异矩阵时，有
$x_{k+1}=x_k + (\bigtriangledown^2 f(x_k))^{-1}·\bigtriangledown f(x_k) = 0 \tag{2.3}$