Управление данными и информационные системы

Научный семинар отдела Информационных систем Института системного программирования им. В.П. Иванникова РАН

Posts Tagged ‘Турдаков Денис’

Лингвистические регулярности в явных и нейросетевых моделях векторного представления слов (29.09.15)

В одкладе рассматриваются результаты работы Леви и Голдберга, опубликованные в статье O. Levy, Y. Goldberg. Linguistic Regularities in Sparse and Explicit Word Representations, получившей приз за лучшую статью на конференции CoNLL, 2014.

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

Докладчик: Константин Архипенко.

Презентация: pdf

Видео: https://www.youtube.com/watch?v=Xp6La4pygcs

Методы выбора оптимального набора информативных признаков для задач классификации текстов (23.04.2013)

Доклад посвящен методам выбора оптимального набора информативных признаков (feature selection) для задач классификации текстов.

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

В докладе дан обзор методов выбора набора информативных признаков. Рассматриваются три основных группы методов: методы-фильтры (filters), методы-обертки (wrappers), встроенные методы (embedded), а также преимущества и недостатки методов каждой группы. Даны описания наиболее популярных методов, рассказано о применении этих методов на практике.

Докладчик: Татьяна Борисова

Материалы:

  1. http://en.wikipedia.org/wiki/Feature_selection
  2. Isabelle Guyon, Andr´e Elisseeff. An Introduction to Variable and Feature Selection. In Journal of Machine Learning Research 3 (2003), pages 1157-1182.
  3. Yiming Yang, Jan O. Pedersen. A comparative study on Feature Selection in Text Categorization. In Proceedings of the Fourteenth International Conference on Machine Learning (ICML’97), pages 412-420.
  4. Luis Carlos Molina, Lluís Belanche, Àngela Nebot. Feature Selection Algorithms: A Survey and Experimental Evaluation. In Proceedings of the 2002 IEEE International Conference on Data Proceedings of the 2002 IEEE International Conference on Data Mining, IEEE Computer Society, 306-313

Презентация с семинара

SimRank: теоретико-графовая мера близости и подходы к ее вычислению (05.03.2013)

В рамках доклада будет рассказано о мере оценки близости вершин в графе — SimRank. SimRank имеет рекурсивное определение и алгоритм вычисления  имеющий сложность O(N^4), где N — количество вершин.  Высокая вычислительная сложность не позволяет применить данную меру к реальным задачам, таким как анализ социальных сетей, где количество вершин может превышать сотни миллионов. Однако потенциальная польза подсчета близости вершин на основе SimRank заставляют исследователей искать более эффективные алгоритмы. Доклад будет посвящен обзору новых подходов к вычислению этой меры.

Докладчик: Денис Турдаков

Материалы:

  1. Glen Jeh and Jennifer Widom. 2002. SimRank: a measure of structural-context similarity. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining (KDD ’02). ACM, New York, NY, USA, 538-543.
  2. Dmitry Lizorkin, Pavel Velikhov, Maxim N. Grinev, Denis Turdakov: Accuracy estimate and optimization techniques for SimRank computation. VLDB J. 19(1): 45-66 (2010)
  3. Weiren Yu, Wenjie Zhang, Xuemin Lin, Qing Zhang, Jiajin Le: A space and time efficient algorithm for SimRank computation. World Wide Web 15(3): 327-353 (2012)
  4. Cuiping Li, Jiawei Han, Guoming He, Xin Jin, Yizhou Sun, Yintao Yu, and Tianyi Wu. 2010. Fast computation of SimRank for static and dynamic information networks. In Proceedings of the 13th International Conference on Extending Database Technology (EDBT ’10)

Методы обнаружения описания событий в социальной сети Твиттер (18.12.2012)

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

Докладчик: Виталий Мордань

