Какие алгоритмы подходят для этой простой задачи машинного обучения?

Question

У меня есть простой вопрос машинного обучения.

Вот основная проблема: мне неоднократно выдаётся новый объект и список описаний объекта. Например: new_object: 'bob' new_object_description: ['tall','old','funny']. Затем мне нужно использовать какое-то машинное обучение, чтобы найти ранее обработанные объекты, которые имеют 10 или менее наиболее похожих описаний, например, past_simil_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 очень дорогая для вычисления, и поэтому я использую алгоритм быстрого машинного обучения, чтобы попытаться угадать, какие объекты будут рядом, прежде чем я действительно выполню дорогой расчет.

Answer 1

Алгоритм, который, кажется, соответствует вашим требованиям (и, возможно, аналогичен тому, что предлагает Джон Статистик): Семантическое хеширование . Основная идея заключается в том, что он обучает глубокую сеть убеждений (тип нейронной сети, которую некоторые называют «нейронными сетями 2.0» и в настоящее время является очень активной областью исследований), чтобы создать хэш списка описаний объекта в двоичное число такое, что расстояние Хэмминга между числами соответствует аналогичным объектам. Поскольку для этого требуются только побитовые операции, он может быть довольно быстрым, и, поскольку вы можете использовать его для создания алгоритма в стиле ближайшего соседа, он естественным образом обобщается на очень большое количество классов. Это очень хороший современный материал. Недостаток: это не тривиально для понимания и реализации, и требует некоторой настройки параметров. Автор предоставляет код Matlab здесь . Несколько более простой для реализации алгоритм, тесно связанный с ним, - это локальное хеширование.

Теперь, когда вы говорите, что у вас есть дорогая функция расстояния, которую вы хотите быстро аппроксимировать, я вспомнил еще один очень интересный алгоритм, который делает это, Boostmap . Этот использует повышение для создания быстрой метрики, которая приближается к дорогой для вычисления метрики. В определенном смысле это похоже на приведенную выше идею, но используемые алгоритмы разные. У авторов этой статьи есть несколько статей по смежным методикам, все они довольно хорошего качества (опубликованные на ведущих конференциях), которые вы, возможно, захотите проверить.

Answer 2

вам действительно нужен алгоритм машинного обучения для этого? Какой у вас показатель сходства? Вы упомянули размерность количества объектов, а как насчет размера признака, установленного для каждого человека? Существует ли максимальное количество типов черт? Я мог бы попробовать что-то вроде этого:

1) Имейте черту отображения словаря в список имен с именем map

на каждого человека p

за каждую черту t в p

карта [т] .Добавьте (р);

2) затем, когда я хочу найти ближайшего человека, я беру свой словарь и создаю новый временный:

имя отображения словаря для подсчета называется cnt

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

для каждого человека p на карте [t]

CNT [р] ++;

, тогда запись с наибольшим счетом является ближайшей

---

Преимущество здесь в том, что карта создается только один раз. если черт на человека мало, а типы доступных черт велики, то алгоритм должен быть быстрым.

Answer 3

Вы можете использовать модель векторного пространства (http://en.wikipedia.org/wiki/Vector_space_model).. Я думаю, что вы пытаетесь научиться взвешивать термины при рассмотрении того, насколько близки два вектора описания объекта друг к другу, например, в терминах упрощенная взаимная информация. Это может быть очень эффективным, так как вы можете хэшировать от терминов до векторов, что означает, что вам не нужно сравнивать объекты без общих функций. Наивная модель будет иметь регулируемый вес за член (это может быть либо за член за вектор, за семестр в целом или за оба), а также за порог. Модель векторного пространства является широко используемым методом (например, в Apache Lucene, который вы могли бы использовать для этой задачи), поэтому вы будете быть в состоянии узнать много об этом через дальнейшие поиски.

Позвольте мне дать очень простую формулировку этого с точки зрения вашего примера. Учитывая Боб: ['высокий', 'старый', 'забавный'], я получаю

Фрэнк: ['молодой', 'короткий,' смешной '] Стив: ['высокий', 'старый', 'сварливый'] Джо: ['высокий', 'старый']

так как я поддерживаю хеш от забавного -> {frank, ...}, высокого -> {steve, joe, ...} и старого -> {steve, joe, ...}

Я вычисляю что-то вроде общей взаимной информации: вес общих тегов / вес тегов Боба. Если этот вес превышает порог, я включаю их в список.

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

Вы можете сделать это настолько сложным, насколько захотите, например, включив веса для сочетаний терминов.

Answer 4

SVM довольно быстрый. LIBSVM для Python, в частности, обеспечивает очень приличную реализацию машины опорных векторов для классификации.

Answer 5

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

Weka (Java) имеет реализацию этого в weka.classifiers.lazy.LWL

Answer 6

Этот проект отличается от типичных классификационных приложений двумя заметными способами:

• Вместо вывода класса, которому, как считается, принадлежит новый объект (или, возможно, вывода массива этих классов, каждый с уровнем вероятности / доверительной вероятности), «классификатор» предоставляет список «соседей», которые «близки» достаточно "для нового объекта.
• При каждой новой классификации целевая функция, независимая от классификатора, предоставляет список правильных «соседей»; в свою очередь исправленный список ( подмножество списка, предоставленного классификатором?) затем используется для обучения классификатора

Идея, стоящая за вторым пунктом, заключается в том, что, вероятно, будущие объекты, представленные в классификатор и имеющие сходство с текущим объектом, должны лучше "классифицироваться" (быть связанными с более правильным набором ранее замеченных объектов) с момента продолжающегося обучения восстанавливает связь с положительными (правильными) совпадениями, в то же время ослабляя связь с объектами, которые классификатор изначально ошибся.

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

Возможно, проблема масштабирования может быть решена с помощью двухэтапного процесса, с первым классификатором, основанным на алгоритме K-средних или чем-то подобным, что приведет к подмножеству всей совокупности объектов (объектов, которые ранее видели) как правдоподобные совпадения для текущего объекта (эффективно отфильтровывая, скажем, 70% или более от сбора). Эти возможные совпадения будут затем оцениваться на основе модели векторного пространства (особенно важно, если размеры элементов основаны на факторах, а не на значениях) или на некоторых других моделях. Основное предположение для этого двухэтапного процесса состоит в том, что коллекция объектов будет эффективно выставлять кластеры (она может быть просто относительно равномерно распределена по различным измерениям).

Еще один способ еще более ограничить число кандидатов для оценки по мере увеличения размера ранее замеченных объектов - это удалить почти дубликаты и сравнить только с одним из них (но в результате предоставить полный дубликат списка в результате, при условии, что если новый объект близок к «представителю» этого почти дублированного класса, все члены класса также будут совпадать)

С проблемой перетяжки сложнее справиться. Возможный подход заключается в том, чтобы [иногда] случайным образом добавлять объекты в список соответствия, который классификатор обычно не включает. Дополнительные объекты могут быть добавлены на основе их расстояния относительно расстояния до нового объекта (то есть, становится более вероятным, что будет добавлен относительно близкий объект)

Answer 7

глубокое обучение может быть использовано. http://www.deeplearning.net/tutorial/ просто перейдите по этой ссылке