WWW.BOOK.LIB-I.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Электронные ресурсы
 
s

«Кластеризация Непараметрические модели кластеризации Другие непараметрические модели Непараметрические байесовские методы: Китайский ресторан ...»

Кластеризация

Непараметрические модели кластеризации

Другие непараметрические модели

Непараметрические байесовские методы:

Китайский ресторан и индийский буфет

Сергей Николенко

Mail.Ru, 18 декабря 2013 г.

Сергей Николенко Непараметрические байесовские методы

Кластеризация О задаче кластеризации

Непараметрические модели кластеризации О байесовском выводе

Другие непараметрические модели Вероятностная модель кластеризации

Outline

Кластеризация О задаче кластеризации О байесовском выводе Вероятностная модель кластеризации Непараметрические модели кластеризации Общая идея Китайский ресторан и кластеризация Байесовский вывод в CRP Другие непараметрические модели Индийский буфет и скрытые факторы Иерархические процессы Дирихле Процесс Питмана–Йора Сергей Николенко Непараметрические байесовские методы Кластеризация О задаче кластеризации Непараметрические модели кластеризации О байесовском выводе Другие непараметрические модели Вероятностная модель кластеризации Суть лекции Кластеризация типичная задача статистического анализа: задача классификации объектов одной природы в несколько групп так, чтобы объекты в одной группе обладали одним и тем же свойством.

Под свойством обычно понимается близость друг к другу относительно выбранной метрики.

Сергей Николенко Непараметрические байесовские методы Кластеризация О задаче кластеризации Непараметрические модели кластеризации О байесовском выводе Другие непараметрические модели Вероятностная модель кластеризации Чуть более формально Есть набор тестовых примеров X = {x1,..., xn } и функция расстояния между примерами.

Требуется разбить X на непересекающиеся подмножества (кластеры) так, чтобы каждое подмножество состояло из похожих объектов, а объекты разных подмножеств существенно различались.

Сергей Николенко Непараметрические байесовские методы Кластеризация О задаче кластеризации Непараметрические модели кластеризации О байесовском выводе Другие непараметрические модели Вероятностная модель кластеризации Методы

Иерархическая кластеризация:

инициализируем каждую точку как отдельный кластер;

объединяем ближайшие точки, далее считаем их единым кластером;

повторяем; в результате получается дерево.

Методами теории графов:

находим минимальное остовное дерево в графе из

–  –  –

Алгоритм k-средних

Вы, наверное, знаете алгоритм k-средних:

инициализировать центры кластеров µ1,..., µK ;

пока принадлежность кластерам не перестанет изменяться:

–  –  –

О байесовском выводе вообще Дальше мы будем заниматься вероятностными моделями.

Чтобы ими заниматься, нужно сначала некоторое введение о том, что вообще имеется в виду под байесовским выводом и зачем всё это надо.

–  –  –

Основные определения Нам не понадобятся математические определения сигма-алгебры, вероятностной меры, борелевских множеств и т.п.

Достаточно понимать, что бывают дискретные случайные величины (неотрицательные вероятности исходов в сумме дают единицу) и непрерывные случайные величины (интеграл неотрицательной функции плотности равен единице).

–  –  –

О болезнях и вероятностях Классический пример из классической области применения статистики медицины.





Пусть некий тест на какую-нибудь болезнь имеет вероятность успеха 95% (т.е. 5% вероятность как позитивной, так и негативной ошибки).

Всего болезнь имеется у 1% респондентов (отложим на время то, что они разного возраста и профессий).

Пусть некий человек получил позитивный результат теста (тест говорит, что он болен). С какой вероятностью он действительно болен?

–  –  –

О болезнях и вероятностях Классический пример из классической области применения статистики медицины.

Пусть некий тест на какую-нибудь болезнь имеет вероятность успеха 95% (т.е. 5% вероятность как позитивной, так и негативной ошибки).

Всего болезнь имеется у 1% респондентов (отложим на время то, что они разного возраста и профессий).

Пусть некий человек получил позитивный результат теста (тест говорит, что он болен). С какой вероятностью он действительно болен?

