Какие алгоритмы подходят для этой простой проблемы машинного обучения?
Я имею, что я думаю, простой вопрос о машинном обучении.
Вот основная проблема: Мне неоднократно дают новый объект и список описаний об объекте. Например: new_object: 'bob' new_object_descriptions: ['tall','old','funny']. Я затем должен использовать некоторое машинное обучение для нахождения ранее обработанных объектов, которые имеют 10 или меньше самых подобных описаний, например, past_similar_objects: ['frank','steve','joe']. Затем, у меня есть алгоритм, который может непосредственно иметь размеры, подобны ли эти объекты действительно для удара, например, correct_objects: ['steve','joe']. Классификатору затем дают это обучение обратной связи успешных соответствий. Затем этот цикл повторяется с новым объектом. Вот псевдокод:
Classifier=new_classifier()
while True:
new_object,new_object_descriptions = get_new_object_and_descriptions()
past_similar_objects = Classifier.classify(new_object,new_object_descriptions)
correct_objects = calc_successful_matches(new_object,past_similar_objects)
Classifier.train_successful_matches(object,correct_objects)
Но, существуют некоторые соглашения, которые могут ограничить, какой классификатор может использоваться:
Будут миллионы объектов, помещенных в этот классификатор так классификация, и обучение должно масштабироваться хорошо к миллионам типов объектов и все еще быть быстрым. Я полагаю, что это дисквалифицирует что-то как классификатор спама, который оптимален всего для двух типов: спам или не спам. (Обновление: Я мог, вероятно, сузить это к тысячам объектов вместо миллионов, если это - проблема.)
Снова, я предпочитаю скорость, когда миллионы объектов классифицируются по точности.
Обновление: классификатор должен возвратить 10 (или меньше) наиболее подобные объекты, на основе обратной связи от прошлого обучения. Без этого предела очевидный обман был бы для классификатора, мог просто возвратить все прошлые объекты :)
Что такое достойные, быстрые алгоритмы машинного обучения с этой целью?
Примечание: calc_successful_matches метрика расстояния является чрезвычайно дорогой для вычисления, и вот почему я использую быстрый алгоритм машинного обучения, чтобы попытаться предположить, какие объекты будут близки, прежде чем я на самом деле сделаю дорогое вычисление.
6 ответов
SVM работает довольно быстро. LIBSVM для Python, в частности, предоставляет очень достойную реализацию Support Vector Machine для классификации.
Этот проект отличается от типичных классификационных приложений двумя важными способами:
- Вместо вывода класса, к которому, как предполагается, принадлежит новый объект (или, возможно, вывода массива этих классов, каждый с уровнем вероятности / достоверности), «классификатор» предоставляет список «соседей», которые «достаточно близки» к новому объекту.
- При каждой новой классификации целевая функция, независимая от классификатора, предоставляет список правильных «соседей»; в свою очередь, исправленный список ( подмножество списка, предоставленного классификатором?) затем используется для обучения классификатора
Идея второго пункта, вероятно, заключается в том, что будущие объекты, представленные классификатору и с подобный текущему объекту должен быть лучше "классифицирован" (быть связан с более правильным набором ранее замеченных объектов), поскольку продолжающееся обучение усиливает связи с положительными (правильными) совпадениями, в то же время ослабляя связь с объектами, которые классификатор изначально ошибся.
Эти две характеристики создают разные проблемы.
- Тот факт, что выходные данные представляют собой список объектов, а не "прототип" (или своего рода идентификатор категории), затрудняет масштабирование, поскольку количество видимых на данный момент объектов увеличивается до миллионов экземпляры, как указано в вопросе.
- Тот факт, что обучение выполняется на основе подмножества совпадений, найденных классификатором, может привести к чрезмерной подгонке, в результате чего классификатор может стать «слепым» к характеристикам (размерам), которые он случайно не придал значимости / значимости на ранних этапах обучения. (Возможно, я слишком много предполагаю в отношении целевой функции, отвечающей за создание списка «правильных» объектов)
Возможно, проблема масштабирования может быть решена с помощью двухэтапного процесса с первым классификатором, основанным на алгоритм K-средних или что-то подобное, которое будет создавать подмножество общей коллекции объектов (объектов, ранее замеченных) как правдоподобных совпадений для текущего объекта (эффективно отфильтровывая, скажем, 70% или более коллекции). Эти возможные совпадения затем будут оцениваться на основе модели векторного пространства (особенно актуально, если размеры объекта основаны на факторах, а не на значениях) или некоторых других моделей. Основное предположение для этого двухэтапного процесса состоит в том, что коллекция объектов будет эффективно раскрывать кластеры (просто она может быть относительно равномерно распределена по различным измерениям).
Другой способ еще больше ограничить количество кандидатов для оценки по мере увеличения размера ранее замеченных объектов - это удалить почти повторяющиеся объекты и сравнить только с одним из них (но предоставить в результате полный список дубликатов, предполагая, что если новый объект близок к «представителю» этого почти дублированного класса, все члены класса также будут соответствовать)
С проблемой чрезмерной подгонки сложнее справиться.Возможным подходом было бы [иногда] случайное добавление объектов в список соответствия, которые классификатор обычно не включает. Дополнительные объекты могут быть добавлены на основе их относительного расстояния до нового объекта (т. Е. Делая более вероятным добавление относительно близкого объекта)
Вам действительно нужен для этого алгоритм машинного обучения? Какая у вас метрика сходства? Вы упомянули размерность количества объектов, а как насчет размера черты, установленной для каждого человека? Есть ли максимальное количество типов черт? Я мог бы попробовать что-то вроде этого:
1) Имейте черту отображения словаря в список имен с именем map
для каждого человека p
для каждой черты t в p
map [t] .add ( p);
2) затем, когда я хочу найти самого близкого человека, я беру свой словарь и создаю новый временный:
имя сопоставления словаря для подсчета cnt
для каждого признака t в моем интересующее лицо
для каждого человека p в карте [t]
cnt [p] ++;
тогда запись с наибольшим количеством является ближайшей
Преимущество здесь в том, что карта создается только один раз . если черт на человека невелико, а типы доступных черт большие, то алгоритм должен быть быстрым.
То, что вы описываете, в некоторой степени похоже на Локально-взвешенное обучение Алгоритм, который для данного экземпляра запроса обучает модель локально вокруг соседних экземпляров, взвешенных по их расстоянию до запрашиваемого.
Weka (Java) реализует это в weka.classifiers.lazy.LWL
Алгоритм, который, кажется, отвечает вашим требованиям (и, возможно, похож на то, что предлагает Джон-статистик) - это Семантическое хэширование. Основная идея заключается в том, что он обучает глубокую сеть убеждений (тип нейронной сети, который некоторые называют "нейронными сетями 2.0" и который сейчас является очень активной областью исследований) создавать хэш списка описаний объекта в двоичном числе так, чтобы расстояние Хэмминга между числами соответствовало похожим объектам. Поскольку для этого требуются только битовые операции, это может быть довольно быстро, и поскольку вы можете использовать его для создания алгоритма в стиле ближайшего соседа, он естественным образом обобщается на очень большое количество классов. Это очень хороший современный материал. Недостаток: он не тривиален для понимания и реализации, и требует некоторой настройки параметров. Автор предоставляет некоторый код Matlab здесь. Несколько более простой в реализации и тесно связанный с этим алгоритм - Locality Sensitive Hashing.
Теперь, когда вы сказали, что у вас есть дорогая функция расстояния, которую вы хотите быстро аппроксимировать, мне вспомнился еще один очень интересный алгоритм, который это делает, Boostmap. Этот алгоритм использует бустинг для создания быстрой метрики, которая аппроксимирует дорогую для вычисления метрику. В определенном смысле это похоже на вышеописанную идею, но используемые алгоритмы отличаются. У авторов этой статьи есть несколько работ по смежным методам, все довольно хорошего качества (опубликованные на ведущих конференциях), с которыми вы можете ознакомиться.
Вы можете использовать модель векторного пространства ( http://en.wikipedia.org/wiki/Vector_space_model ). Я думаю, что вы пытаетесь научиться взвешивать термины, учитывая, насколько близки два вектора описания объектов друг к другу, например, с точки зрения упрощенной взаимной информации. Это может быть очень эффективным, поскольку вы можете хешировать термины в векторы, что означает, что вам не придется сравнивать объекты без общих функций. Тогда наивная модель будет иметь регулируемый вес для каждого члена (это может быть для каждого члена для каждого вектора, для каждого термина в целом или и того, и другого), а также порог. Модель векторного пространства - это широко используемый метод (например, в Apache Lucene, который вы можете использовать для решения этой проблемы), поэтому вы сможете многое узнать о нем путем дальнейшего поиска.
Позвольте мне дать очень простую формулировку этого на вашем примере. Учитывая bob: ['высокий', 'старый', 'смешной'], я извлекаю
откровенный: ['молодой »,' короткий, 'смешной'] steve: ['высокий»,' старый ',' сварливый '] джо: [' высокий ',' старый ']
поскольку я поддерживаю хеш из смешного -> {откровенный, ...}, высокий -> {стив, джо , ...} и старый -> {steve, joe, ...}
Я вычисляю что-то вроде общей взаимной информации: вес общих тегов / вес тегов bob. Если этот вес превышает порог, я включаю их в список.
Во время обучения, если я ошибаюсь, я изменяю общие теги. Если моя ошибка была откровенной, я уменьшаю вес для забавы, а если я ошибаюсь, не включая Стива или Джо, я увеличиваю вес для высоких и старых.
Вы можете сделать это настолько сложным, насколько захотите, например, включив веса для союзов терминов.