Лекция: Метод главных компонент

Курс «Анализ лингвистических данных: квантитативные методы и визуализация».

Школа лингвистики НИУ ВШЭ, магистерская программа «Теория языка и компьютерная лингвистика», 2015-16 учебный год.

Школа лингвистики | Все материалы курса | Исходные коды на Github

Данный материал доступен под лицензией CC BY-SA 4.0. При использовании обязательно упоминание авторов курса и аффилиации. При наличии технической возможности необходимо также указать активную гиперссылку на страницу курса.

Постановка задачи

Словарь Вильяма Шекспира, по подсчёту исследователей, составляет 12000 слов. Словарь негра из людоедского племени «Мумбо-Юмбо» составляет 300 слов. Эллочка Щукина легко и свободно обходилась тридцатью.
И. Илья и Е. Петров. Двенадцать стульев

С данными бывают две проблемы: либо их слишком мало, либо их слишком много. Сегодня мы поговорим о второй проблеме.

Есть такая область исследования — определение авторства текстов. Допустим, у нас есть массив текстов, автор которых неизвестен. Может быть эти тексты принадлежат одному и тому же человеку, может быть разным. Может быть мы догадываемся о том, кто является автором, а может быть и нет. Если бы эти тексты были написаны ручкой на бумаге, мы могли бы ответить на какие-то вопросы об авторстве, сравнивая почерки. Но сейчас перед нами чаще «голый» текст, не содержащий таких естественных индивидуальных признаков, как почерк.

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

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

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

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

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

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

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

Способы решения этой задачи, называются методами уменьшения размерности (dimensionality reduction). Метод главных компонент (principal components analysis, PCA) – один из них. Он очень простой и при этом довольно популярный, так что имеет смысл с ним познакомиться поподробнее.

Школьные оценки

Одно число вместо двух

Отвлечёмся от задачи определения авторства и, прежде, чем обсуждать общую конструкцию, рассмотрим простой (и немного искусственный) пример.

У нас есть табличка с результатами теста для школьников по двум предметам — например, по русскому языку и математике.

##        rus     math
## 1 38.62011 33.67848
## 2 46.22913 54.53733
## 3 46.40963 38.32976
## 4 53.17011 51.07601
## 5 62.86754 65.64322

Можно нарисовать вот такую картинку:

Эта картинка не претендует на полное согласие с реальностью – данные я сгенерировал на компьютере и на самом деле диаграммы рассеяния для оценок по разным предметам устрены несколько иначе (см. последний раздел для более реалистичных картинок) – но в качестве иллюстрации она подходит в самый раз. Точки распределены примерно внутри наклонённого вытянутого эллипса (так обычно устроено многомерное нормальное распределение). Мы видим, что оценки по этим двум предметам скоррелированы — среди школьников, получающих высокие баллы по математике, много тех, кто также получает высокие баллые по русскому языку, и наоборот (это согласуется с нашей интуицией). Есть и исключения, лежащие вне эллипса – выбросы. Для простоты изложения, мы сейчас будем пренебрегать выбросами, а также считать, что если бы мы взяли побольше школьников, то соответствующие им точки практически заполнили бы весь эллипс.

Это наши исходные данные. Теперь предположим, что нам надо уменьшить размерность — вместо двух чисел на каждого школьника хранить только одно число. Например, мы выбираем, что записать в аттестат, и по закону это должно быть только одно число, а не два. И мы хотим в этом единственном числе закодировать как можно больше информации о школьнике. Как в этом случае поступить?

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

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

С другой стороны, какая-то информация всё-таки теряется. Представьте себе, что мы знаем о школьнике только тот факт, что он сдал русский на 50 баллов. Что это говорит о математических способностях школьника? Если не знать настоящих данных, а смотреть только на эллипс на картинке, то мы увидим, что соответствующая точка может находиться в любом месте синего отрезка — его оценка по математике в этом случае колеблется примерно между 29 и 72 — разброс очень большой.

Конечно, понятно, что заменяя два числа одним мы потеряем какую-то информацию, но хотелось бы всё-таки эти потери минимизировать. Можем ли мы сделать что-то лучшее, чем сообщать только одну оценку из двух? Оказывается, можем.

Мы можем сконструировать новое число из двух имеющихся!

Давайте рассмотрим самый простой вариант: впишем в аттестат сумму оценок за русский язык и математику. Иными словами, мы введём новую переменную — обозначим её через $PC_1$ (почему так — будет ясно позднее), которая связана с нашими старыми переменными таким образом:

\[ PC_1=rus+math \]

Посмотрим, насколько этот метод лучше. Пусть мы знаем, что для некоторого школьника $PC_1=100$. Что тогда можно сказать про его оценки?

Проведём на графике прямую, соответствующую условию $PC_1=100$, то есть $rus+math=100$. Она пройдёт из левого верхнего угла в правый нижний и пересечёт наш эллипс по некоторому отрезку.

Как и в прошлый раз, наш школьник мог бы оказаться в любой точке этого отрезка: на этот раз мы не знаем наверняка ни оценку по математике (она колеблется где-то между 39 и 63), ни оценку по русскому языку (она между 37 и 61).

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

Новая система координат

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

В качестве первой координаты точки мы возмём $PC_1$, то есть сумму её старых координат, а в качестве второй координаты (обозначим её через $PC_2$) возьмём разность её старых координат:

\[ PC_2=math-rus \]

Например, школьник, у которого оценки по русскому и математике совпадают, имеет $PC_2$ равное нулю. Школьник со старыми координатами $math=60$ и $rus=40$ имеет новые координаты $PC_1=100$ и $PC_2=20$ и т.д. Зная старые координаты, можно найти новые, а зная новые можно найти старые — для этого нужно решить соответствующую систему уравнений.