Ответ: 16%.

–  –  –

Вывод Вот такие задачи составляют суть вероятностного вывода (probabilistic inference).

Поскольку они обычно основаны на теореме Байеса, вывод часто называют байесовским (Bayesian inference).

Но не только поэтому.

–  –  –

Здесь p() априорная вероятность (prior probability), p(D|) правдоподобие (likelihood), p(|D) апостериорная вероятность (posterior probability), p(D) = p(D | )p()d вероятность данных (evidence).

Вообще, функция правдоподобия имеет вид

–  –  –

Это само по себе ведёт к оверфиттингу, поэтому обычно применяют регуляризацию.

В байесовском подходе ищут апостериорное распределение (posterior) p(|D) p(D|)p() и, возможно, максимальную апостериорную гипотезу (maximum a posteriori):

–  –  –

Постановка задачи Простая задача вывода: дана нечестная монетка, она подброшена N раз, имеется последовательность результатов падения монетки. Надо определить её нечестность и предсказать, чем она выпадет в следующий раз.

Гипотеза максимального правдоподобия скажет, что вероятность решки равна числу выпавших решек, делённому на число экспериментов.

–  –  –

Постановка задачи Простая задача вывода: дана нечестная монетка, она подброшена N раз, имеется последовательность результатов падения монетки. Надо определить её нечестность и предсказать, чем она выпадет в следующий раз.

Гипотеза максимального правдоподобия скажет, что вероятность решки равна числу выпавших решек, делённому на число экспериментов.

То есть если вы взяли незнакомую монетку, подбросили её один раз и она выпала решкой, вы теперь ожидаете, что она всегда будет выпадать только решкой, правильно?

–  –  –

Сделаем предположение: будем считать, что монетка выпадает равномерно, т.е. у нас нет априорного знания ph.

Теперь нужно использовать теорему Байеса и вычислить скрытые параметры.

–  –  –

Сопряжённые априорные распределения Ещё надо научиться выбирать априорные распределения.

Разумная цель: давайте будем выбирать распределения так, чтобы они оставались такими же и a posteriori.

До начала вывода есть априорное распределение p().

После него есть какое-то новое апостериорное распределение p( | x).

Я хочу, чтобы p( | x) тоже имело тот же вид, что и p(), просто с другими параметрами.

–  –  –

Сопряжённые априорные распределения Не слишком формальное определение: семейство распределений p( | ) называется семейством сопряжённых априорных распределений для семейства правдоподобий p(x | ), если после умножения на правдоподобие апостериорное распределение p( | x, ) остаётся в том же семействе: p( | x, ) = p( | ).

называются гиперпараметрами (hyperparameters), это параметры распределения параметров.

Тривиальный пример: семейство всех распределений будет сопряжённым чему угодно, но это не очень интересно.

–  –  –

Сопряжённые априорные распределения Разумеется, вид хорошего априорного распределения зависит от вида распределения собственно данных, p(x | ).

Сопряжённые априорные распределения подсчитаны для многих распределений, мы приведём два примера.

–  –  –

Испытания Бернулли Каким будет сопряжённое априорное распределение для бросания нечестной монетки (испытаний Бернулли)?

Ответ: это будет бета-распределение; плотность распределения нечестности монетки

–  –  –

На этом этапе можно забыть про сложные формулы и выводы, получилось очень простое правило обучения (под обучением теперь понимается изменение гиперпараметров).

–  –  –

Мультиномиальное распределение Простое обобщение: рассмотрим мультиномиальное распределение с n испытаниями, k категориями и по xi экспериментов дали категорию i.

Параметры i показывают вероятность попасть в категорию i:

–  –  –

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

Вероятностные модели задаются порождающими процессами (generative processes): надо понять, как порождается каждая точка, а потом записать каждый шаг этого порождения в виде распределения вероятностей.

Если вы запишете порождающий процесс, обычно можно будет достаточно просто сделать вывод на этой модели (например, при помощи сэмплирования по Гиббсу).

–  –  –

Вероятностная модель кластеризации Порождающий процесс для кластеризации – для очередной точки yn :

выбрать кластер cn, из которого мы будем порождать yn ;

выбрать точку yn из этого кластера.

Нам нужно придумать распределение для точки в одном кластере и распределение на кластерах.

–  –  –

И кластеризация – это задача разделения смеси вероятностных распределений. Её решают так называемым EM-алгоритмом (Expectation Maximization).

Введём скрытые переменные вероятности gnk того, что точка yn принадлежит кластеру k.

–  –  –

EM-алгоритм

Идея EM-алгоритма:

на E-шаге подсчитаем ожидания скрытых переменных;

на M-шаге зафиксируем скрытые переменные и найдём параметры максимального правдоподобия;

повторим до сходимости.

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

–  –  –

Байесовский подход к кластеризации Однако максимизировать правдоподобие не всегда хорошо, потому что точка максимума – это ещё не всё правдоподобие, да и максимум мы можем искать только локальный.

В реальности это приводит к оверфиттингу (overtting):

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

Поэтому используют байесовские методы – назначают априорное распределение на параметры кластеров, а затем интегрируют по всем возможным значениям параметров кластеров, используя это априорное распределение.

–  –  –

Остаётся тонкий вопрос: а что такое p(c)? Это должно быть априорное распределение на всех возможных назначениях индексов кластеров к точкам (groupings).

Перечислить их мы не можем, в EM-алгоритме мы просто фиксировали число кластеров и выражали p(c) как коэффициенты смеси pk.

–  –  –

Model selection

Но при таком подходе остаётся самый интересный вопрос:

а откуда взять число кластеров?

Обычно заранее число кластеров неизвестно.

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

Оптимальная с точки зрения правдоподобия кластеризация – когда каждая точка сама себе кластер;

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

–  –  –

Model selection

Это называется задача выбора модели (model selection):

как выбрать модель правильной сложности, т.е. с оптимальным числом параметров.

Чем больше параметров, тем “лучше” кластеризация.

Есть ряд критериев, которые можно применять для выбора модели и которые учитывают как правдоподобие, так и сложность модели.

–  –  –

Model selection Байесовский информационный критерий (Bayesian information criterion, BIC), он же критерий Шварца (Schwarz criterion):

BIC(M) = ln p(D | MAP ) M ln N, где M – число параметров, N – число точек в данных.

Получается как грубое приближение апостериорного распределения, “усреднённого” по разным моделям.

Т.е. алгоритм такой: кластеризовать много раз для разного числа кластеров, посчитать BIC, сравнить; так действительно часто делают на практике.

Сегодня я рассказываю о том, как можно делать по-другому.

Сергей Николенко Непараметрические байесовские методы Кластеризация Общая идея Непараметрические модели кластеризации Китайский ресторан и кластеризация Другие непараметрические модели Байесовский вывод в CRP

Outline

Кластеризация О задаче кластеризации О байесовском выводе Вероятностная модель кластеризации Непараметрические модели кластеризации Общая идея Китайский ресторан и кластеризация Байесовский вывод в CRP Другие непараметрические модели Индийский буфет и скрытые факторы Иерархические процессы Дирихле Процесс Питмана–Йора

–  –  –

Идея непараметрических методов Как мы уже видели, в вероятностных моделях есть важная проблема: выбор сложности модели.

Как найти, например, число кластеров?

Можно пользоваться методами model selection, обучив несколько моделей.

А можно сделать по-другому – ввести априорное распределение сразу на все модели разной сложности; это и есть основная идея байесовских непараметрических методов.

–  –  –

Идея непараметрических методов Непараметрическая байесовская статистика (Bayesian nonparametric) появилась ещё в 1970-х: [Ferguson, 1973;

Antoniak, 1974] – изучали процессы Дирихле (Dirichlet processes), в основном из чисто математического интереса.

[Rasmussen, 2000]: “The Innite Gaussian Mixture Model” – первое применение процессов Дирихле к машинному обучению.

