Мысли и теория
Путеводитель по ядрам для не математиков
Совершите путешествие в бесконечность, не выходя из комнаты
Я часто черпаю вдохновение в реальности и в том, насколько мы, люди, приспособлены (хотя и несовершенно), из математики. День, когда я понял, что на самом деле ядра делают для меня, остался среди тех памятных моментов трепета.
Специалисты по обработке данных и преподаватели машинного обучения наверняка знакомы с концепцией трюка с ядром. Они изучали это, часто понимали это, даже на секунду, а затем быстро отложили это в глубине души. Существуют десятки технических статей и сообщений о ядрах и их значении для специалиста по данным. Но их красота, элегантность и интуиция, которую его использование может дать нематематикам о силе символического мышления, убедили меня, что мне стоит написать «Туристический путеводитель по ядрам для нематематиков».
Хотя я постараюсь по возможности свести к минимуму математический жаргон, за счет не строгости (пожалуйста, простите меня), это путешествие требует некоторого терпения. Поверьте, это будет вознаграждено.
Если вы думаете, что не можете линейно разделить набор объектов, вы просто не смотрите на него с правильной точки зрения
Представьте, что вы стоите перед киоском, чтобы забрать свой (до пандемии) билет на концерт, и что очередь состоит из вас, немногих ваших друзей впереди и позади вас и кучки других людей, которых вы не знаете.
Теперь, с вашей точки зрения, невозможно провести черту, отделяющую ваших друзей от остальной группы. Предполагая, что вы все выстроились в очередь аккуратно и аккуратно, вы не увидите ничего, кроме того, кто отстает, а кто впереди. Но если бы вы были на втором этаже здания, выходящего на ту же линию, упражнение было бы очень легким; сверху вы будете четко видеть, где останавливаются ваши друзья и начинается остальная часть очереди.
Другими словами, то, что для вас, расплющенного на двухмерной стоянке вместе с остальными, выглядит как точка впереди и точка позади, для наблюдателя над вами, живущего в трехмерном здании, выглядит хорошо упорядоченным. линия на цокольном этаже. И этому человеку довольно легко провести еще одну, воображаемую линию, отделяющую друзей от незнакомцев. Это преобразование размеров - это то, что математики называют добавлением дополнительной функции, чтобы сделать набор данных линейно разделяемым.
Уловка работает от двух до трех измерений, от трех до четырех и от четырех до пяти миллионов. Не изобретая ничего, а просто преобразуя имеющуюся у вас информацию о группе объектов, добавляя новые измерения или координаты для этих объектов, вы можете практически линейно разделить любую группу.
Приведу еще два примера.
На диаграмме слева вы видите облако точек, живущих в двухмерном пространстве, которое никогда не может быть линейно разделимым (в этом пространстве). Другими словами, линия обязательно прорежет некоторые красные или зеленые точки, не отделяя красные от зеленых. Но посмотрите, что происходит с правой стороны: перенося эти данные из двухмерного в трехмерное пространство благодаря некоторому преобразованию признаков, можно было бы идеально нарисовать линию (или, лучше сказать, плоскость). разделите две группы. Вернувшись в исходное двухмерное пространство, эта же плоскость будет выглядеть как закругленная линия, очерчивающая красные точки и отделяющая их от зелени. Это опять же вопрос перспективы.
Что означает преобразование элементов? Математики говорят о преобразовании элементов, потому что при переносе из двухмерного в трехмерное пространство ничего не было добавлено, а просто были увеличены некоторые внутренние характеристики. В математике преобразование можно описать следующим образом. Каждая точка в двумерном пространстве может быть представлена вектором координат x = {x₁, x₂}. Функция преобразования признаков ϕ (x) объединяет эти две координаты и вместо них выдает три координаты: ϕ (x) = {x²₁, √2x₁x₂, x²₂}. График справа отображает все точки x в новом пространстве благодаря ϕ (x).
Второй и последний пример немного менее интуитивно понятен, но дает нам представление о том, насколько мощным может быть преобразование дискретных функций в (гораздо) более высокое размерное пространство. В этом случае ϕ расширяет возможности двумерного пространства в более многомерное (не обманывайтесь кубом, мы просто не можем представить многие измерения на картинке). Где-то в этом гипотетическом пространстве гораздо более высокой размерности данные все еще линейно разделены гиперплоскостью гораздо более высокой размерности - в этом вы должны мне поверить. Эта гиперплоскость, сплющенная в двух измерениях нашего бумажного листа, выглядит как линия, огибающая красные точки.
Когда вы думаете, что явление слишком размыто, чтобы его можно было четко понять и классифицировать, возможно, вы просто не можете взглянуть на всю информацию с точки зрения, достаточно сложной, чтобы понять ее.
Ничего страшного, но что такое ядро?
Потерпи меня еще немного. Оказывается, выполнение вычислений в этом многомерном пространстве значительно усложняет задачу. Информация, которую вы обычно хотите обработать (и разделить), намного сложнее, чем точка с двумя координатами, то есть она уже находится в многомерном пространстве. Например, изображение состоит из тысяч или миллионов пикселей, каждый из которых представляет координату. Проецирование этих многомерных объектов во вселенную с еще большим количеством измерений делает каждую операцию между этими объектами чрезвычайно дорогостоящей, и вы не удивитесь, узнав, что машинное обучение требует большого количества вычислений, включающих миллионы фрагментов данных, которые уже имеют невероятные возможности. ряд отличительных черт.
В машинном обучении (или, точнее, в линейной классификации SVM) одна из наиболее типичных операций, которые нам нужно выполнить, называется точечное (или внутреннее) произведение и включает в себя умножение каждой координаты объекта на одну и ту же координату. другого, а затем суммировать результат всех этих продуктов. Возвращаясь к нашему первому примеру, скалярное произведение (транспонировать - игнорировать) x = {x₁, x₂} и y = {y₁, y₂} будет ( x₁y₁ + x₂y₂). Это скалярное произведение включало 3 операции, 2 умножения и суммирование, чтобы получить результат. Вместо этого выполняется скалярное произведение тех же объектов в их новом трехмерном пространстве ϕ (x) = {x²₁, √2x₁x₂, x²₂} и ϕ (y) = { y²₁, √2y₁y₂, y²₂} будет более затратным (x²₁y²₁ + 2x₁y₁x₂y₂ + x²₂y²₂), включая несколько операций преобразования, умножения и суммирования.
В пространствах с гораздо более высокой размерностью, в которых обычно работают машины, эта разница в сложности огромна, что часто делает такие преобразования невозможными в нашей жизни. Именно здесь нам (наконец) на помощь приходит так называемый трюк с ядром. Фактически ядро - это функция, способная вычислять скалярное произведение между ϕ (x) и ϕ (y) на основе только исходных векторов x и y, следовательно, без необходимости вычислять (или даже знать) преобразование ϕ. Можно доказать (теорема Мерсера), что при некоторых математических условиях такая функция K (x, y) существует всегда.
В нашем конкретном примере функция K (x, y) = (xᵗ ∙ y) ², то есть квадрат скалярного произведения между исходные векторы x и y (верхний индекс t над x означает транспонированный , это просто сложность из-за матричной алгебры, и вы можете с радостью ее проигнорировать), в точности равно скалярному произведению между ϕ (x) и ϕ (y ) мы рассчитали ранее. Однако разница в том, что для вычисления K (x, y) нам нужно 4 операции (2 умножения и суммирование для скалярного произведения плюс квадрат числа ), и ничего более.
То, что произошло, сначала может показаться невинным, но на самом деле оно мощно. Концептуально представляя функцию, работающую в нашем первоначальном пространстве, мы можем получить все преимущества работы вместо этого в многомерном пространстве, даже не посещая такое пространство и не беспокоясь о связанной с ним сложности.
Но позвольте мне расширить это, если вам все еще нужны убедительные доказательства.
Возьмем функцию ядра ниже, так называемое ядро Гаусса.
K (x, y) = exp (-γ ∥ x - y ∥²)
Можно доказать, что обработка функции K (x, y), т. Е. Выполнение простых вычислений в исходном дискретном пространстве, где x и y live, равносильно проецированию x и y в бесконечномерное пространство и вычислению скалярного произведения этих преобразований. Если предыдущий пример вас не впечатлил, попробуйте сейчас сравнить количество операций, необходимых для решения этой функции ядра, с вычислением бесконечного числа преобразований, за которыми следует бесконечное число умножений и бесконечное количество суммирований.
Наша способность мыслить концептуально, не связанная ограничениями времени и пространства, дала нам возможность наслаждаться на наших столах или через наши экраны всеми практическими преимуществами бесконечного путешествия в неизведанное.
