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

Школа лингвистики НИУ ВШЭ, магистерская программа «Теория языка и компьютерная лингвистика», 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\) измеряет «склонность к математике». (Но в дальнейшем не всегда наши главные компоненты будут иметь такую простую интерпретацию.)

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