Затем в машинное обучение пришли процессы Дирихле (с представлением в виде процесса китайского ресторана или процесса разлома палки, stick breaking process), индийского буфета, процесс Питмана–Йора (Pitman–Yor) и т.п.

Много расширений и применений – поговорим позже.

–  –  –

Идея непараметрических методов Смысл: давайте попробуем ввести единое распределение на всех моделях разной сложности.

При этом мы введём его так, чтобы менее сложные модели имели более Затем можно будет применить обычный байесовский подход и понять, какая сложность модели наиболее правдоподобна из данных.

“Непараметрический” не значит “нет параметров”, это значит, что число параметров зависит от данных и может расти, когда данных становится больше.

Бывают невероятностные непараметрические методы, например метод ближайших соседей.

–  –  –

Процесс китайского ресторана Теперь возвращаемся к кластеризации.

В байесовском выводе для кластеризации участвовало распределение p(c); переменные, взятые по этому распределению, должны были показывать, как точки распределены по кластерам.

Именно этим и занимается процесс китайского ресторана (Chinese restaurant process).

–  –  –

Процесс китайского ресторана Оказывается, что для такого процесса верно свойство перестановочности (exchangeability): группировка посетителей по столикам не зависит от того, в каком порядке они приходили:

выделим из совместного распределения

–  –  –

Процесс китайского ресторана Оказывается, что для такого процесса верно свойство перестановочности (exchangeability): группировка посетителей по столикам не зависит от того, в каком порядке они приходили:

числитель тут (Nk 1)!, а знаменатели объединим обратно:

–  –  –

Вывод в модели китайского ресторана

В случае кластеризации идея получается такая:

берём точки, случайно назначаем точки по кластерам;

выбираем точку, фиксируем кластеры всех остальных точек, затем выбираем кластер для текущей точки по CRP;

повторяем.

Рано или поздно этот процесс должен будет сойтись, так что просто ждём, пока назначения по кластерам перестанут значительно меняться.

По сути пользуемся перестановочностью, т.к. для нас каждая точка – как будто последняя.

–  –  –

Вывод в модели китайского ресторана Сэмплирование по Гиббсу – очень мощный инструмент;

его легко расширить на новые модели.

Если вы придумали (или используете) вероятностную модель, заданную порождающим процессом, весьма вероятно, что алгоритм сэмплирования по Гиббсу можно сделать просто посмотрев на этот процесс, без какой-то сложной математики; но сходиться может медленно.

Альтернативный способ – вариационные приближения;

совсем другой подход, сложнее, но часто эффективнее.

Для обычного CRP для задачи кластеризации вариационное приближение, конечно, известно.

–  –  –

Апостериорное распределение Последнее замечание – давайте посмотрим на апостериорное распределение модели CRP, т.е.

что модель думает про следующую точку:

–  –  –

В нём участвует априорное распределение CRP, p(cN+1 | c).

Фактически это означает, что если добавлять новые данные в обученную модель CRP, то новые данные могут привести к тому, что породится новый кластер.

–  –  –

Outline Кластеризация О задаче кластеризации О байесовском выводе Вероятностная модель кластеризации Непараметрические модели кластеризации Общая идея Китайский ресторан и кластеризация Байесовский вывод в CRP Другие непараметрические модели Индийский буфет и скрытые факторы Иерархические процессы Дирихле Процесс Питмана–Йора

–  –  –

Скрытые факторы Другая классическая задача машинного обучения – выделение скрытых факторов (latent factors).

Факторный анализ (FA), анализ главных компонент (PCA), анализ независимых компонент (ICA)...

Здесь тоже возникает проблема model selection: сколько брать факторов?

–  –  –

Скрытые факторы

Рассмотрим самую простую модель факторного анализа:

пусть мы наблюдаем N M-мерных векторов Y = {y1,..., yN }; т.е. в матрице Y по строкам идут наблюдения, по столбцам – размерности наблюдений.

Предположим, что данные порождены зашумленной линейной комбинацией скрытых факторов:

–  –  –

где wmk – вес, а zmk – бинарная переменная, которая показывает, “включён” ли фактор k в размерности m.

