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

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

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

Social Network Analysis vs Network Sciecne (22.05.14)

Фактом давней и прочной ассоциации понятий «социальные сети» и Social Media уже сложно кого-то удивить, несмотря на то что они возникли с разницей в полвека. Однако в последнее время  наблюдается тенденция ассоциировать также и теоретические подходы, методы сбора и анализа данных и связанные с ними. Речь идёт о теоретико-методологическом подходе в социальных науках, который называется Social Network Analysis (SNA) и относительно новом направлении в информатике, математике и Computer Science под названием Network Science. Путаница между данными подходами основана прежде всего на том, что теоретические концепты, математические модели и связанные с ними методы сбора и анализа данных, разработанные в рамках одного из подходов зачастую бездумно копируются для решения задач в другом. При условии значительных различий между объектами и предметами исследований это может привести к ложным результатом.  Таким образом, главной целью данного доклада является сравнительный обзор обоих подходов для минимизации подобной путаницы и связанных с ней рисков. В частности, в докладе будет рассказано о ключевых исторических этапах в становлении обоих подходов, их основные теоретические предпосылки, наиболее известные работы и самые часто используемые методы. Также речь пойдёт о примерах исследований, в которых путаница подходов привела к нелепым, оскорбительным и даже опасным результатам.

Докладчик: Александр Семенов

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

Методы извлечения именованных сущностей из текстов с использованием категорийной структуры Википедии (29.04.14)

Задача распознавания именованных сущностей состоит в обнаружении и классификации элементов текста — слов и последовательностей слов — по предопределенным категориям. Примерами таких категорий могут являтся категории «личные имена» «географические названия», «названия организаций». Распознавание именованных сущностей находит применение в таких приложениях обработки естественного языка, как автоматизированный сбор новостей, вопросно-ответные системы, кросс-языковой информационный поиск, машинный перевод.

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

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

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

Предсказание сайтов связывания транскрипционных факторов в геноме (22.04.14)

Доклад повествует о решении одной из задач, решаемой совместно с Институтом общей генетики РАН. Задача состоит в том, чтобы предсказывать наиболее вероятные позиции в геноме, с которыми могут взаимодействовать специальные белки.

В докладе рассматриваются основные определения связанных с задачей биологических терминов и алгоритмические подходы к решению этой задачи.

Докладчик: Олег Борисенко

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

Методы поиска плагиата (15.04.14)

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

Рассматриваемые методы поиска плагиата: метод «Шинглов» и его модификации, I-Match, метод «Опорных» слов,
метод коэффициента совпадения документов, методы, основанные на использовании внешних поисковых систем.

Литература:
1) Зеленков Ю. Г. и Сегалович И. В. Сравнительный анализ методов определения нечетких дубликатов для Web
2) Potthast Martin Overview of the 4th International Competition on Plagiarism Detection.
3) Barrґon-Cede˜no Alberto и Rosso Paolo On Automatic Plagiarism Detection Based on n-Grams Comparison
4) Маннинг К., Рагхаван П., Шютце Х. Введение в информационный поиск.
5) Ilyinsky Sergey An efficient method to detect duplicates of Web documents with the use of inverted index.

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

Расчет семантической близости концепций с использованием связей в графе ссылок Википедии (08.04.14)

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

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

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

Докладчик: Максим Варламов

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

Обзор современных прикладных методов сжатия данных (01.04.14)

Данный доклад будет посвящён прикладным утилитам для экономии дискового пространства. Речь пойдет о возможностях сжатия blosc, LZ4, LZO, xz(lzma2), ZFS и о способах их использования. Будет рассмотрено применение распространённых средств сжатия данных в контексте разных классов задач. Доклад не будет затрагивать серьёзных теоретических основ методов сжатия данных.

Докладчик: Олег Борисенко

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

Современные методы викификации (25.03.14)

Лексическая многозначность — неотъемлемое свойство естественного языка, заключающееся в том, что слова и словосочетания могут иметь различную смысловую нагрузку в зависимости от окружающего их контекста. В компьютерной лингвистике задача автоматического определения корректных значений слов называется задачей разрешения лексической многозначности (РЛМ). Данная задача является одной из важнейших проблем обработки текстов.
Центральной частью любого современного метода РЛМ является база знаний — источник терминов, их возможных значений (концептов) и связей между ними. В последнее время наибольшее развитие получили методы РЛМ, база знаний которых основана на Википедии — огромном быстрорастущий ресурсе, покрывающем множество предметных областей. В роли концептов в таких базах знаний обычно выступают статьи Википедии, а в роли терминов — текстовые ссылки на них.
Задача поиска терминов в заданном тексте и связывание их с соответствующими статьями Википедии называется задачей викификации. Данная задача имеет такие важные приложения, как семантический поиск, классификация текстов и др.

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

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

