Обучение без учителя Владимир Вежневец, Антон Конушин Александр Вежневец Компьютерное зрение МГУ ВМК, Осень 2006

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

Обучение без учителя Пусть, имеется набор наблюдений: Пусть, имеется набор наблюдений: Требуется некоторым образом сделать суждения о наблюдаемых данных Требуется некоторым образом сделать суждения о наблюдаемых данных Трудно придумать более общую постановку, неправда ли? Трудно придумать более общую постановку, неправда ли?

Обучение без учителя Кластеризация Кластеризация Разбиение наблюдений на некоторые группы, с максимально близкими наблюдениями внутри групп и максимально далекими между Разбиение наблюдений на некоторые группы, с максимально близкими наблюдениями внутри групп и максимально далекими между Понижение размерности Понижение размерности Понижение размерности наблюдений с сохранением описательной силы Понижение размерности наблюдений с сохранением описательной силы Анализ плотности распределения Анализ плотности распределения Получить аппроксимацию плотности распределения вероятности наблюдений или поиск их особых точек Получить аппроксимацию плотности распределения вероятности наблюдений или поиск их особых точек

Обучение без учителя Кластеризация Кластеризация К-средних К-средних Смесь нормальных распределений Смесь нормальных распределений … Понижение размерности Понижение размерности Метод главных компонент Метод главных компонент SOM SOM … Анализ плотности распределения Анализ плотности распределения Аппроксимация плотности распределения через обучение с учителем Аппроксимация плотности распределения через обучение с учителем Сдвиг среднего для поиска экстремумов плотности распределения Сдвиг среднего для поиска экстремумов плотности распределения …

Отличие от классификации Множество ответов неизвестно Множество ответов неизвестно Нет четкой меры качества решений Нет четкой меры качества решений Задачи поставлены крайне нечетко Задачи поставлены крайне нечетко

Кластеризация Постановка задачи (1) Пусть, имеется набор наблюдений: Пусть, имеется набор наблюдений: Требуется разбить на некоторые непересекающиеся подмножества (группы, кластеры), таким образом, что объекты внутри одной группы соотносились сильнее чем объекты из разных групп Требуется разбить на некоторые непересекающиеся подмножества (группы, кластеры), таким образом, что объекты внутри одной группы соотносились сильнее чем объекты из разных групп

Кластеризация Постановка задачи (2) Пусть, так же, имеется некоторая мера, характеризующая «схожесть» между объектами Пусть, так же, имеется некоторая мера, характеризующая «схожесть» между объектами Тогда, требуется найти некоторое разбиение : Тогда, требуется найти некоторое разбиение : Такое, что минимизируется Такое, что минимизируется И максимизируется И максимизируется

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

Алгоритм К-средних Кто хочет рассказать как он работает? Кто хочет рассказать как он работает? 1. Случайным образом выбрать k средних m j j=1,…,k; 2. Для каждого x i i=1,…,p подсчитать расстояние до каждого из m j j=1,…,k, 3. Отнести (приписать) x i к кластеру j, расстояние до m j минимально; 4. Пересчитать средние m j j=1,…,k по всем кластерам; 5. Повторять шаги 2, 3 пока кластеры не перестанут изменяться;

Иллюстрация

Алгоритм К-средних Мера схожести Мера схожести Евклидово расстояние в пространстве Х Евклидово расстояние в пространстве Х Модель кластеров Модель кластеров Пространство поиска - центры масс Пространство поиска - центры масс

Алгоритм К-средних Однопараметрический Однопараметрический Требует знания только о количестве кластеров Требует знания только о количестве кластеров Рандомизирован Рандомизирован Зависит от начального приближения Зависит от начального приближения Не учитывает строения самих кластеров Не учитывает строения самих кластеров

EM алгоритм Общая идеология Пусть есть вектор неизвестных величин Пусть есть вектор неизвестных величин и параметрическая модель с так же неизвестным параметром(ами) и параметрическая модель с так же неизвестным параметром(ами) Пусть возможно рассчитать правдоподобие Пусть возможно рассчитать правдоподобие Наша задача подобрать такие и, чтобы правдоподобие было максимальным Наша задача подобрать такие и, чтобы правдоподобие было максимальным