Материалы:

  1. Deepayan Chakrabarti and Kunal Punera. Event Summarization using Tweets. Yahoo! Research, 701 1st Avenue. Sunnyvale, CA 94089.
  2. J. Allan, R. Papka, and V. Lavrenko. On-Line New Event Detection and Tracking. SIGIR. 1998.
  3. Takeshi Sakaki, Makoto Okazaki, Yutaka Matsuo. Earthquake Shakes Twitter Users: Real-time Event Detection by Social Sensors. The University of Tokyo. Yayoi 2-11-16, Bunkyo-ku. Tokyo, Japan.
  4. Yihong Gong, Xin Liu. Generic Text Summarization Using Relevance Measure and Latent Semantic Analysis. NEC USA, C & C Research Laboratories.

Презентация с семинара

Методы и проблемы извлечения информации из текстов (30.10.12)

Извлечение информации (information extraction) — это одно из направлений обработки текста на естественном языке, заключающееся в автоматическом извлечении структурированных данных из неструктурированных документов. В докладе будут рассмотрены основные задачи, возникающие при извлечении информации: распознавание именованных сущностей(Named-entity
recognition), извлечение отношений(Relation extraction), временной анализ(Temporal analysis) и извлечение событий(Event detection), а также принятые подходы для решения этих задач и возникающие при этом проблемы.

Докладчик: Алексей Лагута

Материалы:

  • Dan Jurafsky, James H. Martin. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. Prentice Hall Series in Artificial Intelligence.

Методы нормализации слов русского языка (09.10.12)

Нормализация слов естественных языков — приведение их к начальной форме — одна из проблем прикладной лингвистики, актуальная для информационного поиска, машинного перевода и других задач обработки текста. Как правило, задача нормализации разбивается на стемминг (поиск неизменяемой части слова) и синтез нормальной формы.
В докладе будут рассмотрены существующие методы нормализации естественных языков, имеющие реализацию для обработки русских слов.

Докладчик: Оксана Астапова

Материалы:

  1. Ilya Segalovich “A fast morphological algorithm with unknown word guessing induced by a dictionary for a web search engine”,  2003
  2. “Russian stemming algorithm” http://snowball.tartarus.org/algorithms/russian/stemmer.html
  3. А. Коваленко «Вероятностный морфологический анализатор русского и украинского языков» , 2002 http://www.keva.ru/stemka/stemka.html

Презентация с семинара (pdf)

Методы анализа тональности коротких сообщений (24.04.12)

Анализ тональности текстов (sentiment analysis) — область прикладной лингвистики, задачей которой является выявление в тексте эмоционально окрашенной лексики и эмоциональной оценки автора по отношению к объектам, речь о которых идет в тексте. В докладе будут рассмотрены некоторые методы, разработанные за последние 5 лет для анализа сообщений в микроблоге Twitter и других социальных медиа-сервисах.

Докладчик: Алексей Сильвестров.

Материалы:

  1. Thelwall, M., Buckley, K., Paltoglou, G. Cai, D., & Kappas, A. Sentiment strength detection in short informal text. // Journal of the American Society for Information Science and Technology, Vol., 2544–2558. 2010.
  2. Pang B. & Lee L. Opinion Mining and Sentiment Analysis // Foundations and Trends in Information Retrieval, v.2 n.1-2, January, 2008 — pp.1-135.
  3. Aspect-Based Opinion Polling from Customer Reviews by Jingbo Zhu, Huizhen Wang, Muhua Zhu, Benjamin K Tsou, Matthew Ma // IEEE TRANSACTIONS ON AFFECTIVE COMPUTING, VOL. 2, NO. 1, JANUARY-MARCH 2011

Разработка наукометрического индекса, устойчивого к спаму (27.03.12)

Доклад посвящен задаче ранжирования исследователей при помощи анализа их публикаций.
Будут рассмотрены существующие решения, такие как импакт-фактор, индекс Хирша(h-индекс) и m-индекс, будут освещены их достоинства и недостатки.
Кроме того, в докладе будет рассмотрен новый алгоритм ранжирования, основанный на анализе направленного графа связей между публикациями.

Докладчик: Александр Пироженко