Литература

* Milne D., Witten I. H. Learning to link with wikipedia //Proceedings of the 17th ACM conference on Information and knowledge management. – ACM, 2008. – С. 509-518.
* Ratinov L. et al. Local and global algorithms for disambiguation to wikipedia //Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1. – Association for Computational Linguistics, 2011. – С. 1375-1384.
* Cheng X., Roth D. Relational Inference for Wikification //Urbana. – 2013. – Т. 51. – С. 61801.
* Cai Z. et al. Wikification via link co-occurrence //Proceedings of the 22nd ACM international conference on Conference on information & knowledge management. – ACM, 2013. – С. 1087-1096.

Методы получения репрезентативной выборки пользователей социальной сети (18.03.14)

Для обучения и оценки качества методов анализа социальных сетей требуются данные: информация о пользователях реальных социальных сетей. Данный доклад посвящен одному из аспектов сбора таких данных — сэмплингу.
В рамках доклада будут рассмотрены различные способы получения репрезентативной выборки пользователей социальных сетей, так называемые, методы сэмплинга (англ. sampling). При этом будут освещены как классические подходы (поиск в ширину, случайные блуждания и др.), так и современные методы, которые «налету» используют извлекаемую в процессе скачивания информацию (например, сообщества пользователей) для повышения качества дальнейшего сбора.
От качества получаемой выборки сильно зависит качество алгоритмов, использующих эти данные. Поэтому будут рассмотрены различные критерии, по которым оценивается репрезентативность получаемой выборки пользователей. В конце доклада будет кратко рассказано о фреймворке MODIS Crawler, который предназначен для автоматического сбора данных из Интернета, в частности, из социальных сетей.

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

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

Список литературы:

1. Leskovec J., Faloutsos C. Sampling from large graphs //Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery
and data mining. — ACM, 2006. — С. 631-636.
http://www.stat.cmu.edu/~fienberg/Stat36-835/Leskovec-sampling-kdd06.pdf

2. PAKDD 2013 Tutorial: Sampling and Summarization for Social Networks
http://mslab.csie.ntu.edu.tw/tut-pakdd13/

3. Leskovec J., Kleinberg J., Faloutsos C. Graphs over time: densification laws, shrinking diameters and possible explanations
//Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining. — ACM, 2005. — С. 177-187.
http://eprints.pascal-network.org/archive/00001220/01/powergrowth-kdd05.pdf

4. Blenn N. et al. Crawling and detecting community structure in online social networks using local information //NETWORKING 2012. —
Springer Berlin Heidelberg, 2012. — С. 56-67.
http://repository.tudelft.nl/assets/uuid:61624ff0-d637-497a-9bf1-355638b63c7e/Crawling.pdf

Применение тематического моделирования для поиска агентов влияния в социальных сетях (11.03.14)

В рамках доклада планируется познакомить слушателей с тематическим моделированием (модели PLSA и RobustPLSA), с semi-supervised подходами к тематическому моделированию, с иерархическим тематическим моделированием (MASHA).

Будет описано применение этих подходов для решения задачи распределенного поиска агентов влияния в социальном графе.

Докладчик: Валерий Аванесов

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

Distributed Generation of Billion-node Social Graphs with Overlapping Community Structure (04.03.14)

In the field of social community detection, it is commonly accepted to utilize graphs with reference community structure for accuracy evaluation. The resulting accuracy value is obtained by directly comparing the ground-truth set of communities with the one produced by the algorithm. Therefore, a generic tool capable of generating random social graphs with realistic community structure and diverse properties is required. As soon as populations of modern social networks reach billion users in size, the tool must be scalable enough to produce synthetic networks of similar scale.

The method for generating large random social graphs with realistic community structure is introduced in the paper. The resulting graphs have several of recently discovered properties of social community structure which run counter to conventional wisdom: dense community overlaps, superlinear growth of number of edges inside a community with its size, and power law distribution of user-community memberships. Further, the method is by-design distributable and showed near-linear scalability in Amazon EC2 cloud using Apache Spark implementation.

Speaker: Kyrylo Chykhradze

presentation (pdf)