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

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

Archive for Март, 2013

Распределённый расчёт графовых статистик на реальных и синтетических социальных графах (02.04.2013)

Доклад посвящён исследованию графовых свойств и характеристик социальных сетей (эффективный диаметр, средняя степень вершин, распределение степеней вершин, коэффициент кластеризации и др.), а также их вычислению с помощью Stanford Network Analysis Platform и распределённому вычислению на базе GraphLab при помощи эффективных алгоритмов (например, HADI для диаметра графа). Почему распределение степеней вершин подчиняется закону power law? Каковы средняя степень вершины и эффективный диаметр графа Facebook? Как за приемлемое время вычислить диаметр графа порядка ~1М вершин? Какими топологическими свойствами обладает граф Facebook? Вот лишь некоторое множество вопросов, которые будут раскрыты на семинаре.

Докладчик: Кирилл Чихрадзе

Материалы:

  1. U Kang, Charalampos Tsourakakis, Ana Paula Appel, Christos Faloutsos, Jure Leskovec. «HADI: Fast Diameter Estimation and Mining in Massive Graphs with Hadoop». CMU-ML-08-117, 2008.
  2. Jure Leskovec. «Dynamics of Large Networks». CMU-ML-08-111, 2008.
  3. Johan Ugander, Brian Karrer, Lars Backstrom, Cameron Marlow. «The Anatomy of the Facebook Social Graph». CoRR(2011)
  4. Emilio Ferrara, Giacomo Fiumara. «Topological Features of Online Social Networks». Communications on Applied and Industrial Mathematics, 2(2):1-20, 2011

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

Автоматическое обогащение неформальной онтологии на основе текстов определенной предметной области (26.03.2013)

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

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

Докладчик: Никита Астраханцев

Материалы:

  1. Н.А. Астраханцев, Д.Ю. Турдаков. “Методы автоматического построение и обогащения неформальных онтологий”. Программирование, Т.39, №1, с. 23-34, 2013.
  2. C. Biemann. Ontology Learning from Text: A Survey of Methods. LDV Forum, vol. 20, pp. 75-93, 2005.
  3. A. Faatz, S. Hörmann, C. Seeberg, and R. Steinmetz, “Conceptual enrichment of ontologies by means of a generic and configurable approach,” in Proceedings of the ESSLLI 2001 Workshop on Semantic Knowledge Acqusition and Categorisation, 2001.
  4. P. Buitelaar, P. Cimiano, and B. Magnini, Ontology Learning from Text: Methods, Evaluation And Applications, ser. Frontiers in Artificial Intelligence and Applications. IOS Press, 2005.

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

Методы извлечения терминологии (19.03.2013)

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

  1. Извлечение кандидатов, то есть слов и словосочетаний, которые могут являться терминами.
  2. Вычисление признаков, позволяющих распознавать термины среди кандидатов, например: TF, TF*IDF, CValue, Domain Relevance, Domain Consensus, Lexical Cohesion, T-test.
  3. Распознавание терминов с помощью некоторой эвристики или алгоритма машинного обучения.

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

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

Материалы:

  1. M. Pazienza, M. Pennacchiotti, and F. Zanzotto. Terminology extraction: an analysis of linguistic and statistical approaches. Knowledge Mining, pages 255–279, 2005.
  2. Lars Ahrenberg. Term extraction: A review draft version 091221. 2009.
  3. Ziqi Zhang, Christopher Brewster, and Fabio Ciravegna. A comparative evaluation of term recognition algorithms. In Proceedings of the Sixth International Conference on Language Resources and Evaluation (LREC08), Marrakech, Morocco, 2008.
  4. A. Patry and P. Langlais. Corpus-based terminology extraction. In Terminology and Content Development–Proceedings of 7th International Conference On Terminology and Knowledge Engineering, Litera, Copenhagen, 2005.
  5. J. Foo. Term extraction using machine learning. 2009.

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

Автоматизация процесса нормализации информации при внедрении систем управления основными данными (12.03.2013)

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

Докладчик: Ярослав Недумов

Материалы

  1. Леонид Черняк. Интеграция данных: синтаксис и семантика. Открытые системы, 10, 2009.
  2. ME Califf and RJ Mooney. Relational learning of pattern-match rules for information extraction. In: Proceedings of the Sixteenth National Conference on Artificial Intelligence (AAAI-99), Menlo Park, CA, American Association for Artificial Intelligence, pages 328-334, 1999
  3. Sofiane Ouaguenouni, Kumar Sivaraman, and Terry Braun. Identity resolution and data quality algorithms for master person index. An Oracle White Paper, August 2010.
  4. Erhard Rahm and Hong Hai Do. Data cleaning: Problems and current approaches. IEEE Data Engineering Bulletin, 23:2000, 2000.

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