Что общего между сжатием изображений, поиском скрытых сообществ в соцсетях и тем, как Google ранжирует страницы? Всё это основано на одной красивой математической идее — собственных векторах и собственных значениях.
*https://www.youtube.com/watch?v=Y_HqYTheDKk
**https://300.ya.ru/v_chVkRJyy
таймкоды
00:00:00 Введение в собственные векторы
- Собственные векторы применяются в сжатии изображений, ранжировании страниц Google и поиске сообществ в социальных сетях.
- Проблема «проклятия размерности» в машинном обучении: как разобраться в данных с множеством признаков?
- Собственные векторы помогают сжать информацию, оставив только суть.
00:01:13 Определение собственных векторов
- Линейное преобразование изменяет длину и направление векторов.
- Собственные векторы сохраняют направление после преобразования, но могут измениться в длине.
- Собственное значение — это коэффициент, показывающий, во сколько раз вектор сжался или растянулся.
00:01:45 Формула собственных векторов
- Формула: матрица A * вектор B = lambda * вектор B.
- Вектор B является собственным для преобразования A с собственным значением lambda.
00:02:44 Метод главных компонент
- Применение собственных векторов для борьбы с «проклятием размерности».
- Использование дисперсии и ковариации для анализа данных.
- Ковариационная матрица описывает форму и ориентацию облака данных.
00:05:12 Ранжирование страниц в Google
- Страницы ранжируются на основе ссылок других важных страниц.
- Система ссылок представлена как матрица, а важность страниц — как вектор.
- Главный собственный вектор матрицы ссылок определяет порядок выдачи страниц в Google.
00:07:43 Спектральная кластеризация
- Представление данных как графа друзей в социальной сети.
- Матрица Лапласа описывает связи между точками данных.
- Второй по малости собственный вектор матрицы Лапласа находит естественный разрез в сети.
00:11:13 История распознавания лиц
- В начале 90-х годов учёные искали способ научить компьютер распознавать лица.
- Каждое лицо представлялось как коктейль из базовых шаблонов.
- Собственные векторы лиц «айгенфейсис» позволили эффективно сравнивать лица.
- Уникальная подпись каждого человека сравнивалась с подписями в базе данных, что было в тысячи раз эффективнее, чем сравнение по пикселям.
00:13:11 Итоги и призыв к действию
- Подведение итогов видео.
- Призыв заплатить за проезд, поставить лайк и подписаться на канал.
In this video
Зачем ML-инженеру знать линейную алгебру
0:00
Что общего между сжатием изображений,
0:02
тем, как Google ранжирует страницы, и
0:05
поиском скрытых сообществ в социальных
0:07
сетях? Ответ: — одна красивая
0:10
математическая идея, которой уже более
0:12
100 лет. Сегодня поговорим про
0:15
собственные векторы в машинном обучении.
0:17
Всем привет. Меня зовут Андрей Жогов. Я
0:20
работаюнженером в Сбере и преподаю
0:23
машинное обучение студентам Афисте. В
0:26
машинном обучении мы постоянно работаем
0:28
с данными, в которых десятки, сотни, а
0:31
то и тысячи признаков. Представьте себе
0:33
Excel-таблицу с пятьюстами столбцов. Как
0:37
в этом разобраться? Как в этом хаосе
0:39
найти самые важные закономерности, не
Интуитивное объяснение собственных векторов и значений
0:42
утонув в шуме? Эта проблема называется
0:44
проклятием размерности. Поэтому нам
0:47
нужен эффективный способ как-то сжать
0:49
всю эту информацию, чтобы оставить
0:51
только самую суть. И чтобы теория не
0:53
была такой сухой, наконец видео я
0:56
приберёг очень забавную историю про то,
0:59
как однажды собственные векторы во время
1:01
распознавания лиц превращали лица в лица
1:05
призраков. Поэтому обязательно
1:07
досмотрите это видео до конца. Будет
1:09
много всего интересного. Поехали.
1:13
Итак, давайте представим, что у нас есть
1:15
какая-то плоскость с векторами. И мы
1:17
применяем к этой плоскости какое-то
1:19
линейное преобразование. Например,
1:22
растягиваем по диагонали. Большинство
1:24
векторов после этого преобразования
1:26
изменят как свою длину, так и своё
1:29
направление, как показано на рисунке. Но
1:31
есть особенные векторы, которые после
1:35
преобразования не меняют своего
1:37
направления. Они могут только либо
1:39
сжаться, либо растянуться. Эти особенные
1:42
векторы и называются собственными.
1:45
Поехали дальше. У каждого собственного
1:47
вектора есть своё собственное значение.
1:50
Что это такое? Собственное значение —
1:53
это просто коэффициент, который
1:55
показывает, во сколько раз вектор сжался
1:58
или растянулся. То есть собственный
2:00
вектор — это направление, а коэффициент
2:04
или собственное значение — это важность
2:06
этого направления. Как всё, что я тут
2:09
наговорил, записать математически? Дело
2:11
в том, что в линейной алгебре любое
2:13
преобразование — это матрица. Поэтому
PCA: сжатие данных и борьба с проклятием размерности
2:15
наша идея записывается очень простой
2:18
формулой. Матрица А, умноженная на
2:20
вектор V, равно лямбда умноженная на
2:23
вектор V. Она читается так: применить к
2:26
вектору V преобразование А — это то же
2:29
самое, что просто умножить вектор V на
2:32
число лямбда. Если приглядеться к этой
2:34
формуле, то становится понятно, что это
2:37
и есть определение того, что вектор V
2:39
является собственным для преобразования
2:42
а собственным значением лямбда. А теперь
2:45
поговорим про применение нашей идеи. И
2:48
первое применение — метод главных
2:50
компонент. Это, пожалуй, самое
2:52
классическое применение собственных
2:54
векторов ВМ для борьбы с проклятием
2:57
размерности. Представьте, что у вас есть
3:00
облако данных. Например, информация о
3:03
тысячах домов, где признаки — это
3:05
количество комнат, площадь, удалённость
3:08
от центра, количество минут пешком до
3:11
метро и так далее. И мы хотим как-то
3:14
сжать эти данные, оставив только саму
3:17
суть. Как это работает? Сначала нам
3:19
нужно понять, как данные расположены
3:22
друг относительно друга в пространстве.
3:24
В этом нам помогут дисперсия и
3:27
ковариация. Дисперсия говорит нам о том,
3:30
насколько сильно разбросаны данные по
3:33
одному признаку. Для примера давайте
3:36
посмотрим на иллюстрацию двух мишеней.
3:38
На левой мишени разброс попаданий явно
3:41
больше, чем на правой. Значит, и
3:43
дисперсия в левом случае будет больше,
3:46
чем в правом. Есть и второй параметр,
3:49
ковариация. Она говорит нам, насколько
3:52
два признака связаны друг с другом.
3:54
Например, площадь дома и его цена имеют
3:57
положительную ковариацию. Когда растёт
3:59
одно, тогда, скорее всего, растёт и
4:02
другое. Соберём эти два понятия в
4:05
ковареционную матрицу. Это просто
4:07
табличка, которая собирает дисперсию и
4:10
ковариацию в одном месте. На её
4:12
диагонали находятся дисперсии каждого
4:15
признака, а в остальных ячейках попарные
4:18
ковывариации между всеми признаками. По
4:20
сути, эта матрица является неким
4:22
математическим паспортом формы и
4:25
ориентации нашего облака данных. После
4:27
этого давайте найдём собственные векторы
4:30
и собственные значения этой матрицы.
4:32
Тогда собственные векторы покажут нам
PageRank: как Google использовал собственные векторы
4:35
новые оси, вдоль которых будет
4:38
наибольший разброс данных. А собственные
4:40
значения покажут, насколько велик этот
4:43
разброс. Самое большое значение лямбда
4:46
соответствует самой важной компоненте.
4:49
Ну и теперь мы просто берём две или три
4:52
компоненты с наибольшим значением
4:54
лямбда, а остальные откидываем.
4:57
Поздравляю, мы сжали данные, сохранив
5:00
максимум доступной информации. А теперь
5:02
пример, который в своё время изменил
5:05
весь интернет. Как поисковик решает,
5:07
какая страница самая авторитетная? Всё
5:10
гениально и просто. Страница считается
5:13
важной, если на неё ссылаются другие
5:15
важные страницы. Заметьте, это
5:18
рекурсивное определение. Как же нам это
5:20
посчитать? Представим это как систему
5:23
голосования. Каждая ссылка с одной
5:26
страницы на другую — это голос. Но вес
5:29
голоса не одинаков. голос какой-нибудь
5:32
важной страницы типа Википедии гораздо
5:35
важнее, чем голос страницы какого-то не
5:38
очень известного блога. При этом, если
5:40
Википедия ссылается на 100 различных
5:43
страниц, то давайте считать, что этот
5:45
авторитет делится между этими 100
5:48
страницами. А если она ссылается только
5:51
на один сайт, то ему она отдаёт весь
5:54
свой авторитет. А теперь магия линейной
5:56
алгебры. Всю эту гигантскую паутину
5:59
ссылок можно представить в виде огромной
6:01
матрицы L, где итый житый элемент
6:04
матрицы — это вес, отданный сайтом G
6:07
сайту и. А важность всех страниц в
6:09
интернете можно представить в виде
6:11
одного длинного вектора R, где каждая
6:14
компонента — это рейтинг конкретной
6:16
страницы. Теперь мы ищем такой
Спектральная кластеризация: поиск скрытых сообществ в данных
6:19
стабильный вектор рейтингов R, чтобы
6:21
выполнялось следующее условие. Если мы к
6:24
нему применим нашу матрицу ссылок L, то
6:26
есть по сути совершим один раунд
6:28
голосования, то вектор R не должен
6:31
измениться. Относительная важность всех
6:34
ссылок останется прежней, и система
6:36
придёт в равновесие. Математически это
6:38
записывается так: L у вектор R равно
6:42
вектор R. Стоп. Это же в точности наша
6:46
формула для собственного вектора. Только
6:48
теперь матрица А — это у нас матрица
6:50
ссылок L. Собственный вектор — это
6:54
вектор R, а лямбда просто равно единице.
6:57
Итоговый вектор, который определяет
6:59
порядок выдачи страниц в поисковике
7:01
Google- это и есть главный собственный
7:04
вектор матрицы ссылок. По сути, вся
7:07
магия аранжирования в поисковике Google
7:10
была построена на поиске одного, но
7:12
самого главного вектора в матрице ссылок
7:15
L. Конечно, это немного упрощённая
7:18
картина. Мы сознательно упускаем
7:20
некоторые математические детали.
7:22
Например, почему этот итерационный
7:25
процесс голосования вообще работает? Что
7:29
именно означает главный собственный
7:31
вектор и почему мы гарантированно найдём
7:34
именно его. Но поскольку это не основная
7:36
тема нашего видео, мы оставим этот
7:39
момент для вдумчивых читателей. Вот
7:42
ссылка специально для вас. Поговорим
7:44
теперь о применении собственных векторов
7:46
в спектральной кластеризации. Что
7:49
делать, если ваши данные имеют сложную
7:52
формулу, например, форму двух
7:54
переплетённых полумесяцев, где методы по
7:58
типу comс не справляются с задачей?
8:00
Давайте опишем алгоритм, как действовать
8:03
в данном случае. Шаг один: посмотреть на
8:06
данные как носеть друзей. Спектральная
8:08
кластеризация использует очень красивый
8:11
подход. Она говорит: «Давайте забудем
8:13
про координаты и про центры. Давайте
8:15
лучше представим наши данные как друзей
8:18
в социальной сети. Будем предполагать,
8:20
что близкие точки — это друзья, а
8:23
далёкие точки — это незнакомцы. Так, мы
8:26
превращаем наше облако точек в граф.
8:29
Задача кластеризации теперь звучит
8:31
иначе. Найти группы друзей, которые
8:34
плотно связаны между собой, но слабо
8:37
связаны с другими группами. Шаг два.
8:39
Описать эту сеть с помощью матрицы
8:41
Лапласа. Как и в методе главных
8:43
компонент, нам нужна матрица, которая
8:45
описывает наши данные. И для графов
8:48
существует специальная матрица, которая
8:50
называется матрицей Лапласа. Не вдаваясь
8:53
в сложные детали, эта матрица кодирует,
8:56
какие точки с какими соединены и сколько
8:59
у каждой точки друзей. Ну и, наконец,
9:01
шаг номер три. Найти естественный разрез
9:05
с помощью собственных векторов.
9:07
Оказывается, у матрицы Лапласа есть
9:09
волшебное свойство. Если найти её второй
9:12
по малости собственный вектор, кстати,
9:15
он даже имеет специальное название
9:17
вектор Фидлера, то его компоненты
9:19
идеально решат нашу задачу. Этот вектор
9:22
для каждой точки данных выдаст одно
9:25
число. И окажется, что у точек из одного
9:27
плотного кластера это число окажется
9:30
положительным, а у точек из другого
9:32
кластера отрицательным. Нам остаётся
9:35
посмотреть на знак числа для каждой
9:37
точки и разделить по этому числу точки
9:40
на два кластера. Собственный вектор в
9:43
нашей задаче здесь находит буквально
9:46
самый естественный разрез в нашей сети
9:48
друзей.
9:51
Сейчас у вас есть выбор. Продолжить
9:53
собирать знания по крупицам, по
9:56
кусочкам, по отдельным роликам на Ютюбе,
9:58
по отдельным статьям в разных местах
10:00
интернета или пойти по понятному
10:02
маршруту. который приведёт вас к нужным
10:06
вам знаниям, то есть присоединиться к
10:08
нашим курсам, опять-таки воспользоваться
10:11
помощью опытных менторов, влиться в
10:14
сообщество профессионалов, работающих в
10:17
лидерах индустрии по теме искусственного
10:19
интеллекта. Если вы хотите в ближайшие
10:22
месяцы реально сдвинуться в вашем
10:24
понимании машинного обучения,
10:26
искусственного интеллекта, если вы
10:28
готовы попробовать, если вы хотите себя
10:31
прокачать как специалист и через
10:34
несколько месяцев уже быть готовыми
10:36
впервые пособеседоваться или впервые
10:39
порешать какие-то задачи, связанные с
10:41
машинным обучением, переходите по ссылке
10:44
в описании видео на анкету предзаписи на
10:46
курс. Мы свяжемся с вами, расскажем,
10:49
подходит ли вам этот курс, какие шаги
10:51
нужно сделать, что может потребоваться
10:53
дополнительно для того, чтобы курс был
10:55
наиболее эффективен. А ещё всем, кто
10:57
оставит заявку, я пришлю PDF с подборкой
11:00
реальных задач собеседований на позицию
11:02
Juniниor Data Scientistста. Эта подборка
11:04
поможет вам сориентироваться в
11:06
требованиях, которые предъявляются к
11:08
специалисту на начальном уровне. Ссылка
11:10
в описании. Увидимся.
11:13
А теперь, как и обещал, история о том,
11:16
как собственные векторы учились
11:18
распознавать лица людей. В начале
Eigenfaces: распознавание лиц через собственные векторы
11:20
девяностых перед учёными стояла
11:22
грандиозная задача: как научить
11:25
компьютер распознавать лица. Ведь
11:27
изображение лица — это тысячи пикселей.
11:30
Огромная размерность. Идея была такой: а
11:34
что, если каждое лицо можно представить
11:37
в виде коктейля из других каких-то
11:40
базовых лиц шаблонов? и их стали искать.
11:43
Сначала взяли большую базу фотографий с
11:46
людьми, привели их к одному размеру и
11:49
освещению. Затем каждое изображение как
11:52
бы вытянули в один длинный вектор из
11:55
тысяч пикселей, а дальше применили к
11:58
этому набору векторов уже знакомый нам
12:00
метод главных компонент. И когда они
12:02
посмотрели на полученные главные
12:04
компоненты, их ждал небольшой сюрприз.
12:07
Если эти векторы, компоненты начать
12:10
преобразовывать обратно в картинке, то
12:13
они начнут выглядеть как призрачные
12:15
полупрозрачные лица. Их так и назвали:
12:19
faces, то есть собственные лица. Первый
12:22
собственный вектор с самым большим
12:24
лямбда выглядел как самое усреднённое
12:27
лицо. Следующие векторы отвечали за
12:29
главные вариации. Один мог отвечать за
12:32
ширину лица, второй за наличие очков,
12:36
третий за угол света. Ну и теперь любое
12:39
лицо можно было представить не как набор
12:41
из десятков тысяч пикселей, а как
12:44
короткий рецепт. Ну, например, возьми
12:46
чуть-чуть от лица один, чуть-чуть от
12:48
лица два, чуть-чуть от лица три и сложи
12:51
это всё вместе. Этот набор из
12:53
коэффициентов перед каждым таким лицом
12:55
становился уникальной подписью каждого
12:58
человека. Чтобы узнать кого-то,
13:00
достаточно было сравнить его подпись с
13:03
подписями в базе данных. Это было в тыся
13:07
раз эффективнее, чем сравнивать просто
13:10
по пикселям. Итак, давайте подведём
13:12
итог, но перед этим надо заплатить за
13:15
проезд, поставить лайк и обязательно
13:17
подписаться на этот канал. Собственные
13:19
векторы — это оси или скелет наших
13:22
данных. Собственные значения — это
13:24
важность этих осей. В методе главных
13:27
компонент они позволяли сжимать данные,
13:30
как мы увидели на примере EN Faces, где
13:33
тысячи пикселей превратились в короткую
13:35
подпись лица. В поисковике Google они
13:37
помогают определить важность
13:39
веб-страниц. Ну а в кластеризации они
13:42
помогают найти естественный разрез в
13:44
данных, позволяя нам более точно
13:47
разделить данные на два кластера.
13:49
Спасибо, что досмотрели это видео до
13:51
конца. Ну а с вами был я, Андрей Жогов.
13:54
Увидимся в следующих видео. Пока.