EM алгоритм Общая идеология Возьмем некоторые начальные приближения Возьмем некоторые начальные приближения Итеративно t =1… делаем два шага: Итеративно t =1… делаем два шага: Expect: согласно текущему значению высчитываем наиболее вероятные значения Expect: согласно текущему значению высчитываем наиболее вероятные значения Maximize: согласно текущем значениям высчитываем новое значение максимизирующее функцию правдоподобия Maximize: согласно текущем значениям высчитываем новое значение максимизирующее функцию правдоподобия Остановимся когда правдоподобие стабилизируется Остановимся когда правдоподобие стабилизируется

Кластеризация смесью нормальных распределений Будем считать, что наблюдения сгенерированы смесью нормальных распределений, то есть: Будем считать, что наблюдения сгенерированы смесью нормальных распределений, то есть: Пусть k известно заранее, будем осуществлять кластеризацию ЕМ алгоритмом Пусть k известно заранее, будем осуществлять кластеризацию ЕМ алгоритмом - Индексы кластеров наблюдений

Кластеризация смесью нормальных распределений Возьмем некоторые (случайные) начальные приближения Возьмем некоторые (случайные) начальные приближения Итеративно для t =1… : Итеративно для t =1… : E: согласно текущему значению высчитываем наиболее вероятные значения индексов кластеров для наблюдений из E: согласно текущему значению высчитываем наиболее вероятные значения индексов кластеров для наблюдений из M: согласно текущем значениям индексов пересчитаем параметры распределений (методом максимального правдоподобия) M: согласно текущем значениям индексов пересчитаем параметры распределений (методом максимального правдоподобия)

Иллюстрация

Кластеризация смесью нормальных распределений Плюсы Плюсы Более полная модель кластеров (больше итоговой информации) Более полная модель кластеров (больше итоговой информации) Более качественная аппроксимация Более качественная аппроксимация Эффективная оценка качества кластеризации (правдоподобие) Эффективная оценка качества кластеризации (правдоподобие) Минусы Минусы Все равно некоторая ограниченная модель со строгой «геометрией» Все равно некоторая ограниченная модель со строгой «геометрией» Чувствительность к размерности и нормализации данных Чувствительность к размерности и нормализации данных

Иллюстрация

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

Метод главных компонент Пусть имеется набор наблюдений Пусть имеется набор наблюдений Будем строить новый базис в пространстве, таким образом что: Будем строить новый базис в пространстве, таким образом что: Центр координат совпадает с мат. ожиданием наблюдений (выборочным средним) Центр координат совпадает с мат. ожиданием наблюдений (выборочным средним) Первый вектор направлен таким образом, что дисперсия вдоль него была максимальной Первый вектор направлен таким образом, что дисперсия вдоль него была максимальной Каждый последующий вектор ортогонален предыдущим и направлен по направлению максимальной дисперсии Каждый последующий вектор ортогонален предыдущим и направлен по направлению максимальной дисперсии

Метод главных компонент Расчет базиса Сдвинем все данные таким образом, чтобы их выборочное среднее равнялось нулю Сдвинем все данные таким образом, чтобы их выборочное среднее равнялось нулю Рассчитаем ковариационную матрицу: Рассчитаем ковариационную матрицу: Ковариация двух сл. величин Выборочное среднее

Метод главных компонент Расчет базиса Векторами нового базиса будут являться собственные вектора ковариационной матрицы Векторами нового базиса будут являться собственные вектора ковариационной матрицы Собственные числа – значениями дисперсии наблюдений вдоль них Собственные числа – значениями дисперсии наблюдений вдоль них

Иллюстрация Убирая базисные вектора с малыми значениями мы можем сократить размерность без существенной потери информации Убирая базисные вектора с малыми значениями мы можем сократить размерность без существенной потери информации *Вопрос: Почему это так?

