Привет, на этой неделе мы продолжим работать со Spark и перейдем к более сложной практической задаче, которую решим с нуля. Мы будем решать задачу классификации текстов. Для этого нам понадобится вспомнить, как устроена модель мешка слов, потому что мы ее будем реализовывать на Spark с нуля. А затем нам нужно вспомнить, как работает логистическая регрессия, потому что она поможет нам обучить модель классификации текстов. И логистическую регрессию мы тоже будем обучать с нуля на Spark прямо руками. Начнем с векторизации текстов. Давайте вспомним, как это работает — как устроена модель мешка слов. Представьте, что у вас есть три текста, которые содержат какие-то слова. Давайте возьмем все уникальные слова, которые там используются, и для каждого из них заведем свой столбец. Теперь каждый текст можно представить в виде набора ноликов и единичек, где единичка содержится в столбце, если это слово содержится в нашем тексте. Заметьте, что для текста "good movie" у нас в этих двух столбцах содержатся единички, а все остальные нули; и собственно, так можно закодировать каждый новый текст. Векторизацией называется превращение текста в длинный массив ноликов и единичек — такой длинный вектор в пространстве слов. Чтобы такой вектор получить, вообще говоря, это сопоставление или словарик, который превращает слово в индекс столбца, нужно иметь на каждой машине. Понятно, что этот словарик, вообще говоря, может быть большим, и он может не поместиться в оперативную память, а мы хотели бы наши тексты векторизовывать при помощи MapReduce параллельно. Представьте, что у вас текстов этих терабайт, и каждый текст, конечно, мы хотим превратить в вектор этих чисел независимо. А это означает, что на каждой машине нужен этот словарь, а он может не поместиться в память. Что же делать? На самом деле люди придумали такой трюк с хешированием: давайте не будем хранить словарь, раз он в память не помещается, а давайте мы сделаем словарь вычислимым. Давайте мы будем считать, что из слова можно получить индекс столбца, который соответствует этому слову при помощи просто хеш-функции. Давайте возьмем хеш-функцию, которая выдает 2 в 32-й корзинок, то есть достаточное число, чтобы запаковать все имеющиеся у нас слова. Плюс такой кодировки — то, что мы не занимаем память под этот словарь, а мы можем просто для каждого слова, которое у нас встречается в тексте, посчитать значение хеша, и мы получили индекс столбца. Классно. Это классно распараллеливается и не занимает память. Давайте вспомним пример хеш-функции. Наверное, самая простая хеш-функция — полиномиальная. Как она применяется к строке? Представьте, что s — это строка, s(i) — это индекс символа (точнее код символа в кодировке ASCII), и мы можем взять еще какое-то простое фиксированное число p; и тогда хеш выглядит следующим образом: берем s(0) прибавляем s(1), умноженное на p в 1-ой, прибавляем s(2), умноженное на p в квадрате, и так далее, то есть получаем такой полином, который мы вычисляем. Показано, что это будет неплохой хеш-функцией. Давайте теперь посмотрим на примере, как это применять. Представьте, что нет у нас никакого словаря, который каждому слову в сопоставление дает индекс колонки, а мы просто этот индекс будем вычислять при помощи хеш-функции. Тогда давайте посмотрим значение хеш-функции для каждого слова, которое у нас есть. Конечно, может такое произойти, что разные слова будут иметь одно и то же значение хеш-функции — это называется коллизией, и здесь мы видим, что если мы похешируем слово "a" или "did", мы получаем индекс три, то есть эти слова как бы склеятся в один столбец. Но будем надеяться, что это не сильно повлияет на качество нашего решения. Тогда, если мы возьмем три тех самых текста, которые мы раньше векторизовали при помощи словарика, теперь мы будем их векторизовывать при помощи хеш-функции. У нас пять различных значений хеша, под каждого из них у нас есть свой столбец, и по сути, мы теперь говорим: "Вот у нас есть "good movie"; мы взяли два этих слова, захешировали, получили значение хеш-функций ноль и один, и в эти столбцы, которые соответствуют этому значению хеш-функции, записали единичку, а все остальные — нули", то есть все так же, как раньше, просто без выделенного словаря, который каждому слову сопоставляет индекс. Здесь мы это делаем при помощи хеш-функции. Понятно, что чем больше корзинок у хеш-функции, то есть чем больше уникальных значений хеш-функция умеет возвращать, тем меньше шанс коллизии. А чем меньше шанс коллизии, тем меньше такая кодировка будет влиять на качество результирующей модели. Понятно, что на самом деле имея какой-то хеш, который выдает много уникальных значений, его можно в любой момент сузить до любого числа корзинок. Представьте, что у нас есть тот же самый полиномиальный хеш, который выдает 32-битное целое число. То есть это значит, что этот полином просто вычисляется в 32-битных целых числах; и это будем называть 32-битным хешем. Давайте теперь посмотрим, что мы можем взять значение этой хеш-функции и можем взять остаток от деления на 2 в 22-ой, например. Таким образом, мы получим 2 в 22-ой уникальных значений хеш-функции, и это уже будет 22-битный хеш. Так же можно сделать с любым числом, и получить из этого хеша хеш любой битности: по сути мы контролируем число уникальных столбцов, которые у нас будут в этой задаче. Есть еще такой классный момент. Е, сть статья, которую можно почитать (ссылка в слайде тоже содержится), где люди показывают, как меняется качество решения задачи с изменением числа корзинок к этой хеш-функции. Здесь видно, что начиная с какого-то момента, число бит в хеше увеличивать особо нет смысла. Например, для значений 22, 24 и 26 получается примерно та же самая ошибка в задаче детекции спама (в этом конкретном примере). На практике оно так и получается, что, начиная с какого-то значения, дальше увеличивать особо корзинки хеш-функции смысла не имеет. Давайте теперь посмотрим на задачу детекции спама, которая в этой статье разбирается. Там есть набор данных для обучения, который содержит полмиллиона пользователей, три миллиона писем и 40 миллионов уникальных слов. Почему их так много? Потому что люди делают опечатки, там содержатся всякие бренды, названия каких-нибудь продуктов, написанные по-разному, и поэтому уникальных слов получается много. Давайте теперь возьмем и добавим к этим 40 миллионам слов еще так называемые персональные слова. Что это за слова? Мы берем идентификатор пользователя, добавляем подчеркивание и прибавляем слово, которое использовалось в письме для этого пользователя. И по сути мы ко всем словам, которые использовались в этом письме, добавляем еще персональные слова пользователя в надежде, что мы сможем выучить какое-то персональное понимание о спаме: одному пользователю нравятся рассылки с какого-нибудь сайта Netflix, а другому — нет, и он считает их спамом. И вот для этих пользователей, если там содержится что-то от Netflix, нужно по-разному принимать решения. Просто на основе текста это сделать сложно, нужно еще понять персональные предпочтения. Собственно, поэтому эти персональные слова могут помочь. Как вы понимаете, таких персональных слов очень много, потому что их столько, сколько различных комбинаций "id пользователя-слово". У нас полмиллиона пользователей, 40 миллионов слов, и в итоге у нас получается 16 триллионов новых признаков. Шестнадцать триллионов! Если просто задуматься, даже словарь, который будет просто кодировать каждое персональное слово в индекс колонки, будет занимать больше 16 терабайт. Понятно, что в оперативную память это никогда не влезет, и тут как раз хеширование поможет. Давайте посмотрим, как работает модель, которая использует эти хешированные 16 триллионов персональных признаков. Здесь на графике вы видите черную линию — это baseline; и понятно, что это модель, которая не использует хештрованние. Понятно, что по горизонтальной оси — это просто константа, потому что она не зависит от количества бит в нашем хеше. Синяя кривулька — это неперсональная модель, которая просто взяла 40 миллионов уникальных слов и захешировала их с хешем разной битности. Видно, что в этом конкретном примере неперсональная модель уже перестает проигрывать baseline, когда мы используем 22 бита в нашем хеше: то есть довольно круто. Далее вы можете посмотреть, что персональная модель — это красный график. Она сильно улучшает качество, то есть мы здесь видим по вертикальной оси относительно baseline ошибку классификации, и видно, что она относительно baseline значительно ниже: у нас baseline — единичка, а красная кривулька, которая использует 16 триллионов новых признаков, получает 0.67, то есть она примерно на 30 процентов лучше. Резюмируя: модель, которая использует персональные слова, сильно лучше; модель, которая использует просто хеширование неперсональных слов, перестает проигрывать baseline, начиная с 22-битного хеша, то есть и в том, и в другом случае хеширование или не хуже, или помогает. Давайте теперь посмотрим вот на какой момент: в нашей модели мы надеемся, что эти персональные слова помогут для конкретных пользователей спам лучше отличать. Но ведь пользователи у нас не все в обучающие выборке. Если придет новый пользователь, как это будет работать для него? И авторы статьи этим вопросом тоже задались. Они разбили вот эту кривую качества по разным корзинкам. Взяли корзинку пользователей, у которых ноль примеров в обучения, один пример, от двух до трех и так далее, и заметили удивительную вещь. Оказывается, что для пользователей из тестового набора данных, у которых ноль примеров в обучающей выборке, модель все равно работает лучше (которая использует персональные признаки). Как же так получается? Здесь они нашли такое объяснение: получается, что эти персональные признаки помогают какие-то странные случаи объяснять через эти персональные признаки, а все остальные веса линейной модели, которые опираются на слова (обычные слова, неперсональные), они становятся более генерализуемыми. То есть они лучше описывают, глобально, как вообще устроен спам — вот такой забавный момент. То есть добавляя персональные признаки, неперсональные веса становятся лучше. Давайте резюмируем, про что мы вспомнили, про что мы узнали. Вообще говоря, для векторизации текста при помощи модели мешка слов нужно в памяти держать словарь, который каждому слову сопоставит индекс. Понятно, что этот словарь может не поместиться в памяти; люди придумали как этого избежать. Придумали просто применять хеширование — то есть берем слово, считаем хеш и берем остаток от деления на какое-нибудь число. Это число задает нам число столбцов в нашей модели: например, 2 в 24-ой. Понятно, что хеширование таким образом позволяет работать просто с потенциально неограниченным числом признаков: мы посмотрели, что даже для 16 триллионов признаков это все еще работает. Собственно, хеширование — это метод по умолчанию, который реализован в таком популярном пакете (промышленном), как vowpal-wabbit, и его авторы написали эту статью, где показали, насколько хеширование классно работает. Это такой пакет для классификации текстов и многого другого, который умеет линейной моделью строить для очень большого числа признаков, и там хеширование — в сердце этого алгоритма. В следующем видео мы поговорим о том, как устроена логистическая регрессия — последний шаг, который нам нужен, чтобы перейти к практике.
