Персептрон и его варианты

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

план содержания

    1. Персептрон
    • 1.1 Определение персептрона
    • 1.2 Алгоритм обучения персептрона
      • 1.2.1 Линейная разделимость наборов данных
      • 1.2.2 Функция потерь персептрона
      • 1.2.3 Первоначальная форма алгоритма обучения персептрона
      • 1.2.4 Двойная форма алгоритма обучения персептрона
        • 1.2.4.1 От примитивного к двойному
        • 1.2.4.2 Алгоритмы обучения в двойной форме
    • 1.3 Почему обучение персептрона сходится?
    • 1.4 Примеры
    1. Варианты персептронов
    1. Персептрон для голосования
    1. средний персептрон
    • 4.1 Определения
    • 4.2 Алгоритм обучения
    1. Структурированный персептрон
    • 5.1 Структурированное обучение
      • 5.1.1 Определение структурированного обучения
        • 5.1.1.1 Общая структура обработки
        • 5.1.1.2 Вероятностная интерпретация общей схемы
      • 5.1.2 Три проблемы, которые необходимо решить с помощью структурированного обучения
    • 5.2 Структурированный персептрон
      • 5.2.1 Определение структурированного персептрона
      • 5.2.2 Обучение структурированного персептрона
        • 5.2.2.1 Стратегия обучения структурированного перцептрона
        • 5.2.2.2 Алгоритм обучения структурированного персептрона
    1. использованная литература

1. Персептрон

Perceptron — это модель линейной классификации для задач бинарной классификации.Его вход — вектор признаков, представляющий выборочные признаки, а его выход — положительный или отрицательный класс, представляющий выборочную классификацию.

1.1 Определение персептрона

Предположим, что входное пространство признаков равноX⊆Rn, выходное пространствоY={−1,+1}.входитьx⃗еXпредставляет вектор признаков образца, соответствующий точке в пространстве признаков,выводyеYПредставляет класс выборки. Тогда функция из входного пространства в выходное пространство выглядит следующим образом:y=f(x)=sign(w⃗⋅x⃗+b)называется перцептроном. в,x⃗- вектор входных признаков,yвыходной класс, представляющий положительный или отрицательный класс,w⃗еRnназывается весовым вектором,bеRназывается предвзятостью,sign(z)символическая функция, т.sign(z)={+1, if z≥0−1, if z<0\begin{aligned} & Предположим, что входное пространство признаков равно X \subseteq R^n, а выходное пространство равно Y=\{-1, +1\}. \\ & input \vec{x} \in X представляет собой вектор признаков образца, соответствующий точке в пространстве признаков, \\ & output y \in Y представляет категорию образца. Тогда следующая функция из входного пространства в выходное пространство: \\ & \boxed{y = f(x) = sign(\vec{w} \cdot \vec{x} + b)} \\ & называется персептроном. Среди них \vec{x} — вектор входных признаков, y — выходная категория, представляющая положительный или отрицательный класс, \\ & \vec{w} \in R^n называется вектором весов, b \in R — называется частичным множеством, sign(z) является функцией знака, т.е. \text{if } z \lt 0 \end{case} } \end{aligned}

1.2 Алгоритм обучения персептрона

Персептрон соответствует разделению выборок на положительные и отрицательные категории во входном пространстве признаков.Разделяющая гиперплоскость, которые относятся к дискриминационной модели.

1.2.1 Линейная разделимость наборов данных

учитывая набор данныхT={(x1⃗,y1),(x2⃗,y2),…,(xn⃗,yn)},вxiеRn,yiеY={−1,+1},iе[1,n], если есть гиперплоскостьS:w⃗⋅x⃗+b=0Положительные и отрицательные точки выборки набора данных можно правильно разделить на две стороны гиперплоскости, а именнодля всех положительных классовiобразцы, естьw⃗⋅xi⃗+b>0,для всех отрицательных классовiобразцы, естьw⃗⋅xi⃗+b<0,Затем набор данных вызываетсяTявляется линейно разделимым набором данных, иначе он называется линейно неразделимым.\begin{align} & Учитывая набор данных T=\{(\vec{x_1}, y_1), (\vec{x_2}, y_2), \dots, (\vec{x_n}, y_n)\}, \\ & где x_i \in R^n, y_i \in Y=\{-1, +1\}, i \in [1, n], если существует гиперплоскость \\ & \boxed{S: \ vec{w } \cdot \vec{x} + b = 0} \\ & может правильно разделить положительные и отрицательные точки выборки набора данных по обеим сторонам гиперплоскости, то есть \\ & для всех положительных выборок класс имеет \vec{w} \cdot \vec{x_i} + b > 0, \\ & i-я выборка всех отрицательных классов имеет \vec{w} \cdot \vec{x_i } + b

