Translate

вторник, 9 декабря 2014 г.

Машинное обучение с оппонентом


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

Также нам уже известно, что задачу классификации можно представить в виде системы линейных неравенств.

Возникает естественный вопрос, каким методом решать эту самую систему? Вроде бы напрашиваются очевидные ответы: линейным или квадратичным программированием. Ведь эти методы и предназначены для систем линейных неравенств? Кстати, квадратичное программирование используется в машине опорных векторов.

Но такой ответ был бы неверным. Потому что в этом случае мы бы не обобщили, а всего лишь построили самую оптимистичную модель, наиболее склонную к переобучению.

Почему?

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

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

Если наш водитель будет многократно ездить от пункта А до пункта Б, то рано или поздно он переобучится. Почему не обучится, а именно переобучится? Дело в том, что когда человек что-то многократно вызубривает, то он запоминает некоторые признаки, способствующие улучшению памяти, но не имеющие отношения к предмету обучения. В более наглых случаях он не только запоминает, но и записывает на какие нибудь, например, бумажные носители такую информацию — шпаргалки, чтобы впоследствии ими воспользоваться.

Если водитель уже многократно проезжал по одной и той же трассе, то он запомнил много различных шпаргалок, которые никакого отношения к дорожному движению не имеют, т. к. не находятся на дорожном покрытии и не являются дорожными знаками или другими автотранспортными средствами. Шпаргалками в этом случае являются различные, хорошо  визуально различимые объекты расположенные вдоль обочины. Это самые настоящие шпаргалки, которые даже записывать нет необходимости, т. к. уже где-то расположены и прекрасно видимы. С помощью этих шпаргалок водитель начинает не только лучше ориентироваться, но и получает более высокие прогнозные способности. Например, увидев возле обочины раскидистый дуб, он уже заранее знает, что далее последует крутой поворот вправо и необходимо притормозить, хотя сам поворот находится вне пределов видимости. Или разглядев на обочине другой хорошо запоминающийся объект, может заранее предположить, что впереди особых препятствий не предвидится, а потому можно прибавить скорость.

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

А теперь возьмём алгоритм машинного обучения, который решает задачу, минимизируя эмпирический риск. Вполне понятно, что алгоритм, как и человек попросту вызубрит не только те признаки которые отвечают решению задачи, но и шпаргалки, т. е. незначимые для решения задачи факторы, но помогающие ему обладать повышенными прогнозирующими способностями. Если переобученному таким образом алгоритму дать выборку с примерами, которые ранее в процессе обучения не встречались, но в той или иной степени похожи, то в отличие от человека, компьютер не сможет определиться, что он имеет дело с другой выборкой и по прежнему будет интерпретировать незначимые факторы, предполагая, что с помощью них он сможет «предсказать» результат, который по его мнению, вроде бы должен является «решением». И попадёт впросак, т. е. начнёт давать неверные ответы.

Если такой алгоритм переобучить на какой нибудь трассе вождению транспортного средства на автопилоте, то на любой другой трассе, он бы начал вести себя неадекватно, т. е. прибавлять скорость, там где нужно притормаживать и притормаживать, там где отсутствуют видимые препятствия. В результате чего такое «вождение» приведёт, как минимум, к провоцированию аварийных ситуаций и, как максимум, закончится дорожно-транспортным происшествием.

Теоретически суть вроде бы понятна. Чтобы алгоритм обобщал только то, что значимо, т. е. относится к задаче, необходимо:

  1. Снизить ему возможность для зубрёжки, т. е. оградить от возможности воспользоваться шпаргалками для построения модели
  2. Вынудить принимать более осторожные решения.

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

Как работает такой алгоритм обучения с оппонентом:

  1. Алгоритм выдвигает некую гипотезу, т. е. слегка изменяет весовой коэффициент искусственного нейрона для какого нибудь одного фактора
  2. Оппонент предъявляет алгоритму пример из обучающей выборки, наименее соответствующий  последней выдвинутой гипотезе.
  3. Алгоритм слегка корректирует весовой коэффициент для одного из факторов таким образом, чтобы улучшить гипотезу для всех ранее предъявленных оппонентом примеров.
  4. Возврат к п. 2.

Такой алгоритм называется минимаксной стратегией и его эффективность доказана теоремой фон Неймана — Моргенштерна (Математическая теория некооперативных антагонистических игр для двух лиц с нулевой суммой).

Суть в том, что оппонент будет предъявлять алгоритму только те примеры, с которыми  тот справляется хуже всего. Вполне понятно, что в таком случае, примеры, на которых алгоритм мог бы переобучиться, т. е. воспользоваться шпаргалками для выдвижения наиболее смелых гипотез, в число предъявляемых не попадут. А поскольку, будут предъявляться только те примеры, для которых необходимы наиболее скромные гипотезы, то переобучение сведётся к минимуму.

Комментариев нет:

Отправить комментарий