Материалы:

  1. Adler, R., Ewing, J., & Taylor, P. C. (2009). Citation statistics: a report from the International Mathematical Union (IMU) in cooperation with the International Council of Industrial and Applied Mathematics (ICIAM) and the Institute of Mathematical Statistics (IMS). Statist. Sci. , 1-14.
  2. Campbell, P. (2008). Escape from the impact factor. Ethics in Science and Environmental , 5-7.
  3. Kleinberg, J. (1999). Authoritative sources in a hyperlinked environment. JACM , 604-632.
  4. Lawrence, P. A. (2008). Lost in publication: how measurement harms science. Ethics in Science and Environmental Politics , 9-11.

презентация с семинара (pptx)

Мультиязычные системы для автоматического реферирования (13.03.12)

Выделение главных мыслей в виде реферата или конспекта интересовало человечество со времен появления письменности. С появлением интернета тема приобрела новую актуальность, так как нынешние объемы информации огромны и постоянно возрастают. Существует множество областей, в которых применение такого, сокращенного представления давало бы существенный выигрыш. Например, система может быть полезна для человека, который должен по большому количеству статьей на определенную тему быстро получить представление о данной области. Автоматическое реферирование также можно использовать в поисковых системах для того, чтобы уменьшать область поиска.
Рефераты бывают нескольких типов: информативные, индикативные и критические. Индикативные рефераты должны предоставлять достаточно информации для принятия решения, стоит ли обращаться к оригиналу. Информативные рефераты должны сжимать исходный текст. Критические рефераты не только сокращают, но и дают оценку тексту.
Существует два основных подхода к автоматическому реферированию. Первый подход ориентирован на извлечение важных фрагментов, обычно предложений так называемый sentence extraction. Второй подход использует сложные методы семантического и лингвистического анализа, обычно это генерация рефератов (summary generation) на основе семантического представления текста.

Особый интерес представляет тестирование разных методов. Ручная проверка является через чур дорогой, требующей порядка 3000 человеко-часов на каждую систему. Автоматические проверки осложняются тем, что даже написанные разными людьми резюме одного текста, может сильно отличатся. В настоящее время, системой тестирования «дэ факто» является ROGUE. ROGUE сравнивает для каждого документа, из тестового набора, резюме полученной системой, с несколькими вручную сделанными резюме.

Докладчик: Борис Павлович

Материалы:

  1. Mani, I. and Maybury, M. (editors) (1999) Advances in Automatic Text Summarization // MI T Press.
  2. Hans Peter Luhn. 1958. The automatic creation of literature abstracts // IBM Journal of Research and Development, 2(2), 159-165
  3. Яцко В.А. Симметричное реферирование: теоретические основы и методика // НТИ. Сер.2. 2002. № 5. С.18-28.
  4. Tibor Kiss and Jan Strunk. 2006. Unsupervised multilingual sentence boundary detection // Computational Linguistics, 32(4):485–525.
  5. Dunning, Ted. 1993. Accurate methods for the statistics of surprise and coincidence // Computational Linguistics, 19(1):61–74.
  6. Riley, Michael D. 1989. Some applications of tree-based modeling to speech and language indexing // In Proceedings of the DARPA Speech and Natural Language Workshop, pages 339–352, Cape Cod, Massachusetts.
  7. Müller, Hans, V. Amerl, and G. Natalis. 1980. Worter kennungs verfahren als Grundlageeiner Universal methode zur automatischen Segmentierung von Texten in Sätze. Ein Verfahren zur maschinellen Satz grenzen bestimmung im Englischen // SpracheundDatenverarbeitung, 4(1):46–64.
  8. Stanley F. Chenand Joshua T. Goodman. 1998. An empirical study of smoothing techniques for language modeling // Technical Report TR-10-98, Harvard University.

презентация с семинара (pptx)

Введение в информационный поиск (18.10.11)

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

Докладчик: Марина Макиенко

Материалы:

  • Christopher D. Manning, Prabhakar Raghavan “Introduction to information retrieval”,  Cambridge University Press. 2008. (Глава 6)

Презентация к семинару (pptx)