Имею задачу на регрессию. Даны правильные ответы в double и следующие данные:
Запись 1: А 1 Б 3 В 4 Г 6
Запись 2: Б 3 Ж 1 З 4 И 5
Запись 3: Г 4 Л 1 М 1
И так далее.

Вопрос в том, как правильно преобразовать мои данные в Vector<Double> (по крайней мере Spark на вход данные принимает именно в таком виде), чтобы обучение было наиболее быстрым. Количество используемой памяти - вторично (можно считать, что ее бесконечное количество).

Есть следующие соображения:

  1. Я могу пробежаться по всему файлу и найти все возможные классы (А, Б, В, Г...) и получить очень большое число классов (букв 33, но классов у меня на порядки больше). Я получу вектора с большим количеством нулей. Хотя есть и dense вектора, мне кажется такой подход не особенно разумен.
  2. Посмотреть по всем данным какие есть классы и преобразовывать их, так сказать на лету. Если я сопоставлю А = 0, Б = 1, В = 2, Г = 3, то первая запись будет выглядеть следующим образом: 0 1 1 3 2 4 3 6. Но тогда нужно будет в Spark отдать конкретные номера категорийных фич. К сожалению это сделать невозможно, потому что записи мои имеют разную длину в этом случае. Первый подход, вообще говоря, позволяет поступить таким образом, потому что записи там - одинаковой длины.
  3. Каким-то хитрым образом закодировать классы так, чтобы использовать данные из фич в наличии у каждой записи. Т.е. для первой записи - это было бы только 4 числа, для третьей записи - только 3. Не очень представляю, можно ли такое сделать в принципе. Единственное, что приходит в голову - для такого подхода нужно использовать неассоциативную функцию.

Заранее благодарю за любые идеи.

Имею задачу на регрессию. Даны правильные ответы в double и следующие данные: Запись 1: А 1 Б 3 В 4 Г 6 Запись 2: Б 3 Ж 1 З 4 И 5 Запись 3: Г 4 Л 1 М 1 И так далее. Вопрос в том, как правильно преобразовать мои данные в Vector&lt;Double&gt; (по крайней мере Spark на вход данные принимает именно в таком виде), чтобы обучение было наиболее быстрым. Количество используемой памяти - вторично (можно считать, что ее бесконечное количество). Есть следующие соображения: 1. Я могу пробежаться по всему файлу и найти все возможные классы (А, Б, В, Г...) и получить очень большое число классов (букв 33, но классов у меня на порядки больше). Я получу вектора с большим количеством нулей. Хотя есть и dense вектора, мне кажется такой подход не особенно разумен. 2. Посмотреть по всем данным какие есть классы и преобразовывать их, так сказать на лету. Если я сопоставлю А = 0, Б = 1, В = 2, Г = 3, то первая запись будет выглядеть следующим образом: 0 1 1 3 2 4 3 6. Но тогда нужно будет в Spark отдать конкретные номера категорийных фич. К сожалению это сделать невозможно, потому что записи мои имеют разную длину в этом случае. Первый подход, вообще говоря, позволяет поступить таким образом, потому что записи там - одинаковой длины. 3. Каким-то хитрым образом закодировать классы так, чтобы использовать данные из фич в наличии у каждой записи. Т.е. для первой записи - это было бы только 4 числа, для третьей записи - только 3. Не очень представляю, можно ли такое сделать в принципе. Единственное, что приходит в голову - для такого подхода нужно использовать неассоциативную функцию. Заранее благодарю за любые идеи.

Мне кажется, что вариант 1 самый легкий в реализации, и в целом, самый удачный. Он похож на так называемый "bag of words", очень успешно применяемый в NLP. Разреженность получившихся векторов в этом случае даже полезна - как правило, это ускоряет вычисления.

Вот, например, можно посмотреть http://spark.apache.org/docs/latest/mllib-feature-extraction.html
Скорее всего, напрямую применить HashingTF не полулчится, но можно посмотреть, как он реализован, и сделать что-то похожее. Если классов (А, Б, В...) не так много (например, не больше 1000), то хэширование не нужно - оно нужно только если классов очень много. Но главное, чтобы векторы были разреженными (http://spark.apache.org/docs/latest/mllib-data-types.html) - иначе вычисления могут занять слишком много времени.

Мне кажется, что вариант 1 самый легкий в реализации, и в целом, самый удачный. Он похож на так называемый "bag of words", очень успешно применяемый в NLP. Разреженность получившихся векторов в этом случае даже полезна - как правило, это ускоряет вычисления. Вот, например, можно посмотреть http://spark.apache.org/docs/latest/mllib-feature-extraction.html Скорее всего, напрямую применить `HashingTF` не полулчится, но можно посмотреть, как он реализован, и сделать что-то похожее. Если классов (А, Б, В...) не так много (например, не больше 1000), то хэширование не нужно - оно нужно только если классов очень много. Но главное, чтобы векторы были разреженными (http://spark.apache.org/docs/latest/mllib-data-types.html) - иначе вычисления могут занять слишком много времени.

@stolzen
Благодарю за ответ. HashingTF очень интересная тема!

Я действительно использовал первый подход и использовал Vector.sparse. И успешно тренирую свои деревья. Планирую закончить за выходные и смогу поделиться результатом - временем тренировки модели разной сложности.

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

HashingTF, насколько я понимаю, решает эту проблему сопоставляя с классами целое число - хэш. Здесь меня смущает, что размерность массива с хэшем будет существенно больше, чем с порядковыми номерами. Повлияет ли размерность массива (при учете, что он сильно разреженный) на производительность? В принципе, вместо zipWithIndex можно использовать другую похожую операцию, которая дает уникальные id с пропусками, но не приводит к дополнительным проходам по данным. Я пока еще не сравнивал время обучения модели с тем и другим подходами.

Классов у меня дофига - на небольшой файл в 160 МБ их 7700. Это маленький файлик для отработки алгоритма. Есть побольше уже для более серьезных экспериментов 1.2 ГБ и я видел имеются файлы размером 8+ ГБ. Не уверен, что классов будет существенно больше на бОльших файлах, но есть такое подозрение.

В HashingTF смущает только вероятность коллизии. Для джавы (hashcode типа int => 4 байта) эта вероятность для 9300 значений будет уже порядка 1% (Probability table здесь - https://en.wikipedia.org/wiki/Birthday_problem). На мой взгляд - это весьма много. Пока что я не понял, как с этим бороться.

@stolzen Благодарю за ответ. HashingTF очень интересная тема! Я действительно использовал первый подход и использовал Vector.sparse. И успешно тренирую свои деревья. Планирую закончить за выходные и смогу поделиться результатом - временем тренировки модели разной сложности. Для использования первого подхода мне действительно понадобилось найти уникальные классы и затем сопоставить им порядковые номера. Эта операция (выделения уникальных) - distinct - вычислительно весьма сложна и использование именно порядковых номеров (zipWithIndex) приводит к дополнительному шагу обработки данных. HashingTF, насколько я понимаю, решает эту проблему сопоставляя с классами целое число - хэш. Здесь меня смущает, что размерность массива с хэшем будет существенно больше, чем с порядковыми номерами. Повлияет ли размерность массива (при учете, что он сильно разреженный) на производительность? В принципе, вместо zipWithIndex можно использовать другую похожую операцию, которая дает уникальные id с пропусками, но не приводит к дополнительным проходам по данным. Я пока еще не сравнивал время обучения модели с тем и другим подходами. Классов у меня дофига - на небольшой файл в 160 МБ их 7700. Это маленький файлик для отработки алгоритма. Есть побольше уже для более серьезных экспериментов 1.2 ГБ и я видел имеются файлы размером 8+ ГБ. Не уверен, что классов будет существенно больше на бОльших файлах, но есть такое подозрение. В HashingTF смущает только вероятность коллизии. Для джавы (hashcode типа int =&gt; 4 байта) эта вероятность для 9300 значений будет уже порядка 1% (Probability table здесь - https://en.wikipedia.org/wiki/Birthday_problem). На мой взгляд - это весьма много. Пока что я не понял, как с этим бороться.

Обычно хэширование работает оч хорошо - вот, можно тут посмотреть http://scikit-learn.org/stable/modules/generated/sklearn.feature_extraction.text.HashingVectorizer.html

there can be collisions: distinct tokens can be mapped to the same feature index. However in practice this is rarely an issue if n_features is large enough (e.g. 2 ** 18 for text classification problems).

Я использовал хэширование и для гораздо меньшего размера словаря - около 5 тыс, и работало нормально.

Я думаю в вашем случае я бы поступил так:

  • я бы прошелся один раз по данным и сложил все классы в какой-нибудь Multiset (из Guava),
  • затем бы выбросил редкие классы (скажем, те которые встречаются меньше, чем в 10-15 объектах).
  • Потом на ключах из multiset сделал бы zipWithIndex, чтобы получить словарь класс -> индекс
  • теперь можно пройтись по данным еще раз для векторизации используя словарь

Если возможно, то словарь можно построить один раз на каком-нибудь большом файле, сохранить его один раз и использовать для всех остальных файлов.

Возможно что-то такое уже реазизовано в спарке, но мне об этом не известно.

Обычно хэширование работает оч хорошо - вот, можно тут посмотреть http://scikit-learn.org/stable/modules/generated/sklearn.feature_extraction.text.HashingVectorizer.html &gt; there can be collisions: distinct tokens can be mapped to the same feature index. However in practice this is rarely an issue if `n_features` is large enough (e.g. 2 ** 18 for text classification problems). Я использовал хэширование и для гораздо меньшего размера словаря - около 5 тыс, и работало нормально. Я думаю в вашем случае я бы поступил так: - я бы прошелся один раз по данным и сложил все классы в какой-нибудь Multiset (из Guava), - затем бы выбросил редкие классы (скажем, те которые встречаются меньше, чем в 10-15 объектах). - Потом на ключах из multiset сделал бы zipWithIndex, чтобы получить словарь `класс -&gt; индекс` - теперь можно пройтись по данным еще раз для векторизации используя словарь Если возможно, то словарь можно построить один раз на каком-нибудь большом файле, сохранить его один раз и использовать для всех остальных файлов. Возможно что-то такое уже реазизовано в спарке, но мне об этом не известно.

@stolzen
Именно таким образом я и поступил. Только без опыта я не сообразил, что этот словарь нужно сохранять и использовать в дальнейшем. Буквально только что мы это выяснили. Здесь есть несколько проблем.

  1. Если такой словарь расширяется - модели нужно перестраивать. Либо иметь очень сложный процесс, который бы позволил расширять словарь так, чтобы модели, которые его уже используют, не сломались.
  2. Словарь нужно где-то хранить и поддерживать (делать для него бэкап и т.д.).
  3. Операция zipWithIndex требует дополнительного вычисления. И хотя для построения словаря эта операция одноразовая, мне бы хотелось ее избежать.

Т.е. использование хэширование классно решает все эти проблемы - никакого состояния: нет нужды хранить словарь, его поддерживать, не нужно выполнять относительно дорогую операцию zipWithIndex (она дорогая из-за дополнительного прохода по данным и выполнения distinct).
Но смущает то, что с хэшированием мы фактически получаем массив фич размером Integer.MAX_VALUE. При условии, что я использую Vector.sparse, я не знаю, как будет вести себя алгоритм. Буду пробовать. За рекомендации большое спасибо!

@stolzen Именно таким образом я и поступил. Только без опыта я не сообразил, что этот словарь нужно сохранять и использовать в дальнейшем. Буквально только что мы это выяснили. Здесь есть несколько проблем. 1. Если такой словарь расширяется - модели нужно перестраивать. Либо иметь очень сложный процесс, который бы позволил расширять словарь так, чтобы модели, которые его уже используют, не сломались. 2. Словарь нужно где-то хранить и поддерживать (делать для него бэкап и т.д.). 3. Операция zipWithIndex требует дополнительного вычисления. И хотя для построения словаря эта операция одноразовая, мне бы хотелось ее избежать. Т.е. использование хэширование классно решает все эти проблемы - никакого состояния: нет нужды хранить словарь, его поддерживать, не нужно выполнять относительно дорогую операцию zipWithIndex (она дорогая из-за дополнительного прохода по данным и выполнения distinct). Но смущает то, что с хэшированием мы фактически получаем массив фич размером Integer.MAX_VALUE. При условии, что я использую Vector.sparse, я не знаю, как будет вести себя алгоритм. Буду пробовать. За рекомендации большое спасибо!

Операция zipWithIndex требует дополнительного вычисления. И хотя для построения словаря эта операция одноразовая, мне бы хотелось ее избежать.

Если использовать какой-нибудь Set в памяти, то zipWithIndexсовсем не затратная. Затратно может быть пройтись один раз по данным для того, чтобы этот сет построить. Но для файла в 1-2 гб это ерунда, даже спарк для этого не нужен, простой скрипт на питоне или awk должен справится - при условии, что кол-во классов не сильно большое и поместится в память.

Но смущает то, что с хэшированием мы фактически получаем массив фич размером Integer.MAX_VALUE. При условии, что я использую Vector.sparse, я не знаю, как будет вести себя алгоритм.

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

Всегда пожалуйста!

&gt; Операция zipWithIndex требует дополнительного вычисления. И хотя для построения словаря эта операция одноразовая, мне бы хотелось ее избежать. Если использовать какой-нибудь `Set` в памяти, то `zipWithIndex`совсем не затратная. Затратно может быть пройтись один раз по данным для того, чтобы этот сет построить. Но для файла в 1-2 гб это ерунда, даже спарк для этого не нужен, простой скрипт на питоне или awk должен справится - при условии, что кол-во классов не сильно большое и поместится в память. &gt;Но смущает то, что с хэшированием мы фактически получаем массив фич размером Integer.MAX_VALUE. При условии, что я использую Vector.sparse, я не знаю, как будет вести себя алгоритм. Если классов $N$ штук, то фактическая размерность вектора после хэширования не должна превышать $N$ (а из-за возможных коллизий, скорее всего, будет меньше). Поэтому, я думаю, нет причин для беспокойства. Всегда пожалуйста!

Я ради интереса решил проверить, действительно ли для awk 1 гб "ерунда" или нет. Сначала сгенерировал файл примерно-приблизительно похожий на сабж с числами от 0 до 10 тыс размером 1 гб, а затем построил словарь на этих данных.

Построение словаря заняло 12 минут - примерно столько же, сколько генерация данных (около 10 мин)

Я, по правде, рассчитывал на 2-3 минуты, но у меня компьютер уже старый, думаю на нормальном сервере с линуксом (у меня винда) должно быть шустрее. А если еще это дело обернуть в gnu-parallel, то можно это ускорить еще в несколько раз.

Вот код: http://pastebin.com/gXwpWqSS

Вообщем, имхо, не так уж и затратно. Хотя для файлов в 8 гб наверное долговато выйдет.

Я ради интереса решил проверить, действительно ли для awk 1 гб "ерунда" или нет. Сначала сгенерировал файл примерно-приблизительно похожий на сабж с числами от 0 до 10 тыс размером 1 гб, а затем построил словарь на этих данных. Построение словаря заняло 12 минут - примерно столько же, сколько генерация данных (около 10 мин) Я, по правде, рассчитывал на 2-3 минуты, но у меня компьютер уже старый, думаю на нормальном сервере с линуксом (у меня винда) должно быть шустрее. А если еще это дело обернуть в gnu-parallel, то можно это ускорить еще в несколько раз. Вот код: http://pastebin.com/gXwpWqSS Вообщем, имхо, не так уж и затратно. Хотя для файлов в 8 гб наверное долговато выйдет.

@stolzen
Не очень затратно, согласен - такие файлы у меня читаются долго (1ГБ) только из-за сортировки в консоли, чтобы получить уникальный набор фич. Я использую такую команду

cat input.file | grep "type AP" | awk -F '"' '{print $2}' | sed 'y/ /\n/' | egrep -v "^\d*$" | sort | uniq >> unique_categories

Сначала выводим весь файл (в каждой строке есть фичи с их значениями)

C10C1002 1 C21C1003 2 C21C1004 2 C21C1005 2...
C10C1002 - это как раз одна из фич. И значение для этой строки у нее - 1.

Т.е. если использовать Set, то все вообще будет мгновенно (у меня мощный компьютер с SSD диском). Что мне все-таки не нравится - что нужно будет хранить эту мапу где-нибудь и пересчитывать при добавлении фич для существующих моделей.

Подход с хэшированием этой проблемы позволяет избежать. Я посмотрел, как работает HashingTF, идея прикольная. Теперь измеряю на своих данных.
Например, есть следующие результаты
для массива длиной 65536: количество features [7694], hashes [7694], mod [7362]
для массива длиной 16394: количество features [7694], hashes [7694], mod [6149]
Видно, что потерь существенно больше, при этом потерь от непосредственного хэширования нет вообще - все-таки в Java достаточно хорошая функция hashCode для строки.

Тот же самый пример для большего количества фич (из большего файла):
для массива длиной 65536: количество features [11729], hashes [11729], mod [10837]
для массива длиной 16394: количество features [11729], hashes [11729], mod [8321]

Я сравнил производительность (времени обучения модели) алгоритма с хешированием и с сохранением маппинга. Алгоритм с хэшированием работает побыстрее на бОльших выборках, но из-за потери фич я не хочу его использовать. К тому же все равно нужно где-то хранить размер массива.

@stolzen Не очень затратно, согласен - такие файлы у меня читаются долго (1ГБ) только из-за сортировки в консоли, чтобы получить уникальный набор фич. Я использую такую команду ```` cat input.file | grep "type AP" | awk -F '"' '{print $2}' | sed 'y/ /\n/' | egrep -v "^\d*$" | sort | uniq &gt;&gt; unique_categories ```` Сначала выводим весь файл (в каждой строке есть фичи с их значениями) ```` C10C1002 1 C21C1003 2 C21C1004 2 C21C1005 2...```` C10C1002 - это как раз одна из фич. И значение для этой строки у нее - 1. Т.е. если использовать Set, то все вообще будет мгновенно (у меня мощный компьютер с SSD диском). Что мне все-таки не нравится - что нужно будет хранить эту мапу где-нибудь и пересчитывать при добавлении фич для существующих моделей. Подход с хэшированием этой проблемы позволяет избежать. Я посмотрел, как работает HashingTF, идея прикольная. Теперь измеряю на своих данных. Например, есть следующие результаты ```` для массива длиной 65536: количество features [7694], hashes [7694], mod [7362]```` ```` для массива длиной 16394: количество features [7694], hashes [7694], mod [6149]```` Видно, что потерь существенно больше, при этом потерь от непосредственного хэширования нет вообще - все-таки в Java достаточно хорошая функция hashCode для строки. Тот же самый пример для большего количества фич (из большего файла): ```` для массива длиной 65536: количество features [11729], hashes [11729], mod [10837]```` ```` для массива длиной 16394: количество features [11729], hashes [11729], mod [8321]```` Я сравнил производительность (времени обучения модели) алгоритма с хешированием и с сохранением маппинга. Алгоритм с хэшированием работает побыстрее на бОльших выборках, но из-за потери фич я не хочу его использовать. К тому же все равно нужно где-то хранить размер массива.
236
просмотров
7
ответов
2
подписчики
Предпросмотр
введите как минимим 10 characters
WARNING: You mentioned %MENTIONS%, but they cannot see this message and will not be notified
Сохраняю...
Сохранено
Все темы будут удалено ?
Сохранены неопубликованные черновики. Нажмите для продолжения редактирования
Discard draft