Уравнение гиперплоскости отделяющей точку от множества

Видео:1. Уравнение плоскости проходящей через точку перпендикулярно вектору / общее уравнение / примерыСкачать

1. Уравнение плоскости проходящей через точку перпендикулярно вектору / общее уравнение / примеры

Геометрия машинного обучения. Разделяющие гиперплоскости или в чём геометрический смысл линейной комбинации?

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

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

Видео:Такие разные бесконечности. Счётные и несчётные множества | матан #005 | Борис Трушин !Скачать

Такие разные бесконечности. Счётные и несчётные множества | матан #005 | Борис Трушин !

Модельный пример

Чтобы теория не отрывалась от реальных кейсов, возьмём в качестве примера задачу бинарной классификации. Есть датасет: m образцов, каждый образец — n-мерная точка. Для каждого образца мы знаем к какому классу он относится (зелёный или красный). Также известно, что датасет является линейно разделимым, т.е. существует n-мерная гиперплоскость такая, что зелёные точки лежат по одну сторону от неё, а красные — по другую.

Уравнение гиперплоскости отделяющей точку от множества

К решению задачи поиска такой гиперплоскости можно подходить разными способами, например с помощью логистической регрессии (logistic regression), метода опорных векторов с линейным ядром (linear SVM) или взять простейшую нейросеть:

Уравнение гиперплоскости отделяющей точку от множества

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

Видео:21.09.2022 Практика 3. Открытые и замкнутые множества, R^nСкачать

21.09.2022 Практика 3. Открытые и замкнутые множества, R^n

От прямой линии до гиперплоскости

Рассмотрим подробную математику для прямой. Для общего случая гиперплоскости в n-мерном пространстве будет всё ровно тоже самое, с поправкой на количество компонент в векторах.

Уравнение гиперплоскости отделяющей точку от множества

Прямая линия на плоскости задаётся тремя числами — Уравнение гиперплоскости отделяющей точку от множества:

Уравнение гиперплоскости отделяющей точку от множества

Уравнение гиперплоскости отделяющей точку от множества

Уравнение гиперплоскости отделяющей точку от множества

Первые два коэффициента Уравнение гиперплоскости отделяющей точку от множествазадают всё семейство прямых линий, проходящих через точку (0, 0). Соотношение между Уравнение гиперплоскости отделяющей точку от множестваи Уравнение гиперплоскости отделяющей точку от множестваопределяет угол наклона прямой к осям.

Если Уравнение гиперплоскости отделяющей точку от множества, получаем линию, идущую под углом 45 градусов (Уравнение гиперплоскости отделяющей точку от множества) к осям Уравнение гиперплоскости отделяющей точку от множестваи Уравнение гиперплоскости отделяющей точку от множестваи делящую первый/третий квадранты пополам.

Ненулевой коэффициент Уравнение гиперплоскости отделяющей точку от множествапозволяет линии не проходить через ноль. При этом наклон к осям Уравнение гиперплоскости отделяющей точку от множестваи Уравнение гиперплоскости отделяющей точку от множестване меняется. Т.е. Уравнение гиперплоскости отделяющей точку от множествазадаёт семейство параллельных линий:

Геометрический смысл вектора Уравнение гиперплоскости отделяющей точку от множества— это нормаль к прямой Уравнение гиперплоскости отделяющей точку от множества:

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

P.S. Понятно, что таких нормалей бесконечно много, как и троек (w1, w2, b) задающих прямую. Если все три числа умножить на ненулевой коэффициент Уравнение гиперплоскости отделяющей точку от множества— прямая останется той же.

В общем случае n-мерного пространства, Уравнение гиперплоскости отделяющей точку от множествазадаёт n-мерную гиперплоскость.

Уравнение гиперплоскости отделяющей точку от множества

Уравнение гиперплоскости отделяющей точку от множества

Уравнение гиперплоскости отделяющей точку от множества

Видео:Окрестность точкиСкачать

Окрестность точки

Геометрический смысл линейной комбинации

Если точка Уравнение гиперплоскости отделяющей точку от множествалежит на гиперплоскости, то

Уравнение гиперплоскости отделяющей точку от множества

А что происходит с этой суммой, если точка не лежит на плоскости?

Гиперплоскость делит гиперпространство на два гиперподпространства. Так вот точки, находящиеся в одном из этих подпространств (условно говоря «выше» гиперплоскости), и точки, находящиеся в другом из этих подпространств (условно говоря «ниже» гиперплоскости), будут в этой сумме давать разный знак:

Уравнение гиперплоскости отделяющей точку от множества0$» data-tex=»inline»/> — точка лежит «выше» гиперплоскости

Уравнение гиперплоскости отделяющей точку от множества— точка лежит «ниже» гиперплоскости

Это очень важное наблюдение, поэтому предлагаю его перепроверить простым кодом на Python:

Нужно понимать, что «выше» и «ниже» здесь — понятия условные. Это специально отражено в примере — зелёные точки оказываются визуально ниже. С геометрической точки зрения направление «выше» для данной конкретной линии определяется вектором нормали. Куда смотрит нормаль, там и верх:

Т.о. знак линейной комбинации позволяет отнести точку к верхнему или нижнему подпространству.

А значение? Значение (по модулю) определяет удалённость точки от плоскости:

Уравнение гиперплоскости отделяющей точку от множества

Т.е. чем дальше от плоскости находится точка, тем больше будет значение линейной комбинации для неё. Если зафиксировать значение линейной комбинации, получим точки, лежащие на прямой, параллельной исходной.

Опять же, наблюдение важное, поэтому перепроверяем:

Выводы

  • Линейная комбинация позволяет разделить n-мерное пространство гиперплоскостью.
  • Точки по разные стороны гиперплоскости будут иметь разный знак линейной комбинации Уравнение гиперплоскости отделяющей точку от множества.
  • Чем точка удалённее от гиперплоскости, тем абсолютное значение линейной комбинации будет больше.

С точки зрения бинарной классификации последнее утверждение можно переформулировать следующим образом. Чем удалённее точка от гиперплоскости, являющейся границей решений (decision boundary), тем увереннее мы в том, что наш образец (sample) определяемый этой точкой попадает в тот или иной класс.

Видео:Множества и операции над множествамиСкачать

Множества и операции над множествами

Близко и далеко: это как?

Близко и далеко — понятия сугубо субъективные. А при классификации отвечать нам нужно чётко — либо деталь годится для строительства ракеты для полёта на Марс, либо это брак. Либо человек кликнет по рекламе, либо нет. Возможно ответить с долей уверенности — дать вероятность позитивного (true) исхода.

Для этого к линейной комбинации можно применить функцию активации (в терминологии нейросетей).

Если применить логистическую функцию (график смотри ниже):

Уравнение гиперплоскости отделяющей точку от множества

получаем на выходе вероятности и такую картинку:

Красные — точно нет (false, точно брак, точно не кликнет). Зелёные — точно да (true, точно годится, точно кликнет). Всё, что в определённом диапазоне близости от гиперплоскости (граница решений) получает некоторую вероятность. На самой прямой вероятность ровно 0.5.

P.S. «Точно» здесь определяется как меньше 0.001 или больше 0.999. Сама логистическая функция стремится к нулю на минус бесконечности и к единице на плюс бесконечности, но никогда этих значений не принимает.

N.B. Обратите внимание, что данный пример лишь демонстрирует каким образом можно ужать (squashing) расстояние со знаком в интервал вероятностей Уравнение гиперплоскости отделяющей точку от множества. В практических задачах для поиска оптимального отображения используется калибровка вероятностей. Например, в алгоритме шкалирования по Платту (Platt scaling) логистическая функция параметризуется:

Уравнение гиперплоскости отделяющей точку от множества

и затем коэффициенты Уравнение гиперплоскости отделяющей точку от множестваи Уравнение гиперплоскости отделяющей точку от множестваподбираются машинным обучением. Подробнее смотрите: binary classifier calibration, probability calibration.

Видео:Операции над множествамиСкачать

Операции  над  множествами

В каком мы пространстве? (полезное умозрительное упражнение)

Казалось бы понятно — мы в пространстве данных Уравнение гиперплоскости отделяющей точку от множества(data space), в котором лежат образцы Уравнение гиперплоскости отделяющей точку от множества. И ищем оптимальное разделение плоскостью, определяемой вектором Уравнение гиперплоскости отделяющей точку от множества.

Уравнение гиперплоскости отделяющей точку от множества0$» data-tex=»inline»/> для зелёных точек
Уравнение гиперплоскости отделяющей точку от множествадля красных точек

Но в нашей задаче бинарной классификации образцы зафиксированы, а веса меняются. Соответственно мы можем всё переиграть, перейдя в пространство весов Уравнение гиперплоскости отделяющей точку от множества(weight space):

Уравнение гиперплоскости отделяющей точку от множества

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

При обучении модели удобнее рассуждать в пространстве весов, т.к. обновляются веса, а вектора-образцы из тренировочного набора задают нормали к гиперплоскостям. Например:

Предположим, что образцу Уравнение гиперплоскости отделяющей точку от множествасоответствует зелёный класс, соответствующий неравенству:

Уравнение гиперплоскости отделяющей точку от множества0$» data-tex=»inline»/>

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

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

Уравнение гиперплоскости отделяющей точку от множества, где Уравнение гиперплоскости отделяющей точку от множества0$» data-tex=»inline»/>

с некоторой «скоростью» Уравнение гиперплоскости отделяющей точку от множества. Тем самым на следующем шаге предсказание будет либо верным, либо менее неверным, т.к. слагаемое Уравнение гиперплоскости отделяющей точку от множества, сонаправленное с нормалью, «довернёт» вектор весов в зелёную область.

Видео:✓ Предел последовательности | матан #006 | Борис ТрушинСкачать

✓ Предел последовательности | матан #006 | Борис Трушин

Практика. Обучаем персептрон

Для решения задачи бинарной классификации в случае линейной разделимости образцов можно обучить простейший персептрон, устроенный по такой схеме:

Уравнение гиперплоскости отделяющей точку от множества

Эта конструкция реализует ровно тот принцип, который был описан выше. Вычисляется линейная комбинация:

Уравнение гиперплоскости отделяющей точку от множества

По значению которой решатель (decision unit) принимает решение отнести образец к одному из двух классов по следующему принципу:

Уравнение гиперплоскости отделяющей точку от множествакласс +1 (зелёные точки)
Уравнение гиперплоскости отделяющей точку от множествакласс -1 (красные точки)

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

Вычисляется предсказание (predicted label). Если оно не совпадает с реальным классом, то веса обновляются по следующему принципу:

Уравнение гиперплоскости отделяющей точку от множества

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

  • Доворачиваем вектор-вес в сторону верного класса: по нормали Уравнение гиперплоскости отделяющей точку от множествав случае класса +1; против нормали Уравнение гиперплоскости отделяющей точку от множествав случае класса -1. (Сама нормаль всегда смотрит в сторону класса +1.)
  • Обновляем смещение по аналогичному принципу.

Вот что получается:

Заглянем теперь в пространство весов Уравнение гиперплоскости отделяющей точку от множества(weight space):

Красные и зелёные линии — это исходные образцы, синяя точка — итоговый вес.

А какие ещё веса дают верную классификацию? Смотрим:

Красные и зелёные линии — это исходные образцы, синяя точка — итоговый вес, фиолетовые точки — другие возможные веса.

И выворачиваем всё наизнанку ещё раз, переходя опять в пространство данных Уравнение гиперплоскости отделяющей точку от множества(data space):

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

Упражнение (простое): На последней иллюстрации четыре характерных пучка линий. Найдите их среди фиолетовых точек в пространстве весов.

Видео:Математика без Ху!ни. Непрерывность функции, точки разрыва.Скачать

Математика без Ху!ни. Непрерывность функции, точки разрыва.

От автора

Спасибо всем хабровчанам за критические отзывы касательно первой версии статьи, в том числе yorko, который вместе с сообществом Open Data Science делает суперский открытый курс по машинному обучению — всем рекомендую.

Стало понятно, что материалу не хватает финального штриха и статья была отправлена на доработку. Вторая (она же текущая) версия дополнена примером обучения персептрона.

Видео:Задача 8. Написать уравнение плоскости, проходящей через точку перпендикулярно вектору.Скачать

Задача 8. Написать уравнение плоскости, проходящей через точку перпендикулярно вектору.

Итоги

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

    Geoffrey Hinton. An overview of the main types of neural network architecture
    Подробнее про обучение персептрона с переходом в пространство весов от гуру нейронных сетей Джеффри Хинтона.

Supervised Learning / Support Vector Machines
Про решение задач бинарной классификации методом опорных векторов и как с точки зрения этого алгоритма выбрать оптимальную разделяющую плоскость.

Hyperplane based сlassification: Perceptron and (Intro to) Support Vector Machines
Опять про персептроны, вскользь про метод опорных векторов. Детально рассматривается вопрос обучения и корректировки весов.

Polyhedra and Linear Programming. Polyhedra, Polytopes, and Cones
Линейная алгебра линейных комбинаций (теория) с множеством иллюстративных примеров.


источники:

🎥 Видео

Множества на комплексной плоскости. Связное множество. Односвязная область. Граница. Круг сходимостиСкачать

Множества на комплексной плоскости. Связное множество. Односвязная область. Граница. Круг сходимости

Изобразить область на комплексной плоскостиСкачать

Изобразить область на комплексной плоскости

17. Показать что прямые пересекаются и составить уравнение плоскости в которой они расположеныСкачать

17. Показать что прямые пересекаются и составить уравнение плоскости в которой они расположены

Уравнение, которое меняет взгляд на мир [Veritasium]Скачать

Уравнение, которое меняет взгляд на мир [Veritasium]

Графический метод решения задачи линейного программирования (ЗЛП)Скачать

Графический метод решения задачи линейного программирования (ЗЛП)

Семинар 4. Выпуклость. Выпуклые множества. Выпуклые функции. Критерии выпуклости. МФТИ 2022.Скачать

Семинар 4. Выпуклость. Выпуклые множества. Выпуклые функции. Критерии выпуклости. МФТИ 2022.

Круги Эйлера. Логическая задача на множества. Иностранные языкиСкачать

Круги Эйлера. Логическая задача на множества. Иностранные языки

Математика это не ИсламСкачать

Математика это не Ислам

Математика без Ху!ни. Комплексные числа, часть 1. Введение.Скачать

Математика без Ху!ни. Комплексные числа, часть 1. Введение.

Методы Оптимизации. Семинар 3. Выпуклые множестваСкачать

Методы Оптимизации. Семинар 3. Выпуклые множества

Семинар 3. Выпуклость. Выпуклые множества. Выпуклые функции. МФТИ. 2022Скачать

Семинар 3. Выпуклость. Выпуклые множества. Выпуклые функции. МФТИ. 2022
Поделиться или сохранить к себе: