Статистический кластерный анализ (регулярный семинар)

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(→Литература)
(→Заседания)
 
(38 промежуточных версий не показаны.)
Строка 15: Строка 15:
== Заседания ==
== Заседания ==
-
13 октября 2015 г.
+
=== 13 октября 2015 г. ===
-
Игорь Силин "Минимаксное оценивание в Stochastic Block Models"
+
'''Игорь Силин "Минимаксное оценивание в Stochastic Block Models"'''
-
28 октября 2015 г.
+
В докладе будет рассмотрена популярная вероятностная модель Stochastic Block Model, используемая для доказательств свойств алгоритмов community detection. Будет получена минимаксная оценка риска для квадратичной функции потерь. Для этого сначала будет предъявлен метод, достигающий необходимой скорости сходимости, а затем будет доказано, что его нельзя улучшить. Для доказательства нижней оценки используется классический инструмент - неравенство Фано.
 +
 
 +
=== 28 октября 2015 г. ===
1. Игорь Силин — продолжение рассказа
1. Игорь Силин — продолжение рассказа
Строка 25: Строка 27:
2. Обсуждение тем курсовых работы для студентов программы ММОС.
2. Обсуждение тем курсовых работы для студентов программы ММОС.
 +
=== 11 ноября 2015 г. ===
 +
 +
'''Константин Славнов "Методы выделения сообществ в применении к анализу социальных сетей"'''
 +
 +
Обзорный доклад, который посвящен теме социальных графов и обзору способов выделения сообществ на основе функционала модулярности. Будут рассмотрены некоторые свойства модулярности, 7 алгоритмов выделения структуры сообществ (Betweenness, Fastgreedy, Multilevel, LabelPropogation, Walktrap, Infomap, Eigenvector), а также рассказаны собственные результаты по способам композиции различных методов выделения сообществ.
 +
 +
