Логистическая регрессия и алгоритм оптимизации модели максимальной энтропии

машинное обучение

Логистическая регрессия и теоретический вывод модели максимальной энтропииВ статье упоминаются четыре алгоритма оптимизации: это:

  1. Алгоритм градиентного спуска
  2. Метод квазиньютона (метод Ньютона)
  3. Обобщенное итеративное масштабирование (ГИС: Обобщенное итеративное масштабирование).
  4. Улучшенное итеративное масштабирование (IIS: улучшенное итеративное масштабирование).

Выражения и целевые функции логистической модели и модели максимальной энтропии:

логистическая модель
  • выражение
\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 Применение

В логистической модели вычислите частную производную целевой функции по весам каждой функции.

\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 Пакетный градиентный спускПакетный градиентный спуск является наиболее часто используемой формой градиентного спуска, Конкретный метод заключается в использовании всех выборок для обновления параметров.1.4.2 Стохастический градиентный спускМетод стохастического градиентного спуска на самом деле похож на метод пакетного градиентного спуска, разница в том, что он не использует все выборочные данные при поиске градиента, а выбирает только один образец для поиска градиента. Стохастический градиентный спуск и пакетный градиентный спуск — это две крайности, в одном используются все данные для градиентного спуска, а в другом — одна выборка для градиентного спуска. Естественно, преимущества и недостатки каждого очень заметны. Что касается скорости обучения, метод стохастического градиентного спуска использует только одну выборку за раз для итерации, поэтому скорость обучения очень высока, в то время как метод пакетного градиентного спуска не может удовлетворить скорость обучения при большом размере выборки. Для точности используется стохастический градиентный спуск для определения направления градиента только с одним образцом, что приводит к решению, которое, вероятно, будет неоптимальным. Что касается скорости сходимости, поскольку метод стохастического градиентного спуска итерирует одну выборку за раз, направление итераций сильно меняется, и он не может быстро сходиться к локальному оптимальному решению.1.4.3 Мини-пакетный градиентный спускМини-пакетный градиентный спуск — это компромисс между пакетным градиентным спуском и стохастическим градиентным спуском, то есть для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}

image.png

3. Квазиньютоновский метод.

Примечания к изучению метода Ньютона и метода квазиньютона (2) Условие квазиньютона

Метод Ньютона и квази-Ньютоновский метод примечания к изучению (3) Алгоритм DFP

4. Метод итеративного масштабирования (модель максимальной энтропии)полный код

использованная литература

Категории