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

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

Archive for the ‘Аннотации’ Category

Методы анализа тональности коротких сообщений (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

Исследование и разработка распределённых алгоритмов для поиска сообществ пользователей в социальных сетях

Доклад посвящен теме поиска сообществ пользователей в социальных графах. Освещены новые подходы к решению этой проблемы. Рассмотрен алгоритм решения задачи поиска максимальных клик в графе, являющейся базовой для большого числа алгоритмов поиска сообществ.

Докладчик: Сергей Рябов

Материалы:

  1. Conrad Lee, Fergal Reid, Aaron McDaid, Neil Hurley. Detecting Highly Overlapping Community Structure by Greedy Clique Expansion.
  2. Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments.

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

Эффективные методы замещения страниц в кэше XML СУБД (03.04.12)

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

Докладчик: Дмитрий Сиващенко

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

Разработка наукометрического индекса, устойчивого к спаму (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)

Извлечение отношений из текста (20.03.12)

Доклад посвящен задаче извлечения отношений из текста с целью восстановления значений атрибутов в частично заполненных отношениях (кортежах). Задача восстановления заключается в том, чтобы найти значения для таких атрибутов, удовлетворяющие исходному отношению. Поиск значений атрибутов осуществляется в текстовой коллекции на основе связей, полученных с помощью обучающих данных — кортежей, удовлетворяющих исходному отношению, в которых известны все значения атрибутов. В качестве примера может быть рассмотрена задача восстановить пропущенное значение в кортеже «Google — ?» на основе кортежей «Microsoft — Redmond» и «IBM — Armonk».
В докладе рассматриваются существующие системы извлечения отношений из текста (DIPRE, Snowball), а также собственная реализация системы, ориентированная на восстановление строк с пропущенными атрибутами.

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

Материалы:

  1. Nguyen Bach, Sameer Badaskar. A Survey on relation extraction (http://www.cs.cmu.edu/~nbach/papers/A-survey-on-Relation-Extraction-Slides.pdf)
  2. Sergey Brin. Extracting Patterns and Relations from the World Wide Web (http://ilpubs.stanford.edu:8090/421/1/1999-65.pdf)
  3. Eugene Agichtein, Luis Gravano. Snowball: Extracting Relations from Large Plain-Text Collections (http://www.mathcs.emory.edu/~eugene/papers/dl00.pdf)

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

Мультиязычные системы для автоматического реферирования (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)

Artificial General Intelligence (06.03.12)

Доклад рассказывает об Artificial General Intelligence (AGI), относительно недавно оформившейся поддисциплине Искусственного Интеллекта. Главная задача AGI — построение полноценного, насколько это возможно, универсального, человекоподобного интеллекта (в отличие от мейнстрима ИИ, занимающегося решением отдельных задач и разработкой узких методов, не охватывающих интеллект в целом).

Докладчик: Иван Белобородов

Материалы:

  1. Pei Wang, Ben Goertzel. Introduction: Aspects of Artificial General Intelligence (в Advances in Artificial General Intelligence: Concepts, Architectures and Algorithms (Proceedings of the AGI Workshop 2006), IOS Press, 2007).
  2. Artificial General Intelligence. Ben Goertzel, Cassio Pennachin (Eds.). Springer-Verlag, 2007.

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

Методы идентификации пользователей в онлайновых социальных сетях (28.02.12)

В настоящее время мы переживаем бум социальных интернет-сервисов. Каждый год появляется множество как общенаправленных, так и нишевых социальных сервисов, и для активных пользователей Интернет типично иметь несколько профилей в различных социальных сетях. Обнаружение профилей, принадлежащих одному человеку, в нескольких социальных сетях, позволяет получить более полный социальный граф, что может быть полезно во многих задачах, таких как информационный поиск, интернет-реклама, рекомендательные системы и т.д.

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

Докладчик: Бартунов Сергей

Материалы:

  • Veldman, I. (2009) Matching Profiles from Social Network Sites. Master’s thesis, University of Twente.
  • Gae-won Y., Seung-won H., Zaiqing N., Ji-Rong W. SocialSearch:Enhancing Entity Search with Social Network Matching. EDBT 2011.

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

Алгоритмы кластеризации на графах (13.12.11)

В докладе рассматриваются алгоритмы k-clique percolation, Керниган-Лин, Гирвана-Ньюмена, распространения меток. Вводится понятие модулярности сетевого сообщества.

Докладчик: Станислав Воробьев

Материалы:

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

Кластеризация: K-means, C-means, Fuzzy c-means, иерархические методы (6.12.11)

Кластеризация (англ.clustering) – это автоматическое разбиение множества элементов на группы (кластеры) в зависимости от степени их схожести.
В докладе рассказывается о самом понятии кластеризации и её основных алгоритмах. Приводится классификация алгоритмов кластеризации и разновидности функции-метрики. Проводится обзор некоторых методов кластеризации: метод k-средних, k-medoids, метод нечеткой кластеризации (fuzzy c-means), иерархические алгоритмы.
Также освещаются достоинства и недостатки рассмотренных методов.

Докладчик: Агаев Нурлан

Материалы:

  • Data Clustering (A.K. JAIN, M.N. MURTY, P.J. FLYNN), 1999 [http://nd.edu/~flynn/papers/Jain-CSUR99.pdf]
  • A Comprehensive Overview of Basic Clustering Algorithms (Glenn Fung), 2001
  • Principles and Theory for Data Mining and Machine Learning (Bertrand Clarke, Ernest Fokou´e, Hao Helen Zhang)
  • Лекции по алгоритмам кластеризации и многомерного шкалирования (К. В. Воронцов), 2007

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