Поэтапно обучаемый классификатор распознавания сущностей

Question

Я занимаюсь исследованием семантической сети / nlp, и у меня есть набор разреженных записей, содержащих смесь числовых и нечисловых данных, представляющих сущности, помеченные различными функциями, извлеченными из простых английских предложений.

, например

uid|features
87w39423|speaker=432, session=43242, sentence=34, obj_called=bob,favorite_color_is=blue
4535k3l535|speaker=512, session=2384, sentence=7, obj_called=tree,isa=plant,located_on=wilson_street
23432424|speaker=997, session=8945305, sentence=32, obj_called=salty,isa=cat,eats=mice
09834502|speaker=876, session=43242, sentence=56, obj_called=the monkey,ate=the banana
928374923|speaker=876, session=43242, sentence=57, obj_called=it,was=delicious
294234234|speaker=876, session=43243, sentence=58, obj_called=the monkey,ate=the banana
sd09f8098|speaker=876, session=43243, sentence=59, obj_called=it,was=hungry
...

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

, например

uid|sameas
87w39423|234k2j,234l24jlsd,dsdf9887s
4535k3l535|09d8fgdg0d9,l2jk34kl,sd9f08sf
23432424|io43po5,2l3jk42,sdf90s8df
09834502|294234234,sd09f8098
...

Какой алгоритм (ы) я бы использовал для постепенного обучения классификатора, который мог бы использовать набор функций, и мгновенно рекомендовал бы N наиболее похожих UID и вероятность того, действительно ли эти UID представляют собой такая же сущность? При желании я также хотел бы получить рекомендации по отсутствующим функциям для заполнения, а затем провести повторную классификацию, чтобы получить более определенные совпадения.

Я исследовал традиционные приближенные алгоритмы ближайшего соседа. такие как FLANN и ANN , и я не думаю, что они будут подходящими, поскольку они не обучаемы (в смысле контролируемого обучения), и при этом они, как правило, не предназначены для разреженных числовой ввод.

В качестве очень наивной первой попытки я думал об использовании наивного байесовского классификатора путем преобразования каждого отношения SameAs в набор обучающих выборок. Таким образом, для каждой сущности A с такими же отношениями B, я бы повторял каждую и обучал классификатор как:

classifier = Classifier()
for entity,sameas_entities in sameas_dataset:
    entity_features = get_features(entity)
    for other_entity in sameas_entities:
        other_entity_features = get_features(other_entity)
        classifier.train(cls=entity, ['left_'+f for f in entity_features] + ['right_'+f for f in other_entity_features])
        classifier.train(cls=other_entity, ['left_'+f for f in other_entity_features] + ['right_'+f for f in entity_features])

А затем используйте его как:

>>> print classifier.findSameAs(dict(speaker=997, session=8945305, sentence=32, obj_called='salty',isa='cat',eats='mice'), n=7)
[(1.0, '23432424'),(0.999, 'io43po5', (1.0, '2l3jk42'), (1.0, 'sdf90s8df'), (0.76, 'jerwljk'), (0.34, 'rlekwj32424'), (0.08, '09843jlk')]
>>> print classifier.findSameAs(dict(isa='cat',eats='mice'), n=7)
[(0.09, '23432424'), (0.06, 'jerwljk'), (0.03, 'rlekwj32424'), (0.001, '09843jlk')]
>>> print classifier.findMissingFeatures(dict(isa='cat',eats='mice'), n=4)
['obj_called','has_fur','has_claws','lives_at_zoo']

Насколько жизнеспособен этот подход? Первоначальное пакетное обучение было бы ужасно медленным, по крайней мере, O (N ^ 2), но поддержка инкрементного обучения позволила бы обновлениям происходить быстрее.

Какие подходы лучше?

Answer 1

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

Возможно, вы захотите взглянуть на кластеризацию под наблюдением. В результате краткого поиска в Google появилась статья Активное полу-наблюдение за попарно-ограниченной кластеризацией , которая дает псевдокод для алгоритма, который является инкрементным / активным и использует наблюдение в том смысле, что он принимает данные обучения, указывающие, какие объекты являются или являются не в том же кластере. Вы можете легко получить это из своих данных, предположив, что, например, uids 87w39423 и 4535k3l535 - это определенно разные вещи.

Однако, чтобы это работало, вам нужно придумать метрику расстояния, основанную на функциях в данных. У вас есть много вариантов здесь, например, вы можете использовать простое расстояние Хемминга для объектов, но выбор метрической функции здесь немного произвольный. Я не знаю ни одного хорошего способа выбора метрики, но, возможно, вы уже рассматривали это, когда рассматривали алгоритмы ближайшего соседа.

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

Могут быть и другие подходящие подходы, если вопрос, на который вы хотели ответить, был чем-то вроде «заданной сущности, какие другие сущности могут относиться к тому же самому?», Но я не думаю, что это то, что вам нужно .

Answer 2

Возможно, вы захотите взглянуть на этот метод:

«Крупномасштабное онлайн-изучение сходства изображений через ранжирование» Гал Чечик, Варун Шарма, Ури Шалит и Сами Бенжио, журнал машинного обученияИсследования (2010).[ PDF ] [ Домашняя страница проекта ]

Больше мыслей:

Что вы подразумеваете под «сущностью»?Является ли сущность той вещью, на которую ссылается obj_called?Используете ли вы содержимое 'obj_called' для сопоставления разных сущностей, например, "Джон" похож на "Джон Доу"?Используете ли вы близость между предложениями для обозначения похожих объектов?Какова главная цель (задача) картирования?