Семинар "Классификация данных, представленных графами, методом опорных векторов с помощью ядер". Докладчик - Кашницкий Юрий

В четверг, 30 октября 2014 года, состоится очередное заседание семинара "Математические модели информационных технологий"  департамента анализа данных и искусственного интеллекта и НУЛ "Интеллектуальные системы и структурный анализ" под руководством С.О. Кузнецова.

Место проведения: Кочновский проезд, 3. ауд.327, 16.40

Аннотация: Метод опорных векторов, предложенный в 1963 году советскими учеными Владимиром Вапником и Алексеем Червоненкисом, - это алгоритм построения оптимальной разделяющей гиперплоскости в задаче бинарной классификации данных, представленных численными векторами. Один из этапов алгоритма классификации SVM, нахождение максимального зазора между объектами разных классов, формулируется как задача квадратичной оптимизации с граничными условиями Куна-Таккера, поэтому алгоритм обладает своего рода математической красотой, и сразу привлек на себя внимание в сообществе машинного обучения.

Позднее, только в конце XX века,  SVM стал во много раз мощнее за счет использования ядерных функций, которые позволили значительно упростить задачу квадратичной оптимизации и строить очень сложные разделяющие гиперплоскости, используя при этом лишь подвыборку данных (опорные вектора) для классификации тестовых объектов. Интуитивно, суть ядра – метрика сходства между двумя объектами. Самыми популярными ядрами стали полиномиальное и гауссово (радиальная базисная функция). Однако вскоре оказалось, что в таких задачах, где входные данные имеют более сложное описание, нежели просто вектора чисел, целесообразно использовать другие ядра. Например, при автоматической обработке текста сходство строк определяют с помощью строкового ядра (string kernel).

Описания в виде графов появляются, например, в задаче предсказательной токсикологии, где вещества представлены их упрощенной молекулярной структурой, или опять же, в задаче автоматической обработки текста при анализе настроений (sentiment analysis), где предложение представляется деревом разбора (parse tree), а абзац текста, соответственно, чащей разбора (parse thicket), то есть, по сути, тоже деревом. Также графами представляются социальные сети и сети генной коэкспресии, поток выполнения программ (program flow) и структура протеинов и РНК.

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

Приглашаются все желающие.

Для студентов, аспирантов, преподавателей и сотрудников Высшей школы экономики - вход свободный.

При необходимости заказа пропуска в здание НИУ ВШЭ просьба сообщить по e-mail: lantropova@hse.ru<mailto:lantropova@hse.ru>.