Случай нормального распределения Расстояние от центра распределения в новой системе координат равно: Расстояние от центра распределения в новой системе координат равно: Так называемое расстояние Махалонобиса Так называемое расстояние Махалонобиса Пропорционально правдоподобию наблюдения Пропорционально правдоподобию наблюдения

Метод главных компонент Связь с линейной аппроксимацией Если рассмотреть систему проекций данных на первые главных компонент, то мы получим систему наилучших линейных приближений данных (в смысле среднеквадратичного отклонения) Если рассмотреть систему проекций данных на первые главных компонент, то мы получим систему наилучших линейных приближений данных (в смысле среднеквадратичного отклонения)

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

Самоорганизующиеся карты SOM (Карты Кохенена) Основная идея Основная идея вписать в данные сетку низкой размерности, и анализировать ее, вместо самих данных вписать в данные сетку низкой размерности, и анализировать ее, вместо самих данных

SOM (Карты Кохенена) Модель сетки Матрица узлов Матрица узлов Соседство - 4 или 8 связность Соседство - 4 или 8 связность Каждому узлу соответствует точка в исходном пространстве Каждому узлу соответствует точка в исходном пространстве

SOM (Карты Кохенена) Алгоритм построения Проинициализируем случайными значениями Проинициализируем случайными значениями Далее, в случайном порядке будем предъявлять наблюдения и для каждого: Далее, в случайном порядке будем предъявлять наблюдения и для каждого: Вычисляем ближайший узел Вычисляем ближайший узел Выберем множество соседей узла, такое что расстояние на сетке между ними меньше r Выберем множество соседей узла, такое что расстояние на сетке между ними меньше r Для некоторого множества соседей узла, включая сам узел, изменяем их положения согласно: Для некоторого множества соседей узла, включая сам узел, изменяем их положения согласно: Повторяем процедуру уменьшая r и пока сеть не стабилизируется Повторяем процедуру уменьшая r и пока сеть не стабилизируется

SOM (Карты Кохенена) Иллюстрация: исходные данные

SOM (Карты Кохенена) Иллюстрация: сетка

SOM (Карты Кохенена) Иллюстрация: проекции на матрицу

SOM (Карты Кохенена) Практическое использование Данные представляют некоторую поверхность, требуется сократить размерность Данные представляют некоторую поверхность, требуется сократить размерность Хорошо подходят для последующей кластеризации Хорошо подходят для последующей кластеризации Могут работать «online» Могут работать «online» В случае слишком сложных данных не информативны В случае слишком сложных данных не информативны

Задание 2 Каждому будут выданы Каждому будут выданы Данные (3 набора) Данные (3 набора) Алгоритмы классификации, реализованные в MatLab Алгоритмы классификации, реализованные в MatLab Требуется Требуется Для каждого из наборов натренировать наилучший возможный классификатор (из выданных вам) Для каждого из наборов натренировать наилучший возможный классификатор (из выданных вам) Написать отчет (по форме лежащий на сайте) описывающий каким образом вы выбирали классификатор и настроили параметры Написать отчет (по форме лежащий на сайте) описывающий каким образом вы выбирали классификатор и настроили параметры Оценка складывается из: Оценка складывается из: Аккуратности и полноты отчета Аккуратности и полноты отчета Результатов работы Вами присланного классификатора на наших данных (часть выборки мы дали Вам, часть оставили себе) Результатов работы Вами присланного классификатора на наших данных (часть выборки мы дали Вам, часть оставили себе)

Содержание отчета Применявшиеся методы Применявшиеся методы Список Список Алгоритм, по которому оценивались алгоритмы и выбирались параметры Алгоритм, по которому оценивались алгоритмы и выбирались параметры Результаты в виде Результаты в виде Графиков Графиков Таблиц Таблиц Выводы (кратко!) Выводы (кратко!) Какой классификатор был выбран в итоге Какой классификатор был выбран в итоге Почему именно этот классификатор Почему именно этот классификатор

Оформление решения Классификаторы Классификаторы _ _ Например 23_SVM Например 23_SVM Отчет Отчет Файл в формате MS Word Файл в формате MS Word