1.2.2 Функция потерь персептрона

Цель обучения персептрона состоит в том, чтобы найти гиперплоскость разделения S, которая может линейно разделить обучающий набор в предположении, что обучающий набор является линейно отделимым, По этой причине стратегия обучения персептрона состоит в том, чтобы выбрать функцию потерь и объединить Функция потерь Минимизация, принять параметры на момент минимизации в качестве окончательных параметров модели.

Итак, вопрос в том, как выбрать функцию потерь?

Естественное решение состоит в том, чтобы выбрать общее количество неправильно классифицированных точек выборки, то есть постоянно уменьшать общее количество ошибочно классифицированных точек выборки во время обучения. Однако такая функция потерь не является непрерывно дифференцируемой функцией весов и смещений, и методы оптимизации, такие как градиентный спуск, не могут использоваться для получения минимального значения Поэтому персептрон использует метод, используемый для измерения ошибочно классифицированных точек выборки до разделения гиперплоскость Метод полного расстояния как функции потерь.

Так как это для измерения расстояния, то сначала дайте входное пространствоRnлюбая точка вxiк гиперплоскостиSрасстояние,Предположим, что уравнение гиперплоскости имеет видw⃗⋅x⃗+b=0:1∣∣w⃗∣∣∣w⃗⋅xi⃗+b∣в∣∣w⃗∣∣как векторw⃗изL2норма.Потому что, когда модель будет сэмплировать точки(xi,yi)ошибочно классифицирован как(xi,yi^)когда естьyi^=−yiТакже из-за yi^={+1, w⃗⋅xi⃗+b≥0−1, w⃗⋅xi⃗+b<0так yi^(w⃗⋅xi⃗+b)=−yi(w⃗⋅xi⃗+b)≥0так ∣w⃗⋅xi⃗+b∣=−yi(w⃗⋅xi⃗+b)Итак, неправильно классифицированные точки выборки(xi,yi^)к разделяющей гиперплоскостиSРасстояние:−1∣∣w⃗∣∣yi(w⃗ ⋅xi⃗+b)Наконец, игнорироватьw⃗изL2норма, предполагая, что набор ошибочно классифицированных точек выборки моделиM, тогда всеНеправильно классифицированные точки гиперплоскостиSПолное расстояние , то есть окончательная функция потерь:L(w⃗,b)=−∑(xi,yi)еMyi(w⃗ ⋅xi⃗+b)\begin{aligned} & Поскольку это мера расстояния, сначала укажите расстояние от любой точки x_i во входном пространстве R^n до гиперплоскости S, \\ & Предположим, что уравнение гиперплоскости равно \vec{w} \cdot \vec {x} + b = 0: \\ & \boxed{\frac{1}{||\vec{w}||}|\vec{w} \cdot \vec{x_i} + b| } \\ & Где ||\vec{w}|| — норма L_2 вектора \vec{w}. \\ & Поскольку, когда модель ошибочно классифицирует точку выборки (x_i, y_i) как (x_i, \hat{y_i}), возникает \boxed{\hat{y_i}=-y_i} \\ & И потому что \\boxed{ \hat{y_i} = \begin{case} +1, \ \vec{w} \cdot \vec{x_i} + b \ge 0 \\ -1, \ \vec{w} \cdot \vec{x_i} + b \lt 0 \end{cases} } \\ & so \\boxed{\hat{y_i}(\vec{w} \cdot \vec{x_i} + b) = -y_i(\vec{w} \ cdot \vec{x_i} + b) \ge 0} \\ & так \\boxed{|\vec{w} \cdot \vec{x_i} + b| = -y_i(\vec{w} \cdot \vec {x_i} + b)} \\ & So \ Расстояние от ошибочно классифицированной точки выборки (x_i, \hat{y_i}) до разделяющей гиперплоскости S равно: \\ & \boxed{-\frac{1}{|| \vec{w}||}y_i(\vec{w}\ \cdot \vec{x_i} + b)} \\ & Наконец, игнорируйте норму L_2 для \vec{w}, предполагая неправильно классифицированные точки выборки модели. равно M, то общее расстояние от всех \\ & ошибочно классифицированных точек до гиперплоскости S, то есть окончательная функция потерь: \\ & \boxed{L(\vec{w}, b)=-\sum_{ ( x_i, y_i) \in M}y_i(\vec{w}\ \cdot \vec{x_i} + b)} \\ \end{aligned}

1.2.3 Первоначальная форма алгоритма обучения персептрона

Вход: тренировочный наборT={(x1⃗,y1),(x2⃗,y2),…,(xn⃗,yn)},вxi⃗еRn,             yiеY={−1,+1},iе[1,n], скорость обученияηе[0,1]Выход: функция потерьL(w⃗,b)по минимальной стоимостиw⃗иb,и модель персептронаf(x)=sign(w⃗⋅x⃗+b)(1)Случайно выбранныхw⃗=w⃗0иb=b0(Его также можно грубо установить на0);(2)Выберите случайную выборку из обучающей выборки(xi⃗,yi);(3)рассчитатьyi^=sign(w⃗⋅xi⃗+b);(4)еслиyi^≠yi:Используйте следующую формулу расчета градиента, чтобы вычислить градиент функции потерь в текущей точке выборки:     {∂L∂w∣(xi,yi)=−yixi∂L∂b∣(xi,yi)=−yiЗатем используйте градиент для обновления параметров:     {w⃗←w⃗−η∂L∂w∣(xi,yi)=w⃗+ηyixib←b−η∂L∂b∣(xi,yi)=b+ηyi(5)перенаправить на(2), пока в обучающем наборе не останется ошибочно классифицированных точек выборки.\begin{align} & Input: обучающий набор T=\{(\vec{x_1}, y_1), (\vec{x_2}, y_2), \dots, (\vec{x_n}, y_n)\}, где \vec{x_i} \in R^n, \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ y_i \in Y=\{-1, +1\}, i \in [1, n] , скорость обучения \eta \in [0, 1]\\ & Выход: \vec{w} и b, когда функция потерь L(\vec{w}, b) принимает минимальное значение, \\ & \ \ \ \ \ \ \ \ \ \ \ \ и модель персептрона f(x)=sign(\vec{w} \cdot \vec{x} + b) \\ & (1) случайно выбранные \vec{w} = \vec {w}_0 и b = b_0 (также можно грубо установить равным 0); \\ & (2) случайным образом выбрать образец в обучающем наборе (\vec{x_i}, y_i); \\ & (3) вычислить \ hat {y_i}=sign(\vec{w} \cdot \vec{x_i} + b); \\ & (4) if \hat{y_i} \neq y_i: \\ & \ \ \ \ \ Используйте следующее вычисление градиента Формула вычисляет градиент функции потерь в текущей точке выборки: y_i)=-y_ix_i \\\frac{\partial L}{\partial b}|_(x_i, y_i)=-y_i \end{cases} } \\ & \ \ \ \ \ Затем используйте градиент для обновления параметры: \\ & \ \ \ \ \ \boxed{ \begin{cases} \vec{w} \gets \vec{w} - \eta \frac{\partial L}{\partial w}|_(x_i, y_i) = \vec{w} + \eta y_i x_i \\ b \gets b - \eta \frac{\partial L}{\partial b}|_(x_i, y_i) = b + \eta y_i \end{ case} }\\ & (5) Перейти к (2) до тех пор, пока в обучающем наборе не останется ошибочно классифицированных точек выборки. \end{выровнено}

1.2.4 Двойная форма алгоритма обучения персептрона

Мы знаем, что в исходном виде точки выборки(x⃗,y)выбирается случайным образом, то можно сказать, чтоВектор признаков выборочной точки извлекается много раз, при этом также можно сказать, что модель находится в этомМножественные неправильные классификации вектора признаков.Ключевая идея двойственной формы заключается в том, что она использует векторt⃗=(t1,t2,…,tn)T(nдля точки выборкичисло) для записи каждого вектора признаковx⃗количество ошибочных классификаций.\begin{aligned} & Мы знаем, что в исходной форме точки выборки (\vec{x}, y) извлекаются случайным образом, тогда можно сказать, что \ & вектор признаков определенной точки выборки извлекается повторно много раз, в то же время также можно сказать, что модель несколько раз неверно классифицировала этот вектор признаков \&. Ключевая идея двойственной формы \\& заключается в том, что она использует вектор \vec{t}=(t_1, t_2, \dots, t_n)^T (n - количество точек выборки \\&) для записи каждый вектор признаков Количество раз, когда \vec{x} был неправильно классифицирован. \end{выровнено}

1.2.4.1 От примитивного к двойному

Первоначальная форма алгоритма обучения использует следующую формулу для обновления параметров:

{w⃗←w⃗+ηyixib←b+η\begin{aligned} & \boxed{ \begin{cases} \vec{w} \gets \vec{w} + \eta y_i x_i \\ b \gets b + \eta \end{cases} } \end{aligned}

Теперь предположим

w⃗=0, b=0, и точка выборки(xi⃗,yi)неправильно классифицированныйtiвторосортный\begin{align} \boxed{\vec{w}=0,\b=0}, и точка выборки (\vec{x_i}, y_i) была неправильно классифицирована t_i раз \\ \end{align}

Тогда параметры модели можно записать в виде:

{w⃗=∑i=1ntiηyixib=∑i=1ntiηyi\begin{aligned} & \boxed{ \begin{cases} \vec{w} = \sum_{i=1}^{n} t_i \eta y_i x_i \\ b = \sum_{i=1}^{n} t_i \eta y_i \end{cases} } \end{aligned}
Наконец, параметры модели, которые необходимо изучить, следующие:w⃗иbстановится элементомti(iе[1,n])векторt⃗.\begin{aligned} & Наконец, изучаемые параметры модели заменяются с \vec{w} и b на вектор \vec{t}, элементами которого являются t_i(i \in [1, n]). \end{выровнено}

1.2.4.2 Алгоритмы обучения в двойной форме

Вход: тренировочный наборT={(x1⃗,y1),(x2⃗,y2),…,(xn⃗,yn)},вxi⃗еRn,             yiеY={−1,+1},iе[1,n], скорость обученияηе[0,1]Выход: функция потерьL(w⃗,b)по минимальной стоимостиt⃗, и модель персептрона             f(x⃗)=sign(∑j=1ntjηyjxj⃗x⃗+∑j=1ntjηyj)(1)инициализацияt⃗=0;(2)Выбор точки выборки случайным образом(xi⃗,yi);(3)yi^=sign(∑j=1ntjηyjxj⃗x⃗+∑j=1ntjηyj);(4)еслиyi^≠yi:Параметры обновления:ti←ti+1(5)перенаправить на(2), пока не останется ошибочно классифицированных точек выборки.\begin{align} & Input: обучающий набор T=\{(\vec{x_1}, y_1), (\vec{x_2}, y_2), \dots, (\vec{x_n}, y_n)\}, где \vec{x_i} \in R^n, \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ y_i \in Y=\{-1, +1\}, i \in [1, n] , скорость обучения \eta \in [0, 1]\\ & вывод: \vec{t}, когда функция потерь L(\vec{w}, b) принимает минимальное значение, а модель персептрона \\ & \ \ \ \ \ \ \ \ \ \ \ \ f(\vec{x})=sign(\sum_{j=1}^{n} t_j \eta y_j \vec{x_j} \vec{x} + \sum_ { j=1}^{n} t_j \eta y_j) \\ & (1) Инициализация \vec{t} = 0; \\ & (2) Произвольный выбор точки выборки (\vec{x_i}, y_i); \ \ & (3) \hat{y_i} = sign(\sum_{j=1}^{n} t_j \eta y_j \vec{x_j} \vec{x} + \sum_{j=1}^{n} t_j \eta y_j); \\ & (4) if \hat{y_i} \neq {y_i}: \\ & \ \ \ \ \ обновить параметры: t_i \gets t_i + 1 \\ & (5) перейти Перейти к (2) до тех пор, пока не останется ошибочно классифицированных точек выборки. \end{выровнено}

1.3 Почему обучение персептрона сходится?

Процесс доказательства сходимости см. в разделе 2.3.2 «Статистических методов обучения» (второе издание). Вывод, сделанный в книге, таков:

  • Когда обучающая выборка линейно отделима, количество ошибочных классификаций K при итеративном обучении имеет верхнюю границу, и гиперплоскость разделения, которая полностью правильно разделяет обучающую выборку, может быть найдена после конечного числа поисков;
  • Когда обучающая выборка линейно неделима, алгоритм обучения не может сходиться, и результат итерации будет колебаться.

1.4 Примеры

Продолжение следует, ждите

2. Варианты персептронов

  • проголосовал персептрон
  • Усредненный персептрон
  • Структурированный персептрон

3. Персептрон для голосования

Как упоминалось выше, персептрон будет обновлять параметры (веса и смещения) один раз в каждой итерации обучения, то есть на каждой итерации генерируется новая модель, если вы хотите знать, какая модель лучше, простое решение состоит в том, сравните новую модель со старой моделью в новом наборе данных и, если новая модель более точна, замените старую модель новой моделью. В общем, новая модель лучше, чем старая модель, поэтому еще один лучший способ - сохранить модель и уровень точности для нового набора данных для каждой итерации.При прогнозировании каждая модель дает свои собственные результаты прогнозирования, а при В то же время используйте соответствующие показатели точности в качестве веса, умножьте соответствующие результаты прогнозирования на средневзвешенный результат и, наконец, вычислите, какая модель имеет самый высокий конечный результат, и используйте самый высокий результат в качестве окончательного результата прогнозирования, чтобы восприятие операции машина называетсяПерсептрон для голосования.

4. Средний персептрон

Поскольку персептрон голосования должен сохранять параметры каждого раунда итерации и соответствующую точность, и в то же время должен выполнять дополнительный расчет средневзвешенного значения во время предсказания, он не является элегантным с точки зрения временной сложности и пространственной сложности. предложить более отличныйсредний персептрон: Инициализируйте сумму параметров перед итерацией, добавьте обновленное значение параметра к сумме параметров в каждой итерации и разделите сумму параметров на количество итераций после итерации, чтобы получить окончательную модель.

4.1 Определения

Определение среднего персептрона такое же, как и у обычного персептрона, но алгоритм обучения отличается.

4.2 Алгоритм обучения

Вход: тренировочный наборT={(x1⃗,y1),(x2⃗,y2),…,(xn⃗,yn)},вxiеRn,             yiеY={−1,+1},iе[1,n], скорость обученияηе[0,1]вывод: итерацияNЗа рулемw⃗иbсоответствующие средние значения и модель персептрона             f(x⃗)=sign(w⃗⋅x⃗+b)(1)инициализацияw⃗совокупная суммаsw⃗а такжеbсовокупная суммаsb;(2)Случайно выбранныхw⃗=w⃗0иb=b0(Его также можно грубо установить на0);(3)Выберите случайную выборку из обучающей выборки(xi,yi);(4)рассчитатьyi^=sign(w⃗⋅xi⃗+b);(5)еслиyi^≠yi:Используйте следующую формулу расчета градиента, чтобы вычислить градиент функции потерь в текущей точке выборки:     {∂L∂w∣(xi,yi)=−yixi∂L∂b∣(xi,yi)=−yiЗатем используйте градиент для обновления параметров:     {w⃗←w⃗−η∂L∂w∣(xi,yi)=w⃗+ηyixib←b−η∂L∂b∣(xi,yi)=b+ηyiЗатем добавьте два кумулянта:{sw⃗←sw⃗+w⃗sb←sb+b(6)перенаправить на(2), пока в обучающей выборке не останется ошибочно классифицированных точек выборки;(7)рассчитатьw⃗иbсреднее из:{w⃗‾=sw⃗Nb‾=sbN\begin{align} & Input: обучающий набор T=\{(\vec{x_1}, y_1), (\vec{x_2}, y_2), \dots, (\vec{x_n}, y_n)\}, где x_i \in R^n, \\ & \ \ \ \ \ \ \ \ \ \ \ \ y_i \in Y=\{-1, +1\}, i \in [1, n], скорость обучения \ eta \in [0, 1]\\ & вывод: соответствующие средние значения \vec{w} и b после N итераций, а также модель персептрона \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ f (\vec {x})=sign(\vec{w} \cdot \vec{x} + b) \\ & (1) Инициализировать кумулянты \vec{w}\vec{s_w} и кумулянты b s_b;\ \ & (2) случайным образом выбрать \vec{w} = \vec{w}_0 и b = b_0 (также можно грубо установить равным 0);\\ & (3) случайным образом выбрать выборку в обучающем наборе ( x_i, y_i); \\ & (4) вычислить \hat{y_i}=sign(\vec{w} \cdot \vec{x_i} + b); \\ & (5) если \hat{y_i} \neq y_i: \\ & \ \ \ \ \ Используйте следующую формулу расчета градиента для расчета градиента функции потерь в текущей точке выборки: \\ & \ \ \ \ \ \boxed{ \begin{cases} \frac{\partial L }{\ partial w}|_(x_i, y_i)=-y_ix_i \\ \frac{\partial L}{\partial b}|_(x_i, y_i)=-y_i \end{cases}} \\ & \ \ \ \ \ Затем используйте градиент для обновления параметров: \\ & \ \ \ \ \ \boxed{ \begin{cases} \vec{w} \gets \vec{w} - \eta \frac{\partial L }{\partial w} |_(x_i, y_i) = \vec{w} + \eta y_i x_i \\ b \gets b - \eta \frac{\partial L}{\partial b}|_(x_i, y_i) = b + \ eta y_i \end{cases} }\\ & \ \ \ \ \ Затем добавьте два кумулянта: \boxed{ \begin{cases} \vec{s_w} \gets \vec{s_w} + \vec{w} \\ s_b \gets s_b + b \end{cases} } \\ & (6) Переход к (2) до тех пор, пока в обучающая выборка До классифицированных точек выборки \\ & (7) Вычислить среднее значение \vec{w} и b: \boxed{ \begin{case} \overline{\vec{w}} = \frac{\vec {s_w} }{N} \\ \overline b = \frac{s_b}{N} \end{case} } \end{aligned}

5. Структурированный персептрон

Структурированный персептрон — это линейная модель, улучшенная на основе персептрона с целью достижения структурированного обучения.

Далее кратко вводятся базовые знания о структурированном обучении, а затем даются определение и алгоритм обучения структурированного персептрона.

5.1 Структурированное обучение

Мы знаем, что модели, используемые для задач регрессии, будут выводить одно или несколько непрерывных скалярных значений, модели, используемые для задач классификации, будут выводить одно или несколько дискретных значений, представляющих категории или метки, а модели, используемые для структурированной обученной модели, выводят набор данных, которые подчиняется отношению или структуре.

В НЛП тегирование частей речи и синтаксический анализ можно рассматривать как примеры структурированного обучения.Первая модель выводит последовательность частей речи, соответствующую каждому слову предложения, а вторая модель выводит синтаксическое дерево. Мы знаем, что в структуре данных последовательность представляет собой набор наборов данных, которые удовлетворяют линейному отношению один к одному, а дерево — это набор наборов, которые удовлетворяют отношениям один ко многим или многие к одному. Таким образом, значение структуры можно понимать как модель.Выход представляет собой некоторую структуру данных.

5.1.1 Определение структурированного обучения

Цель структурированного обучения состоит в том, чтобы дать входной вектор признаковx⃗и соответствующая структура выводаyв случае,найти измеримоеx⃗иyФункция оценки соответствияf(x⃗,y), так что функция подсчета очков может возвращать тот, который имеет наивысший балл при прогнозированииy^как вывод.\begin{aligned} & Цель структурированного обучения состоит в том, чтобы найти метод, который может измерить степень соответствия \vec{x} и y с учетом входного вектора признаков \vec{x} и соответствующей выходной структуры y. Функция оценки f (\vec{x}, y), чтобы функция подсчета очков могла возвращать \hat{y} с наивысшим результатом в качестве результата при прогнозировании. \end{выровнено}

5.1.1.1 Общая структура обработки

Структурированное обучение предполагает обучение (training),предсказывать(prediction) или сделать вывод (inference)Два звена, в которых на этапе обучения необходимо(X,Y)Найдите тот, который можно использовать в качестве оценкикарта функцийf(x,y),На этапе прогнозирования необходимоx⃗При условии найти структуру с наивысшим балломy^.В общем виде эти два этапа можно представить следующим набором формул:{f(x,y):X×Y→Ry^=argmaxyеYf(x,y)\begin{aligned} & Структурированное обучение состоит из двух этапов: обучение, предсказание или вывод\\ &. На этапе обучения необходимо найти решение, которое можно использовать в качестве обучающего набора (X, Y). Отображение f(x, y) скоринговой функции \\ &, \\ & На этапе прогнозирования необходимо найти структуру с наивысшим баллом \hat{y} при заданном входном признаке \vec{x}. \\ & В общем случае эти две фазы можно представить следующим набором выражений: \\ & \boxed{ \begin{cases} f(x, y): X \times Y \to R \\ \ hat{y } = argmax_{y \in Y}f(x, y) \end{cases} } \end{aligned}

5.1.1.2 Вероятностная интерпретация общей схемы

Если два вышеуказанных этапа описать с позиции вероятности, то возможны следующие приблизительные объяснения:{P(X,Y)→[0,1]y^=argmaxyеYP(Y∣X)=argmaxyеYP(X,Y)P(X)≈argmaxyеYP(X,Y)в тренировочном наборе(X,Y)середина,P(X)Его можно рассматривать как константу, поэтому есть приближение второй формулы выше.\begin{aligned} & Если два вышеуказанных этапа описать с точки зрения вероятности, они имеют следующую приблизительную интерпретацию: \\ & \boxed{ \begin{cases} P(X, Y) \to [0, 1] \\ \hat{y} = argmax_{y \in Y}P(Y|X) = argmax_{y \in Y} \frac{P(X, Y)}{P(X)} \ приблизительно argmax_{y \in Y}P(X, Y) \end{cases} } \\ & В обучающем наборе (X, Y) P(X) можно рассматривать как константу, поэтому существует аппроксимация второй формулы выше . \end{выровнено}

5.1.2 Три проблемы, которые необходимо решить с помощью структурированного обучения

  • Форма скоринговой функции f(X, Y)
  • Как рассчитать наивысший балл
  • Учитывая тренировочный набор (X, Y), как определить f (X, Y)

5.2 Структурированный персептрон

5.2.1 Определение структурированного персептрона

Мы знаем, что персептрон — это линейная модель, поэтому, чтобы линейная модель поддерживала структурированное обучение,Во-первых, необходимо определить форму скоринговой функции. Как видно из вышеизложенного, оценочная функцияf(x,y)нужно дваПараметры: входные собственные векторыx⃗и структура выводаy.Однако оценочная функция предыдущего персептрона требует только одного параметраx⃗:w⃗⋅x⃗+b, то структураyКак это учесть? Ответ заключается в определении новых характеристических функций:ϕ(x⃗,y), поставить структуруyтакже какособенность с исходным вектором признаковx⃗объединяются вместе в структурированные векторы признаков.Чтобы функция оценки подчинялась линейной зависимости, функция оценки может быть определена следующим образом:f(x⃗,y)=w⃗⋅ϕ⃗(x⃗,y),в,ϕ⃗представляет собой набор характеристических функцийϕiсостоит из векторовИтак, при прогнозировании:y^=argmaxyеY[(w⃗⋅ϕ⃗(x⃗,y)]\begin{aligned} & Мы знаем, что персептрон является линейной моделью, поэтому, чтобы линейная модель поддерживала структурированное обучение, \\ & должен сначала определить форму функции оценки. Как видно из вышеизложенного, оценочная функция f(x, y) требует двух параметров \\ &: вектора входных признаков \vec{x} и выходной структуры y. \\ & \\ & Однако оценочная функция предыдущего персептрона требует только одного параметра \vec{x}: \vec{w} \cdot \vec{x} + b, тогда как структура y \\ & учитывать шерстяное сукно? Ответ состоит в том, чтобы определить новую функцию признаков: \phi(\vec{x}, y), рассматривать структуру y как признак \\ & и объединить его с исходным вектором признаков \vec{x} для формирования структурированного вектор признаков. \\ & \\ & Чтобы функция оценки следовала линейной зависимости, функция оценки может быть определена следующим образом: \\ & \boxed{ f(\vec{x}, y) = \vec{w} \cdot \ vec{\phi} (\vec{x}, y), где \vec{\phi} — вектор набора функций признаков \phi_i} \\ & Итак, при прогнозировании: \\ & \boxed{ \hat {y} = argmax_{y \in Y} [(\vec{w} \cdot \vec{\phi}(\vec{x}, y)] } \end{aligned}

5.2.2 Обучение структурированного персептрона

5.2.2.1 Стратегия обучения структурированного перцептрона

Целью обучения структурированного персептрона является нахождение оценочной функцииf(x,y), эта оценочная функция может бытьзаданный вектор признаковxi⃗из множества структур при условииYвыбрать один изxi⃗лучший матчyi.Так как же функция подсчета очков находит наилучшее совпадение?yШерстяная ткань? Простой и грубый способ - структурироватьИсчерпывающее все в комплектеy, положи этоyс даннымx⃗вместе в пару(x⃗,y), то пусть оценкаФункция оценивает каждую пару таких комбинаций, а затем выбирает наивысшую оценку в качестве выходных данных.Однако, к счастью, на этапе обучения для тренировочного набора(X,Y)любой изxiеX, с этимлучший матчyФактически установлено, чтоyi.Итак, во время обучения мы можем сделать функцию подсчета очков в точке выборки(xi⃗,yi)высший балл в остальномисчерпывающая комбинация(xi⃗,yj)(i≠j)чтобы дать более низкую оценку, это гарантирует, что функция подсчета очков может предсказатьвывод правильныйyi.Если вы хотите использовать математический язык, чтобы выразить приведенный выше текст, есть следующее утверждение:известная скоринговая функцияf(x⃗,y)=w⃗⋅ϕ⃗(x⃗,y),заданная точка выборки(xi⃗,yi)и остальные исчерпывающие комбинации(xi⃗,yj)(i≠j),найти разрешающее неравенствоw⃗^⋅ϕ⃗(xi⃗,yi)≥w⃗^⋅ϕ⃗(xi⃗,yj)учредилw⃗^.Теперь обе части неравенства представлены в виде скалярного произведения двух векторов, а затем по числу скалярного произведения векторовВ чем смысл?Выражение в левой части неравенства можно рассматривать как точку отсчета(xi⃗,yi)Собственные векторы, представленные в вектореw⃗^Длина проекции на , аналогично, выражение в правой части неравенства есть исчерпывающая комбинация остальных(xi⃗,yj)представлятьСобственные векторыw⃗^Длина проекции на .Итак, как сделать длину проекции слева больше, чем проекцию справа при итеративном обучении?Ответ - вектор вращенияw⃗^, приближая его к собственным векторамϕ⃗(xi⃗,yi), держась подальше отϕ⃗(xi⃗,yj):w⃗←w⃗+ϕ^(xi⃗,yi)−ϕ^(x⃗,yj)(i≠j)\begin{aligned} & Цель обучения структурированного персептрона состоит в том, чтобы найти оценочную функцию f(x, y), которую можно выбрать из набора структур Y при условии \\ & при заданном векторе признаков \vec{x_i } y_i, который лучше всего соответствует \vec{x_i}. \\ & Так как же функция подсчета очков находит наилучшее соответствие y? Простой и грубый способ состоит в том, чтобы полностью перебрать все y в структуре \\ & set, объединить это y с заданным \vec{x} в пару (\vec{x}, y), а затем присвоить счету \ The Функция \& оценивает каждую такую ​​комбинацию и выбирает наивысшую оценку в качестве вывода. \\ & \\ & К счастью, на этапе обучения для любого x_i \in X в тренировочном наборе (X, Y) действительно был определен y, который лучше всего соответствует его \\ &, тогда это y_i. \\ & Итак, во время обучения мы можем позволить функции подсчета очков получить наивысший балл по точкам выборки (\vec{x_i}, y_i), а при исчерпывающей комбинации оставшихся \\ & (\vec{x_i}, y_j) (Меньшая оценка i \neq j) гарантирует, что функция оценки \\ & выводит правильный y_i при прогнозировании. \\ & \\ & Если вы хотите выразить вышеприведенный текст математическим языком, есть следующее утверждение: \\ & Известная функция подсчета очков f(\vec{x}, y) = \vec{w} \cdot \ vec {\phi}(\vec{x}, y), \\ & заданные точки выборки (\vec{x_i}, y_i) и остальные исчерпывающие комбинации (\vec{x_i}, y_j)(i \neq j ), \\ & найдите неравенства, которые \\ & \boxed{ \hat{\vec{w}} \cdot \vec{\phi}(\vec{x_i}, y_i)\ge \hat{\vec{ w}} \cdot \vec{\phi}(\vec{x_i}, y_j) } \\ & содержит \hat{\vec{w}}. \\ & Теперь обе части неравенства представлены в виде операции скалярного произведения двух векторов, и тогда по смыслу скалярного произведения векторов выражение в левой части неравенства можно рассматривать как образец точка (\vec{x_i}, длина проекции вектора признаков, представленного y_i) на вектор \\ & \hat{\vec{w}}, аналогично, выражение в правой части неравенства является оставшимся исчерпывающим комбинация (\ vec {x_i}, y_j) представляет \ Прогнозируемую длину собственных векторов \ & на \ hat {\ vec {w}}. \ & Итак, как сделать длину проекции слева больше, чем проекцию справа при итеративном обучении? \\ & Ответ состоит в том, чтобы повернуть вектор \hat{\vec{w}} так, чтобы он был ближе к собственным векторам \vec{\phi}(\vec{x_i}, y_i) и дальше от \vec{\phi }(\vec {x_i}, y_j): \\ & \boxed{ \vec{w} \gets \vec{w} + \hat{\phi}(\vec{x_i}, y_i) - \hat{\ phi}(\ vec{x}, y_j)(i \neq j) } \end{выровнено}

5.2.2.2 Алгоритм обучения структурированного персептрона

Вход: тренировочный набор(X,Y)={(x1⃗,y1),(x2⃗,y2),…,(xn⃗,yn)}вывод: весаw⃗(1)случайная инициализацияw⃗=w0(Его также можно установить непосредственно как0);(2)Выбор точки выборки случайным образом(xi⃗,yi);(3)коллекция в структуреYнайти вxi⃗лучший матчyi^;(4)еслиyi^≠yi:Параметры обновления:w⃗←w⃗+ϕ^(xi⃗,yi)−ϕ^(x⃗,yj)(yiеY,yjеY,i≠j)(5)перенаправить на(2), пока параметрw⃗пока больше не будет обновлений.\begin{выровнено} и ввод: обучающий набор (X, Y) = \{(\vec{x_1}, y_1), (\vec{x_2}, y_2), \dots, (\vec{x_n}, y_n) \} \\ & Вывод: Вес \vec{w} \\ & (1) Случайная инициализация \vec{w}=w_0 (также можно установить в 0 напрямую); \\ & (2) Случайный выбор точки выборки ( \ vec{x_i}, y_i); \\ & (3) найти \hat{y_i}, которая лучше всего соответствует \vec{x_i} в наборе структур Y; \\ & (4) если \hat{y_i} \ neq y_i : \\ & \ \ \ \ \ Параметры обновления: \vec{w} \gets \vec{w} + \hat{\phi}(\vec{x_i}, y_i) - \hat{\phi}( \vec {x}, y_j)(y_i \in Y, y_j \in Y, i \neq j) \\ & (5) Переход к (2) до тех пор, пока параметр \vec{w} больше не будет обновляться. \end{выровнено}

6. Ссылки

[1].«Введение в обработку естественного языка» Хе Хана

[2].«Статистические методы обучения» (второе издание), Ли Ханг

[3]. Introduction of Structured Learning, Hung-yi Lee

[4]. Structured Linear Model, Hung-yi Lee

[5]. Understanding the Averaged Perceptron Machine Learning Technique

[6]. Как понять двойную форму алгоритма обучения персептрона?

Категории