Archive for Февраль, 2013

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.

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