Координата $PC_2$ имеет простую интерпретацию: это «уклон»: даже если два школьника в целом учатся одинаково хорошо, кто-то из них может быть чуть лучше другого по математике, но хуже по русскому. Можно сказать, что $PC_2$ измеряет «склонность к математике». (Но в дальнейшем не всегда наши главные компоненты будут иметь такую простую интерпретацию.)

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

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

Проверьте, что множество точек, в которых $PC_1$ равно какой-нибудь константе (например, 120) является прямой, параллельной оси $PC_2$, и наоборот, множество точек, в которых $PC_2$ равно константе (например, 10) является прямой, параллельной оси $PC_1$.

Таким образом получается новая система координат. Если мы развернём картинку таким образом, чтобы $PC_1$ стала горизонтальной осью, а $PC_2$ вертикальной, то наш эллипс «ляжет на бок», а старые координаты $math$ и $rus$ будут диагональными прямыми. Получится картинка, изображённая на рис. 5.

Заметим, что на новой картинке $PC_1$ и $PC_2$ имеют нулевую корреляцию: раньше мы знали, что школьник, хорошо успевающий по русскому, скорее всего имеет неплохую оценку и по математике, а сейчас знание $PC_1$ ничего не говорит нам о том, велик или мал $PC_2$. Геометрически это соответствует тому, что эллипс теперь не имеет никакого ярко выраженного наклона (вспомните лекцию про корреляцию). Это важный момент: в новой системы координат мы избавились от зависимостей между переменными. Именно благодаря этому новая система координат «экономнее» старой и мы можем выделить в ней переменную $PC_1$, содержащую большую часть информации.

Координата $PC_1$ называется первой главной компонентой, а $PC_2$ — второй. Заметим, что «главных компонент» получилось столько же, сколько изначально было переменных, но зато теперь мы знаем, что $PC_1$ «главнее» (содержит больше информации), чем $PC_2$.

Мы выбирали координату $PC_1$ таким образом, чтобы уменьшить длину отрезка, по которому наш эллипс пересекается с прямой $PC_1=const$, перпендикулярной оси. Можно действовать другим способом, который приведёт к такому же результату: подбирать направление оси $PC_1$ так, чтобы вдоль него был максимальный разброс значений. Иными словами, ось нужно направить вдоль длинной оси эллипса — тогда перпендикулярная ось пойдёт вдоль его короткой оси (с минимумом разброса). Мы будем использовать этот подход в следующем разделе.

Связь старых переменных с новыми

На рис. 5 также видно, как связаны старые и новые переменные. Например, видно, что в $PC_1$ обе старые переменные ($rus$ и $math$) вносят положительный вклад: если увеличиваются они, то увеличивается и $PC_1$. А в $PC_2$ положительный вклад вносит математика (у неё стрелочка смотрит «вверх»), а $rus$ вносит отрицательный вклад (стрелочка направлена «вниз»). Это значит, что $PC_2$ растёт с увеличением $math$ и уменьшается с увеличением $rus$.

В нашем случае обе старые переменные вносят одинаковый вклад в $PC_1$, но эта ситуация могла бы быть и иной. Рассмотрим, например, другой датафрейм с оценками; его диаграмма рассеяния изображена на рис. 6.

Здесь эллипс повёрнут не на 45 градусов, а на меньший угол — его длинная ось лишь немножко отклоняется от горизонтали. Если бы мы ввели такие же координаты $PC_1$ и $PC_2$, как и раньше, они бы не были оптимальными. Раньше координаты $rus$ и $math$ были равноправными, а теперь они явно неравноправны: оценка по русскому содержит больше информации о школьнике, чем оценка по математике. Это связано с тем фактом, что разброс оценок по математике в этом случае гораздо меньше разброса оценок по горизонтали. Мы хотим выбрать ось $PC_1$ таким образом, чтобы разброс значений по этой оси был максимально возможным (чтобы она содержала максимум информации), то есть вдоль длинной оси эллипса (см. конец предыдущего параграфа).

Чтобы найти, как следует направить оси (или, что то же самое, как выразить $PC_1$ и $PC_2$ через старые переменные $rus$ и $math$), можно использовать функции prcomp или princomp или какие-нибудь другие (существует несколько пакетов, реализующих метод главных компонент в R):

pca <- prcomp(gradebook)
rot <- pca$rotation
pca

## Standard deviations:
## [1] 10.10655  3.92137
## 
## Rotation:
##            PC1        PC2
## rus  0.9513181 -0.3082107
## math 0.3082107  0.9513181

Матрица Rotation как раз и показывает, как новые оси повёрнуты относительно старых. Фактически, здесь написано:

\[ PC_1=0.9513181\times rus + 0.3082107\times math \] \[ PC_2=-0.3082107\times rus + 0.9513181\times math \]

Нарисуем оси на картинке.

Теперь переменная $rus$ вносит гораздо больший вклад в первую главную компоненту, по сравнению с переменной $math$: это видно и по картинке (ось $PC1$ почти параллельна оси $rus$), и по числам (коэффициент при $rus$ гораздо больше коэффициента при $math$).

Нарисуем теперь картинку в новых координатах.

Трёхмерный пример

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

Начнём снова с искусственных данных. Пусть наш датафрейм теперь имеет вот такой вид.

##            x         y          z
## 1  1.0260509  2.316172  1.5304640
## 2  1.6672554 -1.448155  0.5606579
## 3 -2.5949498 -1.328355  0.5180702
## 4  4.9366130  2.384744  1.5730692
## 5 -0.3543403 -2.030523 -3.6689673

В каждой строке записаны три числа. Нарисуем трёхмерную диаграмму рассеяния.

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