Это называется “spike and slab” модель, потому что получается смесь из “spike” в нуле размера p(zmk = 0) и “slab” p(wmk ) (обычно гауссовского) по остальным переменным.

–  –  –

Для этого надо выбрать априорное распределение p(Z);

это легко, если известно K.

А если K (число факторов) неизвестно? Тогда как раз можно опять непараметрически.

–  –  –

Скрытые факторы Рассмотрим Z как бесконечную матрицу с M строками (по размерности наблюдений) и бесконечным числом столбцов (потенциальные факторы).

Нам нужно расставить там 0 и 1 так, чтобы ненулевых столбцов получалось конечное число, и априорно меньшее число столбцов было бы более вероятно.

Китайский ресторан не подойдёт, т.к. тогда получится, что в каждой строке только одна единица (один фактор выражен); нам же нужно, чтобы в одной точке были выражены несколько факторов.

–  –  –

Скрытые факторы

Процесс индийского буфета (Indian buet process):

n-й посетитель (размерность) подходит к шведскому столу, где стоит бесконечная последовательность разных блюд;

пробует каждое из блюд, которые уже пробовали другие посетители, с вероятностью, пропорциональной тому, сколько посетителей их пробовали;

после этого пробует ещё Poisson(/n) новых блюд, которые другие раньше не пробовали.

Для индийского буфета тоже можно разработать алгоритм вывода на сэмплировании по Гиббсу.

–  –  –

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

То есть получаются как бы “группы кластеров”, в которых некоторые кластеры общие, а некоторые свои.

–  –  –

LDA Пример: тематическое моделирование (topic modeling).

В наивных подходах к категоризации (кластеризации) текстов, один документ принадлежит одной теме.

Латентное размещение Дирихле (latent Dirichlet Allocation, LDA): разумно предполагаем, что один документ касается нескольких тем:

тема – это (мультиномиальное) распределение на словах (в модели bag-of-words);

документ – это (мультиномиальное) распределение на темах.

–  –  –

Иерархические процессы Дирихле Хорошо было бы использовать процессы Дирихле в каждой группе с общим априорным распределением:

из общего априорного распределения выбрать параметры кластеров для каждой группы;

дальше используем их как обычно в процессе Дирихле в каждой группе независимо.

Но есть проблема: априорное распределение непрерывное, и кластеры не получатся общими.

–  –  –

Иерархические процессы Дирихле Решение: пусть априорное распределение будет дискретным, и его мы породим из процесса Дирихле, а потом из него уже наберём кластеров для каждой группы:

–  –  –

Процесс Питмана–Йора В китайском ресторане вероятность сгенерировать новый столик убывает пропорционально числу посетителей, и в результате с ростом числа посетителей число столиков растёт логарифмически, как O( log n).

Но как известно, на самом деле в жизни часто встречается степенной закон.

Например, если моделировать встречаемость слов процессом Дирихле, получится не очень, потому что частота слов затухает по закону Ципфа, т.е. степенному, а не экспоненциальному.

–  –  –

Резюме Байесовский вывод с априорными распределениями – нужен для того, чтобы не получалось оверфиттинга; это концептуальная замена регуляризации.

Непараметрические байесовские модели – концептуальная замена model selection; вводим априорное распределение на всевозможных наборах параметров разного размера (бесконечно большом числе), так, чтобы наборы с меньшим числом параметров имели преимущество.

Варианты: китайский ресторан (один посетитель – одно блюдо), индийский буфет (один посетитель – набор блюд), иерархические процессы Дирихле (разные рестораны с общими столиками), процесс Питмана–Йора (больше разных столиков, степенной закон).

Сергей Николенко Непараметрические байесовские методы Кластеризация Индийский буфет и скрытые факторы Непараметрические модели кластеризации Иерархические процессы Дирихле Другие непараметрические модели Процесс Питмана–Йора Что почитать

Презентации:

Michael I. Jordan. Dirichlet Processes, Chinese Restaurant Processes, And All That.

http://videolectures.net/icml05_jordan_dpcrp/ Yee Whye Teh. Modern Bayesian Nonparametrics.

