Семинары 2012 года
25.12.2012
Speaker: BorisGalitsky, eBayInc., SanJoseCAUSA.Title: Multi-Sentence Search Using Parse Thicket.
Annotation: We develop a graph representation and learning technique for parse structures for sentences and paragraphs of text. This technique is used to improve relevance answering complex questions where an answer is included in multiple sentences. We introduce Parse Thicket (PT) as a union of syntactic parse trees augmented by a number of arcs for inter-sentence word-word relations such as coreference and taxonomic relations. These arcs are also derived from other sources, including Speech Act and Rhetoric Structure theories, and respective indexing rules are introduced, which identify inter-sentence relations and joins phrases connected by these relations in the search index.
Generalization of syntactic parse trees (as a similarity measure between sentences) is defined as a set of maximum common sub-trees for two parse trees. Generalization of a pair of PTs to measure relevance of a question and an answer (distributed in multiple sentences) is defined as finding a set of maximal common sub-graphs of this pair of PTs.
The proposed approach is evaluated in the product search domain of eBay.com, where user query includes product names, features and expressions for user needs, and query keywords occur in different sentences of text. Another evaluation setting is based on re-ranking Yahoo and Bing search API results. We compare the improvement of search relevance achieved by re-ranking via sentence-level syntactic generalization with that of PT. It is demonstrated that search relevance is improved by single sentence-level generalization, and further increased by PT generalization.
15.11.2012
Докладчик: Борисенко Владимир Витальевич, Мехмат МГУ, Отделение прикладной математики и информатики НИУ ВШЭ.Тема: Поиск оптимальных тетраэдрических сетей в трехмерном пространстве.
Аннотация: Рассматриваются правильные разбиения 3-х мерного пространства на тетраэдры - тетраэдрические сети. Ограничиваемся случаем сетей, инвариантных относительно трех сдвигов на базисные векторы, т.е. периодических. Подобные сети используются в трехмерной компьютерной графике для построения триангуляции трехмерной поверхности, заданной функцией f(x, y, z) = const, с помощью ячеечных методов. Качество триангуляции поверхности зависит от качества сети: чем ближе тетраэдры сети к правильным, тем выше качество триангуляции. К сожалению, разбиение пространства на правильные тетраэдры невозможно. Мерой близости тетраэдра к правильному является параметр AspectRatio, равный отношению радиусов описанной и вписанной в тетраэдр сфер (для правильного тетраэдра AspectRatio = 3, для произвольного >= 3). Задача состоит в том, чтобы построить сеть, наилучшую по параметру AspectRatio (среднему или максимальному для тетраюдров сети), а также обладающую дополнительными хорошими свойствами (тетраэдры равны, зеркально симметричны и т.п.).
08.11.2012
Докладчик: Стариковская Татьяна Андреевна, аспирантка механико-математического факультета МГУ им. М.В. Ломоносова.Тема: Оптимальное выравнивание и наибольшая общая подпоследовательность двух строк.
Аннотация: В докладе будет рассказано о задаче о выравнивании двух строк и о ее частном случае - задаче о наибольшей общей подпоследовательности. Обе задачи имеют приложения, в частности, в биоинформатике и анализе текстов.В первой части доклада будет дан обзор основных вариантов задачи о выравнивании двух строк. Выравнивание двух строк можно рассматривать как последовательность операций удаления, вставки и замены букв, преобразующих одну строку в другую. В зависимости от того, как оценивается стоимость выравнивания, оптимальное выравнивание позволяет понять, насколько похожи сами строки, или найти подстроки максимального сходства.
Во второй части доклада будет рассмотрен частный случай задачи о выравнивании двух строк – задача о наибольшей общей подпоследовательности. Эта задача проще с вычислительной точки зрения, и для нее существует ряд эффективных алгоритмов. В докладе будет дан обзор основных алгоритмов, в частности, будут рассказаны идеи алгоритма Вагнера-Вишера, алгоритма Хиршберга, алгоритма Ханта-Сцимански, алгоритма Масека и др.
25.10.2012
Speaker: Steffen Hoelldobler (Technical University Dresden, Institute for Artificial Intelligence, Head).Title: Human Reasoning and Computational Logic.
Annotation: A novel approach to human conditional reasoning based on the three-valued Lukasiewicz logic is presented. I will demonstrate that the Lukasiewicz logic overcomes problems the so-far proposed Fitting logic has in reasoning with the so-called suppression task. The approach can be implemented by an appropriate connectionist network. While adequately solving the suppression task, the approach gives rise to a number of open questions concerning the use of Lukasiewicz logic, contractions, completion versus weak completion, explanations, negation, and sceptical versus credulous approaches in human reasoning.
17.10.2012
Докладчик: Д.А. Паперно, Университет штата Калифорния, Лос Анджелес (UCLA).Тема: О проекте COMPOSES.
Аннотация: Проект COMPOSES соединяет идеи семантической композициональности с корпусными методами компьютерной лингвистики. Одна из стандартных задач компьютерной лингвистики - распознавание свойств слов, частей слов и других языковых единиц на основе статистического анализа корпусов текстов. (Пример: автоматическая классификация значений глаголов по их частотным характеристикам). Подобные задачи ставились уже на заре компьютерной лингвистики и современных компьютерных технологий (например, выделение гласных и согласных букв по статистике их встречаемости, автоматическое выделение морфем и т.п.). Статистические методы такого рода зачастую упрекают в том, что они теряют из виду продуктивную природу языка, в частности то, что значения сложных выражений складываются из значений их частей (так наз. композициональность). Например, значение фразы «зеленый шарик» включает в себя значения слов «зеленый» и «шарик».
Проект COMPOSES (COMPositional Operations in SEmantic Space) стремится восполнить этот пробел. COMPOSES аппроксимирует значения слов как многомерные векторы, отражающие частоту встречаемости слова в разных контекстах. Значение фраз (напр. greenball) получается из значений составляющих их слов (напр. ball) посредством операций над векторами. В зависимости от синтаксической связи между словами применяются различные операции.
20.09.2012
Докладчик: Ревенко Артем Викторович, аспирант кафедры анализа данных и искусственного интеллекта ОПМИ, НИУ ВШЭ.Тема: Построение интерактивного инструмента анализа данных: задача нахождения ошибок.
Аннотация: В докладе рассматривается задача построения интерактивного инструмента на основе методов анализа формальных понятий на примере математических данных. Обсуждается общий план работы по построению, выделяется сделанная часть и дальнейший план работ. Отдельное внимание уделено задаче нахождения ошибок в данных, как приоритетной при построении интерактивного многопользовательского инструмента. Обсуждается предложенный подход на основе применения свойств оператора замыкания. Данный подход сравнивается с другими подходами к исправлению ошибок в данных, в частности, с подходом, основанном на методе ближайших соседей. Проводится анализ сложности алгоритмов, обсуждаются приложения.
14.06.2012
Докладчик: Четверкин Илья Игоревич, аспирант ВМК МГУ им. М.В. Ломоносова.Тема: Методы анализа тональности текстов и их тестирование на семинаре РОМИП-2011.
Аннотация: В докладе рассказано об особенностях задачи анализа тональности текстов, основных методах, применяемых для решения этой задачи. Также будут представлены результаты проведенного соревнования по автоматической обработке мнений пользователей на русском языке в рамках Российского семинара по информационному поиску РОМИП-2011.
01.01.2012
Докладчик: Кашницкий Юрий, аспирант НИУ ВШЭТема: Классификация данных, представленных графами, методом опорных векторов с помощью ядер
Аннотация: Метод опорных векторов, предложенный в 1963 году советскими учеными Владимиром Вапником и Алексеем Червоненкисом, - это алгоритм построения оптимальной разделяющей гиперплоскости в задаче бинарной классификации данных, представленных численными векторами. Один из этапов алгоритма классификации SVM, нахождение максимального зазора между объектами разных классов, формулируется как задача квадратичной оптимизации с граничными условиями Куна-Таккера, поэтому алгоритм обладает своего рода математической красотой, и сразу привлек на себя внимание в сообществе машинного обучения.
Позднее, только в конце XX века, SVM стал во много раз мощнее за счет использования ядерных функций, которые позволили значительно упростить задачу квадратичной оптимизации и строить очень сложные разделяющие гиперплоскости, используя при этом лишь подвыборку данных (опорные вектора) для классификации тестовых объектов. Интуитивно, суть ядра – метрика сходства между двумя объектами. Самыми популярными ядрами стали полиномиальное и гауссово (радиальная базисная функция). Однако вскоре оказалось, что в таких задачах, где входные данные имеют более сложное описание, нежели просто вектора чисел, целесообразно использовать другие ядра. Например, при автоматической обработке текста сходство строк определяют с помощью строкового ядра (string kernel).
Описания в виде графов появляются, например, в задаче предсказательной токсикологии, где вещества представлены их упрощенной молекулярной структурой, или опять же, в задаче автоматической обработки текста при анализе настроений (sentiment analysis), где предложение представляется деревом разбора (parse tree), а абзац текста, соответственно, чащей разбора (parse thicket), то есть, по сути, тоже деревом. Также графами представляются социальные сети и сети генной коэкспресии, поток выполнения программ (program flow) и структура протеинов и РНК.
На семинаре мы рассмотрим различные ядра, которые используют для определения сходства между описаниями объектов в виде графов в задаче классификации. Мы отметим их достоинства и недостатки, способность выражения структурной природы (expressiveness) и вычислительную сложность.
Нашли опечатку?
Выделите её, нажмите Ctrl+Enter и отправьте нам уведомление. Спасибо за участие!
Сервис предназначен только для отправки сообщений об орфографических и пунктуационных ошибках.