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

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

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

Распределённый расчёт графовых статистик на реальных и синтетических социальных графах (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.

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

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)

Байесовский вывод и Тьюринг-полные модели (26.02.2013)

Доклад посвящен дополнительным аспектам машинного обучения, основанного на байесовском выводе, в приложении к деревьям и графам решений. Сравниваются метод выбора модели maximum a posteriori (MAP) и получение модели матожиданием по постериорным вероятностям (байесовской оценкой); описывается процедура эффективного вычисления байесовской оценки для деревьев и графов решений. Рассматриваются способы задания первичных вероятностей для байесовского вывода. Графы решений обобщаются до Тьюринг-полных моделей, рассматриваются преимущества и недостатки данного класса моделей. Вкратце рассматриваются возможности применения описанных методов машинного обучения в производственных процессах.

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

Материалы:

  1. Jaynes, E.T. 2003. Probability Theory: The Logic of Science.
  2. Veness, J., Ng, K.S., Hutter, M., Uther, W., and Silver, D. 2011. A Monte-Carlo AIXI Approximation. Journal of Artificial Intelligence Research 40, 95–142.
  3. Looks, M. 2006. Competent Program Evolution. Doctoral Dissertation.

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

Деревья и графы решений. Принцип Minimum Message Length и байесовский вывод (19.02.2013)

В докладе будет рассказано о методах машинного обучения, основанных на построении деревьев и графов решений с использованием принципа Minimum Message Length и байесовского вывода. Формулируется принцип Minimum Message Length сравнения моделей, показывается его связь с байесовским выводом. Строится процедура вывода деревьев решений из обучающих данных, вводятся графы решений как обобщение деревьев решений.

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

Материалы:

  1. Quinlan, J.R. and Rivest, R.L. 1989. Inferring Decision Description Trees Using the Minimum Length Principle. Information and Computation 80, 227–248.
  2. Wallace, C.S. and Patrick, J.D. 1993. Coding Decision Trees. Machine Learning 11, 7–22.
  3. Oliver, J.J. 1993. Decision Graphs — An Extension of Decision Trees.
  4. Tan, P.J. and Dowe, D.L. 2002. MML Inference of Decision Graphs with Multi-Way Joins. Proceedings of the 15th Australian Joint Conference on Artificial Intelligence, 131–142.

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

Методы обнаружения описания событий в социальной сети Твиттер (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.

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

Тематическое моделирование текстов с учетом временного фактора (11.12.2012)

Доклад посвящен аспектам тематического моделирования динамических коллекций текстовых документов, то есть коллекций, документы которых разделены на группы в соответствие с временем их создания. Также будет рассмотрена динамическая вероятностная тематическая модель (Dynamic Hierarchical Dirichlet Process Model), позволяющая моделировать такие коллекции документов.

Докладчик: Кристина Чуприна

Материалы:

  1. Mining Text Data (Springer) Ed. Charu Aggarwal, ChengXiang Zhai, March 2012. Chapter 8.
  2. A. Ahmed, E. Xing. Timeline: A Dynamic Hierarchical Dirichlet Process Model for Recovering Birth/Death and Evolution of Topics in Text Stream, 2012.

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

Вероятностные тематические модели (4.12.2012)

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

  • Latent Dirichlet Allocation (Скрытое размещение Дирихле)
  • Hierarchical Latent Dirichlet Allocation (Иерархическое скрытое размещение Дирихле)

Также будет рассказано об оценке качества вероятностных тематических моделей.

Докладчик: Андрей Гомзин

Материалы:

  1. Mining Text Data (Springer) Ed. Charu Aggarwal, ChengXiang Zhai, March 2012. Chapters 5 and 8.
  2. Blei, David M. (April 2012). Introduction to Probabilistic Topic Models. Comm. ACM 55 (4): 77-84. [PDF]
  3. D. Blei, T. Griffiths, M. Jordan, and J. Tenenbaum. Hierarchical topic models and the nested Chinese restaurant process. Neural Information Processing Systems 16, 2003 [PDF]

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