http://www.youtube.com/watch?v=F0_ih7THV94 Yee Whye Teh. Bayesian Nonparametrics.

http://videolectures.net/mlss2011_teh_nonparametrics/ Pierre Chainais. Bayesian nonparametric approaches: an

introduction.

Mark Johnson. Chinese Restaurant Processes.

Khalid El-Arini. Dirichlet Processes: a Gentle Tutorial.


Похожие работы:

«® POD HD Pro ® Расширенное руководство пользователя Подробное описание особенностей и функций процессора POD HD Pro Электронное ограниченное издание Содержание Обзор Начальные экраны Режим тюнера Задание темпа Подключения Программное обеспечение POD HD Edit Pro Настройка системы Доступ к настройкам системы Страница 1, На...»

«© 2003 г. В.Э. БОЙКОВ ГОСУДАРСТВЕННАЯ СЛУЖБА. ВЗГЛЯД ИЗНУТРИ И ИЗВНЕ БОЙКОВ Владимир Эрихович доктор философских наук, профессор, директор Социологического центра Российской академии государственной службы при Президенте РФ. Состояние кадрового потенциала государственной службы оценивается обычно на основе стат...»

«vomer YOUR FARMING EQUIPMENT ru EVOLUTION/НЕПРЕРЫВНЫЙ ПРОЦЕСС РАЗВИТИЯ И AFTER-SALES SERVICE/ СОВЕРШЕНСТВОВАНИЯ ПОСЛЕПРОДАЖНОЕ Отдел инжиниринга и дизайна ОБСЛУЖИВАНИЕ Vomer постоянно разрабатывает Компания Vomer предлагает новую продукцию с целью полное послепродажное максимального увеличения обслуживание, гарантирует продуктивности работ....»

«ЕВРОПЕЙСКИЙ ИНФОРМАЦИОННЫЙ ЛИСТ СТАНДАРТНОЙ ИНФОРМАЦИИ О ПОТРЕБИТЕЛЬСКОМ КРЕДИТЕ Имя и контактные данные кредитора и при необходимости посредника в получении кредита 1. Кредитор Swedbank AS Адрес ул. Лийвала...»

«I. Задания заключительного этапа олимпиады 2014-15 года Заключительный этап 11 класса (приведен один из вариантов заданий) 1. Системы счисления (2 балла) [Последние цифры] Условие Число, записанное в четверичной системе счисления как 3234, возвели в степень, записанну...»

«Действия работников организаций при угрозе и возникновении на территории региона (муниципального образования) чрезвычайных ситуаций природного, техногенного и биологосоциального характера.Учебные вопросы: 1. Мероприя...»

«Клубные встречи: песенные вечерницы в БУЛ В конце минувшего марта Большой зал БУЛ на Трифоновской, 61, возможно, в последний раз принимал гостей клуба "Пісенні вечорниці", ежемесячно собиравшегося в гостеприимных стенах нашей библиотеки на протяжении вот уже почти десяти...»

«Е.А.Лютикова Относительные предложения с союзным словом который: общая характеристика и свойства передвижения У нас есть где искать, но надо знать, что искать, иначе. [Иван Ефремов. Звездные корабли (1944)] 1. Введение Относительные предложения долгие годы представляли собой ту синтаксическую проблемати...»

«Ежеквартальный бюллетень INOGATE / май – июль 2014 Сентябрь 2014 Об этом выпуске Приветствуем вас на страницах информационного бюллетеня INOGATE за сентябрь 2014 года! Это ежеквартальное издание охватывает к...»

«Отец Автор: Андреев Константин Весну сорок четвертого года Кинелахта перемогала в тревоге. В марте разнесся слух, что финны в Салми готовят ярмарку. Деревня эта в ходе Зимней войны в числе прочих была присоединена к Карелии, точнее, завоевана Красной Армией, а теперь снова стала территорией Финляндии. Поговаривали, что на торги...»










 
2017 www.book.lib-i.ru - «Бесплатная электронная библиотека - электронные ресурсы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.