[[Media:Pres_for_IPPI_report.pdf|Презентация]], [http://www.machinelearning.ru/wiki/images/6/60/2015_417_SlavnovKA.pdf Текст работы «'''Анализ социальных графов'''» ]
 +
 +
=== 18 ноября 2015 г. ===
 +
 +
'''Сергей Довгаль "Кластеризация с адаптивными весами"'''
 +
 +
На докладе мы расскажем об алгоритме AWC (Adaptive Weights Clustering). Мы посмотрим, какие геометрические подзадачи возникают при задаче кластеризации и опишем основные свойства этого алгоритма. Алгоритм исследуется для метрической кластеризации, но его можно применять для произвольных графов, на которых задана матрица расстояний.
 +
 +
=== 2 декабря 2015 г. ===
 +
 +
'''Максим Панов "Введение в спектральные методы кластеризации"''' ([[Media:presentation_spectral_clustering.pdf|Презентация]])
 +
 +
В рамках доклада мы расскажем об алгоритме спектральной кластеризации (Spectral clustering). Данный алгоритм прост в реализации и часто превосходит другие традиционные алгоритмы кластеризации. Цель доклада состоит в том, чтобы дать аудитории интуитивное понимание математических идей, лежащих в основе алгоритма. Будут рассмотрены различные виды лапласианов графа и их основные свойства, а также представлены наиболее популярные варианты алгоритма спектральной кластеризации.
 +
 +
=== 9 декабря 2015 г. ===
 +
 +
'''Лада Токмакова "Стабильность кластеризации: обзор"'''
 +
 +
([[Media:Clustering_stability.pdf|Презентация]])
 +
 +
Современные методы определения количества кластеров выбирают такое оптимальное число разбиений, при котором кластеризация является наиболее стабильной. В ходе доклада будет определен термин стабильности кластеризации, также будет рассказано о некоторых теоретических достижениях для алгоритмов K-means: the idealized K-means algorithm (когда целевая функция сходится к глобальному минимуму) и the actual K-means algorithm (когда целевая функция сходится к локальному минимуму).
 +
 +
'''Антон Вотинов "Графы ближайших соседей: алгоритмы оценки размерности и плотности"'''
 +
 +
([[Media:prezi.pdf|Презентация]])
 +
 +
Графы ближайших соседей часто встречаются в различных приложениях. Несмотря на то, что в таких графах содержится только информация об относительно расположении точек, существует возможность заглянуть глубже. В ходе доклада будут рассмотрены два алгоритма: алгоритм оценки размерности исходного пространства, из которого граф был порождён; оценка распределения наблюдений, на основе которых был построен граф.
 +
 +
=== 18 февраля 2016 г. ===
 +
 +
'''Константин Славнов "Выделение пересекающихся сообществ. Метод BigClam, его связь с AGM-моделью и NMF"'''
 +
 +
В докладе пойдет речь про современный эффективный метод выделения пересекающихся сообществ на графах BigClam (Cluster Affiliation Model for Big Networks). Его связь с дискретной моделью AGM (Community-Affiliation Graph Model). Будет затронута тема неотрицательного матричного разложения (NMF) и показано как задача выделения пересекающихся сообществ может быть рассмотрена как вариант NMF-задачи.
 +
 +
=== 3 марта 2016 г. ===
 +
 +
'''Сергей Довгаль "Sum-Product Algorithm and Affinity Propagation"'''
 +
 +
В рамках доклада планируется рассказать про алгоритм кластеризации графов Affinity Propagation, а также про истоки этого алгоритма: Factor Graphs и алгоритм Sum-Product, или его модификации типа Max-Product. Оказывается, что многие известные идеи можно свести к этому алгоритму: например, быстрое преобразование Фурье. Кроме того, с помощью графов можно моделировать линейные коды, он позволяет решать рекурренты типа Калмана, а также обобщает известный Forward-Backward алгоритм Витерби для марковский цепей. Если останется время, я постараюсь рассказать про то, откуда вытекают формулы для обновления в Affinity Propagation, и почему они являются оптимизационными итерациями для свободной энергии Бете.
 +
 +
[http://electric-tric.github.io/en/2016/03/03/sum-product-algorithm-part1.html Материалы к докладу]
 +
 +
=== 10 марта 2016 г. ===
 +
 +
Сергей Довгаль - продолжение рассказа.
 +
 +
=== 31 марта 2016 г. ===
 +
 +
'''Юрий Янович "Асимптотический анализ непараметрических оценок на многообразиях"'''
 +
 +
Данные высокой размерности часто лежат на или вблизи (нелинейного) многообразия низкой размерности (manifold hypothesis). Это наблюдение позволило формализовать постановку задачи снижения размерности (dimension reduction) и нашло широкое развитие в области оценивания многообразий (manifold learning). Доклад посвящен непараметрическому статистическому оцениванию на многообразиях. В дополнение к традиционным в статистике состоятельности, асимптотическому распределению и вероятности больших уклонений, автором доказана равномерная сходимость оценок и равномерная сходимость решений выборочных оптимизационных задач к своим непрерывным интегральным аналогам.
 +
 +
=== 7 апреля 2016 г. ===
 +
 +
'''Айдар Ризванов "Introduction to Matrix Completion via Semi-supervised Clustering"'''
 +
 +
([[Media:Seminar_Cluster_Rizvanov.pdf|Презентация]])
 +
 +
В рамках доклада планируется рассказать об основах задачи восстановления матриц с использованием алгоритмов Semi-supervised clustering. Суть их работы заключается не только в обработке исходных параметров описываемых переменных, но и в работе с информацией о попарных принадлежностях переменных к одному кластеру. Цель доклада состоит в формировании у аудитории понимания проблемы и некоторых способах её эффективного решения. Также планируется проиллюстрировать работу алгоритмов на примерах платформ Netflix и Tumblr.
 +
 +
=== 21 апреля 2016 г. ===
 +
 +
'''Кирилл Кузнецов "Различные подходы к решению задачи Разреженного метода главных компонент"'''
 +
 +
([[Media:Kuznetsov_SparsePCA.pdf|Презентация]])
 +
 +
В данном докладе слушателям напомнят о методе главных компонент (PCA). Далее слушатели познакомятся с разреженным методом главных компонент (Sparse PCA) и узнают про его связь с обычным методом главных компонент. Будут представлены различные методы решения задачи Sparse PCA, их сравнение. В заключении будут озвучены новые подходы к решению задачи Sparse PCA.
 +
 +
=== 12 мая 2016 г. ===
 +
 +
'''Лада Токмакова "Provably Learning Mixtures of Gaussians and More"'''
 +
 +
([[Media:Tokmakova_mixtures.pdf|Презентация]])
 +
 +
Как можно оценить параметры вероятностной модели, порождающей данные? Это один из фундаментальных вопросов машинного обученения. Наиболее распространенной задачей является оценка параметров смеси гауссиан. В ходе доклада будет сформулирована задача изучения смеси гауссиан, будут приведены подходы изучения с помощью проекции данных на подпространства меньших размерностей, описаны спектральные методы, также будут рассказаны недавние результаты и техники, способные изучать произвольные смеси.
 +
 +
=== 19 мая 2016 г. ===
 +
 +
'''Антон Вотинов "Algorithms on ordinal data"'''
 +
 +
([[Media:prezi2.pdf|Презентация]])
-
11 ноября 2015 г.
+
Ординальные данные являются самым естественным типом данных, используемых человеком. «Объект А ближе к объекту B, чем объект C», «Объект А является выбросом в тройке (A,B,C)» и тд. Тем не менее, существует мало алгоритмов, работающих с таким типом данных. В рамках доклада будет рассказано о разных видах ординальных данных, алгоритмах и проблемах, связанных с этими алгоритмами.
-
Константин Славнов TBA
 
[[Категория:Учебные курсы]]
[[Категория:Учебные курсы]]
Строка 64: Строка 152:
[https://www.informatik.uni-hamburg.de/ML/contents/people/luxburg/publications/Luxburg07_tutorial.pdf] Ulrike von Luxburg "A Tutorial on Spectral Clustering"
[https://www.informatik.uni-hamburg.de/ML/contents/people/luxburg/publications/Luxburg07_tutorial.pdf] Ulrike von Luxburg "A Tutorial on Spectral Clustering"
-
[http://www.cs.berkeley.edu/~jordan/papers/yan-etal-long.pdf] Donghui Yan, Ling Huang, Michael I. Jordan "Fast Approximate Spectral Clustering
+
[http://www.cs.berkeley.edu/~jordan/papers/yan-etal-long.pdf] Donghui Yan, Ling Huang, Michael I. Jordan "Fast Approximate Spectral Clustering"
-
"
+
=== Метрическая кластеризация ===
=== Метрическая кластеризация ===
Строка 71: Строка 158:
1. Задача одномерной оценки плотности
1. Задача одномерной оценки плотности
-
[http://bookfi.org/book/510172] --- Tsybakov, Nonparametric Estimation
+
[https://www.dropbox.com/s/4nwzi91ubo1nrdy/Introduction%20to%20Nonparametric%20Estimation.pdf?dl=0] Alexandre B. Tsybakov "Introduction to Nonparametric Estimation"
-
[https://projecteuclid.org/euclid.aos/1176348901] --- Superkernels in density estimation
+
[https://projecteuclid.org/euclid.aos/1176348901] Luc Devroye "A note on the usefulness of superkernels in density estimation"
2. Задача одномерной кластеризации
2. Задача одномерной кластеризации
-
[http://www.researchgate.net/publication/251400257_One-dimensional_center-based_l_1_-clustering_method] --- One-dimensional center-based l 1 -clustering
+
[http://www.researchgate.net/publication/251400257_One-dimensional_center-based_l_1_-clustering_method] Kristian Sabo, Rudolf Scitovski, Ivan Vazler "One-dimensional center-based l_1-clustering method"
-
method
+
-
[cs229.stanford.edu/notes/cs229-notes8.pdf] --- EM-algorithm
+
[http://cs229.stanford.edu/notes/cs229-notes8.pdf] Andrew Ng "The EM algorithm"
3. Задача многомерной кластеризации и оценки плотности
3. Задача многомерной кластеризации и оценки плотности
-
[http://projecteuclid.org/euclid.aos/1278861457] --- Generalized Density Clustering
+
[http://projecteuclid.org/euclid.aos/1278861457] Alessandro Rinaldo and Larry Wasserman "Generalized Density Clustering
 +
 
 +
[http://arxiv.org/abs/1409.8437] Ingo Steinwart "Fully adaptive density-based clustering"
-
[http://bookfi.org/book/510172] --- Tsybakov, Nonparametric Estimation
+
[https://www.dropbox.com/s/4nwzi91ubo1nrdy/Introduction%20to%20Nonparametric%20Estimation.pdf?dl=0] Alexandre B. Tsybakov "Introduction to Nonparametric Estimation"
4. Стабильность кластеризации
4. Стабильность кластеризации
-
[http://arxiv.org/abs/1007.1075] --- Ulrike von Luxburg, Clustering Stability
+
[http://arxiv.org/abs/1007.1075] Ulrike von Luxburg "Clustering Stability: An Overview"

Текущая версия

Содержание

Описание семинара

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

Время заседаний

Регулярный семинар, проводится в ИППИ РАН по средам в 18-30, ауд. 615.

Научные руководители семинара

М.Е. Панов, С. Довгаль, В. Г. Спокойный

Организатор семинара

Совместный учебно-научный семинар магистерской программы Математические методы оптимизации и стохастики Факультета Компьютерных наук НИУ ВШЭ, Института проблем передачи информации РАН и Лаборатории ПреМоЛаб МФТИ. Куратор семинара М.Е. Панов

Заседания

13 октября 2015 г.

Игорь Силин "Минимаксное оценивание в Stochastic Block Models"

В докладе будет рассмотрена популярная вероятностная модель Stochastic Block Model, используемая для доказательств свойств алгоритмов community detection. Будет получена минимаксная оценка риска для квадратичной функции потерь. Для этого сначала будет предъявлен метод, достигающий необходимой скорости сходимости, а затем будет доказано, что его нельзя улучшить. Для доказательства нижней оценки используется классический инструмент - неравенство Фано.

28 октября 2015 г.

1. Игорь Силин — продолжение рассказа

2. Обсуждение тем курсовых работы для студентов программы ММОС.

11 ноября 2015 г.

Константин Славнов "Методы выделения сообществ в применении к анализу социальных сетей"

Обзорный доклад, который посвящен теме социальных графов и обзору способов выделения сообществ на основе функционала модулярности. Будут рассмотрены некоторые свойства модулярности, 7 алгоритмов выделения структуры сообществ (Betweenness, Fastgreedy, Multilevel, LabelPropogation, Walktrap, Infomap, Eigenvector), а также рассказаны собственные результаты по способам композиции различных методов выделения сообществ.

Презентация, Текст работы «Анализ социальных графов»

18 ноября 2015 г.

Сергей Довгаль "Кластеризация с адаптивными весами"

На докладе мы расскажем об алгоритме AWC (Adaptive Weights Clustering). Мы посмотрим, какие геометрические подзадачи возникают при задаче кластеризации и опишем основные свойства этого алгоритма. Алгоритм исследуется для метрической кластеризации, но его можно применять для произвольных графов, на которых задана матрица расстояний.

2 декабря 2015 г.

Максим Панов "Введение в спектральные методы кластеризации" (Презентация)

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

9 декабря 2015 г.

Лада Токмакова "Стабильность кластеризации: обзор"

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

Современные методы определения количества кластеров выбирают такое оптимальное число разбиений, при котором кластеризация является наиболее стабильной. В ходе доклада будет определен термин стабильности кластеризации, также будет рассказано о некоторых теоретических достижениях для алгоритмов K-means: the idealized K-means algorithm (когда целевая функция сходится к глобальному минимуму) и the actual K-means algorithm (когда целевая функция сходится к локальному минимуму).

Антон Вотинов "Графы ближайших соседей: алгоритмы оценки размерности и плотности"

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

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

18 февраля 2016 г.

Константин Славнов "Выделение пересекающихся сообществ. Метод BigClam, его связь с AGM-моделью и NMF"

В докладе пойдет речь про современный эффективный метод выделения пересекающихся сообществ на графах BigClam (Cluster Affiliation Model for Big Networks). Его связь с дискретной моделью AGM (Community-Affiliation Graph Model). Будет затронута тема неотрицательного матричного разложения (NMF) и показано как задача выделения пересекающихся сообществ может быть рассмотрена как вариант NMF-задачи.

3 марта 2016 г.

Сергей Довгаль "Sum-Product Algorithm and Affinity Propagation"

В рамках доклада планируется рассказать про алгоритм кластеризации графов Affinity Propagation, а также про истоки этого алгоритма: Factor Graphs и алгоритм Sum-Product, или его модификации типа Max-Product. Оказывается, что многие известные идеи можно свести к этому алгоритму: например, быстрое преобразование Фурье. Кроме того, с помощью графов можно моделировать линейные коды, он позволяет решать рекурренты типа Калмана, а также обобщает известный Forward-Backward алгоритм Витерби для марковский цепей. Если останется время, я постараюсь рассказать про то, откуда вытекают формулы для обновления в Affinity Propagation, и почему они являются оптимизационными итерациями для свободной энергии Бете.

Материалы к докладу

10 марта 2016 г.

Сергей Довгаль - продолжение рассказа.

31 марта 2016 г.

Юрий Янович "Асимптотический анализ непараметрических оценок на многообразиях"

Данные высокой размерности часто лежат на или вблизи (нелинейного) многообразия низкой размерности (manifold hypothesis). Это наблюдение позволило формализовать постановку задачи снижения размерности (dimension reduction) и нашло широкое развитие в области оценивания многообразий (manifold learning). Доклад посвящен непараметрическому статистическому оцениванию на многообразиях. В дополнение к традиционным в статистике состоятельности, асимптотическому распределению и вероятности больших уклонений, автором доказана равномерная сходимость оценок и равномерная сходимость решений выборочных оптимизационных задач к своим непрерывным интегральным аналогам.

7 апреля 2016 г.

Айдар Ризванов "Introduction to Matrix Completion via Semi-supervised Clustering"

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

В рамках доклада планируется рассказать об основах задачи восстановления матриц с использованием алгоритмов Semi-supervised clustering. Суть их работы заключается не только в обработке исходных параметров описываемых переменных, но и в работе с информацией о попарных принадлежностях переменных к одному кластеру. Цель доклада состоит в формировании у аудитории понимания проблемы и некоторых способах её эффективного решения. Также планируется проиллюстрировать работу алгоритмов на примерах платформ Netflix и Tumblr.

21 апреля 2016 г.

Кирилл Кузнецов "Различные подходы к решению задачи Разреженного метода главных компонент"

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

В данном докладе слушателям напомнят о методе главных компонент (PCA). Далее слушатели познакомятся с разреженным методом главных компонент (Sparse PCA) и узнают про его связь с обычным методом главных компонент. Будут представлены различные методы решения задачи Sparse PCA, их сравнение. В заключении будут озвучены новые подходы к решению задачи Sparse PCA.

12 мая 2016 г.

Лада Токмакова "Provably Learning Mixtures of Gaussians and More"

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

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

19 мая 2016 г.

Антон Вотинов "Algorithms on ordinal data"

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

Ординальные данные являются самым естественным типом данных, используемых человеком. «Объект А ближе к объекту B, чем объект C», «Объект А является выбросом в тройке (A,B,C)» и тд. Тем не менее, существует мало алгоритмов, работающих с таким типом данных. В рамках доклада будет рассказано о разных видах ординальных данных, алгоритмах и проблемах, связанных с этими алгоритмами.

Литература

Кластеризация на графах

1. Stochastic block models and graphon estimation

[1] Chao Gao, Yu Lu, Harrison H. Zhou "Rate-optimal Graphon Estimation"

[2] Olga Klopp, Alexandre B. Tsybakov, Nicolas Verzelen "Oracle inequalities for network models and sparse graphon estimation"

2. Кластеризация графов на основе модулярности

[3] Santo Fortunato "Community detection in graphs"

[4] Twan van Laarhoven, Elena Marchiori "Axioms for graph clustering quality functions"

[5] Yunpeng Zhao, Elizaveta Levina, Ji Zhu "Consistency of community detection in networks under degree-corrected stochastic block models"

3. Графы ближайших соседей и их кластеризация

[6] Ulrike von Luxburg, Morteza Alamgir "Density estimation from unweighted k-nearest neighbor graphs: a roadmap"

[7] Matthaus Kleindessner, Ulrike von "Luxburg Dimensionality estimation without distances"

4. Обнаружение пересекающихся сообществ в больших сетях: алгоритм BigCLAM и его обобщения

[8] Jaewon Yang, Jure Leskovec "Overlapping Community Detection at Scale: A Nonnegative Matrix Factorization Approach"

5. Spectral clustering

[9] Ulrike von Luxburg "A Tutorial on Spectral Clustering"

[10] Donghui Yan, Ling Huang, Michael I. Jordan "Fast Approximate Spectral Clustering"

Метрическая кластеризация

1. Задача одномерной оценки плотности

[11] Alexandre B. Tsybakov "Introduction to Nonparametric Estimation"

[12] Luc Devroye "A note on the usefulness of superkernels in density estimation"

2. Задача одномерной кластеризации

[13] Kristian Sabo, Rudolf Scitovski, Ivan Vazler "One-dimensional center-based l_1-clustering method"

[14] Andrew Ng "The EM algorithm"

3. Задача многомерной кластеризации и оценки плотности

[15] Alessandro Rinaldo and Larry Wasserman "Generalized Density Clustering

[16] Ingo Steinwart "Fully adaptive density-based clustering"

[17] Alexandre B. Tsybakov "Introduction to Nonparametric Estimation"

4. Стабильность кластеризации

[18] Ulrike von Luxburg "Clustering Stability: An Overview"

Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%A1%D1%82%D0%B0%D1%82%D0%B8%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BA%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7_%28%D1%80%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D1%8B%D0%B9_%D1%81%D0%B5%D0%BC%D0%B8%D0%BD%D0%B0%D1%80%29»
Личные инструменты