Часть III
Машинное обучение
249
ГЛАВА 13
Концепции машинного обучения
13.1 Стили обучения
В широком смысле, двумя основными областями машинного обучения являются контролируемое обучение и обучение без контроля. При обучении под контролем основное внимание уделяется точному прогнозированию, в то время как при обучении без контроля цель состоит в том, чтобы найти точные и компактные описания данных.
Особенно при обучении под контролем интересны методы, которые хорошо работают с ранее невидимыми данными. То есть метод "обобщает" невидимые данные. В этом смысле проводится различие между данными, которые используются для обучения модели, и данными, которые используются для тестирования производительности обученной модели, см. рис.13.1.
13.1.1 Контролируемое обучение
Рассмотрим базу данных изображений лиц, каждое из которых представлено вектором 1 x. Наряду с каждым изображением x есть выходной класс y ; {male \мужчина, female\ женщина}, который определяет, принадлежит ли изображение мужчине или женщине. Доступна база данных из 10000 таких пар "изображение-класс", D = {(xn , yn ) , n = 1, . . . , 10000}. Задача состоит в том, чтобы точно предсказать y(x;) пол нового изображения x;. Это пример приложения, которое было бы сложно запрограммировать традиционным способом, поскольку формально указать, чем мужские лица отличаются от женских, сложно. Альтернативный вариант состоит в том, чтобы привести примеры лиц и их гендерные обозначения и позволить машине автоматически ‘обучиться знать’ правило отличать мужские лица от женских.
Определение 88 (Обучение Под Наблюдением). При заданном наборе данных D = {(xn , yn ) , n = 1, . . . , N } задача состоит в том, чтобы "обучить находить" взаимосвязь между входными данными x и выходными данными y таким образом, чтобы при вводе новых входных данных x; прогнозируемый выходной сигнал y; был точным. Чтобы явно указать, что означает точность, определяют функцию потерь L(ypred \предварительно , ytrue \истинно ) или, наоборот, функцию полезности U = ;L.
При обучении под наблюдением нас интересует описание y, обусловленное знанием x. Поэтому с точки зрения вероятностного моделирования нас интересует в первую очередь условное распределение p(y|x, D). Термин "контролируемый" указывает на то, что существует "руководитель", определяющий выходные данные y для каждого входного параметра x в доступных данных D. Выходные данные также называются "меткой", особенно при обсуждении классификации.
Прогнозирование завтрашней цены акций y(T +1) на основе прошлых наблюдений y(1), . . . , y(T) является формой контролируемого обучения. У нас есть набор значений времени и цен D = {(t, y(t)) , t = 1, . . . , T }, где время t - это "входные данные", а цена y(t) - выходные данные.
1Для изображения лица размером m ; n с элементами Fmn мы можем сформировать вектор, сложив элементы матрицы. В MATLAB этого можно достичь, используя x=F(:).
251 Стили обучения
Поезд
Тест
Рисунок 13.1: При обучении и оценке модели концептуально используются два источника данных. Параметры модели задаются только на основе данных о поезде. Если тестовые данные получены из того же базового процесса, который сгенерировал данные поезда таким образом, объективная оценка эффективности обобщения может быть получена путем измерения эффективности тестовых данных обученной модели. Важно отметить, что результаты тестирования не должны использоваться для корректировки параметров модели, поскольку в этом случае у нас больше не будет независимого показателя эффективности модели.
Пример 57. Отец решает рассказать своему маленькому сыну, что такое спортивный автомобиль. Поскольку ему трудно объяснить это словами, он решает привести несколько примеров. Они стоят на автомобильном мосту и, когда мимо проезжает машина, внизу отец кричит: "это спортивная машина!" - когда мимо проезжает спортивная машина. Через десять минут отец спрашивает сына, понял ли он, что такое спортивная машина. Сын отвечает: ‘Конечно, это просто’. Старый красный фольксваген Жук проезжает мимо, и сын кричит: "Это спортивная машина!". Удрученный отец спрашивает: "Почему ты так говоришь ?". "Потому что все спортивные машины красные!" - отвечает сын.
Это пример сценария для обучения под руководством учителя. Здесь отец играет роль надсмотрщика, а его сын - это "студент" (или "обучающийся"). Это свидетельствует о проблемах, с которыми сталкивается машинное обучение, поскольку в любом случае не совсем ясно, что такое спортивный автомобиль – если бы мы это знали, нам не нужно было бы проходить через процесс обучения. Этот пример также подчеркивает проблему, заключающуюся в том, что существует разница между хорошей работой с обучающими данными и хорошей работой с новыми тестовыми данными. Основной интерес в обучении под руководством преподавателя заключается в выявлении базового правила, которое будет хорошо обобщаться, что приведет к точному прогнозированию новых входных данных.
Для входных данных x, если выходные данные являются одним из дискретного числа возможных "классов", это называется задачей классификации. В задачах классификации мы обычно используем c для выходных данных.
Для входных данных x, если выходные данные непрерывны, это называется задачей регрессии. Например, вас попросят спрогнозировать спрос на солнцезащитный крем в вашем супермаркете на основе исторической информации о спросе на солнцезащитный крем в вашем супермаркете на следующий месяц. В некоторых случаях можно выделить непрерывный объем производства, а затем рассмотреть соответствующая проблема классификации. Однако в других случаях это нецелесообразно или неестественно; например, если выходные данные y представляют собой многомерный вектор с непрерывным значением, или если порядок состояний переменной имеет смысл.
13.1.2 Обучение без присмотра
Определение 89 (Обучение без учителя). При наличии набора данных D = {xn , n = 1, ... , N } при обучении без учителя мы стремимся "обучиться применять\ выучить" правдоподобное компактное описание данных. Объектив используется для количественной оценки точности описания.
В неконтролируемом обучении нет специальной "прогнозирующей" переменной. С вероятностной точки зрения мы заинтересованы в моделировании распределения p(x). Например, вероятность получения данных в соответствии с i.i.d. \ независимым\ предположением была бы одним из объективных показателей точности описания.
252 ПРОЕКТ от 9 марта 2010 года "Стили обучения"
Пример 58. Сеть супермаркетов хочет выяснить, сколько существует различных базовых моделей покупательского поведения, основываясь на обширной базе данных о кассах в супермаркетах. Товары, принесенные клиентом во время посещения кассы, представлены (очень редким) вектором x размером 10 000 измерений, который содержит 1 в i-м элементе, если клиент купил товар i и 0 в противном случае. Основываясь на 10 миллионах таких векторов оформления покупок в магазинах по всей стране, D ={ xn , n = 1, . . . , 107}, сеть супермаркетов хочет выявить закономерности покупательского поведения.
В таблице каждый столбец представляет модели покупок клиента (показаны 7 записей о клиентах и только первые 6 из 10 000 товаров). 1 означает, что клиент купил этот товар. Мы хотим найти общие закономерности в данных, например, если кто-то покупает кофе, он, скорее всего, также купит молоко.
кофе
, чай
, молоко
, пиво
, подгузники
, аспирин.
Пример 59 (Кластеризация).
В таблице справа представлена коллекция неотмеченных двумерных точек с кольцами. Мы можем визуализировать эти данные, построив их в двух измерениях.
Просто взглянув на данные, мы можем увидеть, что здесь есть два очевидных кластера, один из которых сосредоточен в районе (0,5), а другой - в районе (35,45). Поэтому разумной моделью для описания этих данных может быть представлен в виде двух кластеров с центрами (0,0) и (35,35), каждый из которых имеет стандартное отклонение около 10.
13.1.3 Обнаружение аномалий
Ребенок обрабатывает массу сенсорных данных, которые поначалу сбивают с толку. Через некоторое время он начинает понимать его окружение в том смысле, что новые сенсорные данные из того же окружения являются знакомыми или ожидаемыми. Когда появляется незнакомое лицо, ребенок понимает, что оно ему незнакомо, и может расстроиться. Ребенок усвоил представление о знакомом и может отличить ожидаемое от неожиданного; это пример обучения без контроля. Модели, которые могут обнаруживать нерегулярные события, используются в мониторинге предприятий и требуют модели нормальности, которая в большинстве случаев будет основана на данных без маркировки.
13.1.4 Онлайн (последовательное) обучение
В описанных выше ситуациях мы предполагали, что данные D были предоставлены заранее. При онлайн-обучении данные поступают последовательно, и мы хотим постоянно обновлять нашу модель по мере поступления новых данных. Онлайн-обучение может проходить как под наблюдением, так и без него.
13.1.5 Взаимодействие с окружающей средой
Во многих реальных ситуациях агент способен определенным образом взаимодействовать со своей средой.
Обучение с помощью запросов (активное) В нашем случае агент имеет возможность запрашивать данные из окружающей среды. Для примера, предсказатель может распознать, что он менее уверенно может прогнозировать в определенных областях пространства x, и поэтому запрашивает больше обучающих данных в этой области. Активное обучение также можно рассматривать в неконтролируемом контексте, когда агент может запрашивать информацию в регионах, где p(x) выглядит неинформативным или "плоским".
ЧЕРНОВИК от 9 марта 2010 г. 253 Обучение под наблюдением
Обучение с подкреплением Которое можно также назвать ‘обучением выживанию’. Имеются в виду сценарии, подобные тем, с которыми приходится сталкиваться в реальной жизни, когда организму необходимо научиться наилучшим действиям, которые он может предпринять в своей среде обитания, чтобы выжить как можно дольше. В каждой ситуации, в которой оказывается агент, ему необходимо предпринять какое-либо действие. Некоторые действия могут в конечном итоге принести пользу (например, привести к получению пищи), в то время как другие могут быть катастрофическими (например, привести к тому, что его съедят). Основываясь на накопленном опыте, агент должен понять, какие действия следует предпринять в той или иной ситуации, чтобы достичь желаемой долгосрочной цели. По сути, действия, которые приводят к долгосрочному вознаграждению, нуждаются в усилении. Подкрепление обучение связано с теорией управления, марковскими процессами принятия решений и теорией игр. В то время как мы обсуждали MDP и вкратце упомянули о том, как можно изучить среду, основанную на отсроченных вознаграждениях, в разделе (7.8.3), мы не будем обсуждать эту тему далее в этой книге.
13.1.6 Обучение под непосредственным наблюдением
В машинном обучении распространенным сценарием является наличие небольшого количества помеченных и большого количества немаркированных данных. Например, может случиться так, что у нас есть доступ ко многим изображениям лиц, однако лишь небольшое количество из них может быть помечено как экземпляры известных лиц. При обучении под наблюдением, кто-то пытается использовать немаркированные данные, чтобы создать лучший классификатор, чем тот, который основан только на маркированных данных.
13.2 Контролируемое обучение
Контролируемое и неконтролируемое обучение - это развитые области с широким спектром практических инструментов и соответствующим теоретическим анализом. Наша цель здесь - дать краткое представление о проблемах и "философии", лежащих в основе этих подходов. Здесь мы уделяем основное внимание обучению под наблюдением и, в частности, классификации.
13.2.1 Полезность и потери
Чтобы более полно определить контролируемую проблему, нам нужно четко представлять, какие "затраты" связаны с принятием правильного или неверного решения \ прогноза. В задаче двух классов dom(c) = {1, 2} мы предполагаем, что все, что мы знаем об окружающей среде, содержится в модели p(x, c). Учитывая новые входные данные x;, оптимальный прогноз также зависит от того, насколько дорого обойдется ошибка. Это можно количественно оценить с помощью функции потерь (или, наоборот, полезности). При формировании решающей функции c(x; ), которая будет выдавать метку класса для новых входных данных x; , мы не знаем истинный класс, только наше предполагаемое распределение p(c|x; ). Ожидаемая полезность для функции принятия решения равна
а оптимальным решением является то, которое максимизирует ожидаемую полезность.
Потери равны нулю -единице
Показатель эффективности прогнозирования "подсчитать правильные прогнозы" основан на полезности "ноль-единица" (или, наоборот, потери равны нулю- единице):
Для случая двух классов мы имеем
Следовательно, чтобы получить наивысшую ожидаемую полезность, решающая функция c(x; ) должна соответствовать выбору наивысшей вероятности класса p(c|x; ):
В случае равенства очков любой класс выбирается случайным образом с равной вероятностью.
254 ЧЕРНОВИК от 9 марта 2010 г. Контролируемое обучение
Общие функции потерь
В общем случае для задачи с двумя классами мы имеем
и функция оптимального принятия решений c(x; ) выбирает класс с наибольшей ожидаемой полезностью.
Это можно легко обобщить на ситуации с несколькими классами, используя матрицу полезности с элементами
где элемент i, j матрицы содержит полезность предсказания класса j, когда истинным классом является i.И наоборот, можно представить матрицу потерь с записями Lij = -Uij . Ожидаемый убыток по отношению к p(c|x) тогда называется риском.
В некоторых приложениях матрица полезности сильно несимметрична. Рассмотрим медицинский сценарий, в котором нас просят предсказать, есть ли у пациента рак dom(c) = {cancer \рак, benign\ доброкачественный}. Если истинный класс - рак, но мы прогнозируем, что он доброкачественный, это может иметь ужасные последствия для пациента. С другой стороны, если класс - доброкачественный, но мы прогнозируем рак, это может быть менее катастрофичным для пациента. Такая асимметричная полезность может повлиять на прогнозы в пользу консервативных решений – в случае с раком мы были бы более склонен считать выборку скорее злокачественной, чем доброкачественной, даже если прогностическая вероятность двух классов одинакова.
13.2.2 В чем же подвох?
При определении оптимальной решающей функции c(x;), приведенной выше, мы предполагаем, что модель p(c|x) является "правильной". Таким образом, загвоздка в том, что на практике :
• Мы обычно не знаем правильную модель, лежащую в основе данных – все, что у нас есть, это набор примеров D = {(xn , yn ) , n = 1, . . . , N } и наши знания в предметной области.
• Мы хотим, чтобы наш метод хорошо работал не только на специально выбранном x; , но и на любых новых входных данных, которые мы хотим, чтобы это было обобщено на новые исходные данные. Это означает, что нам также нужна модель для p(x), чтобы измерить ожидаемую производительность нашей функции принятия решений. Следовательно, нам требуется знание совместного распределения p(c, x) = p(c|x)p(x).
Следовательно, нам необходимо сформировать распределение p(x, c|D), которое в идеале должно быть близко к истинному, но неизвестному совместному распределению данных. Сообщества исследователей в области машинного обучения формируются вокруг различных стратегий, направленных на устранение недостатка знаний об истинных p (c, x).
13.2.3 Используя эмпирическое распределение
Прямой путь к тому, чтобы не знать правильную модель ptrue (c, x), заключается в замене ее эмпирическим распределением
То есть мы предполагаем, что базовое распределение аппроксимируется путем размещения одинаковой массы в каждой из точек (xn , cn ) в наборе данных. Использование этого метода дает эмпирическую полезность
или, наоборот, эмпирический риск
ПРОЕКТ от 9 марта 2010 г. 255 Обучение под наблюдением
Поезд
Утверждать
Тест
Рисунок 13.2: Модели могут быть обучены с использованием данных о поездах на основе различные параметры регуляризации. Оптимальный параметр регуляризации определяется эмпирическими результатами проверки данных. Независимая оценка эффективности обобщения достигается с помощью отдельного набора тестов.
Предполагая, что потери минимальны при прогнозировании правильного класса, оптимальное решение c(x) для любого входного сигнала в наборе поездов тривиально определяется как c(xn ) = c n. Однако для любого нового x;, не содержащегося в D, значение c(x; ) не определено. Чтобы определить класс новых входных данных, можно использовать параметрическую функцию
c(x) = f (x|;) (13.2.10)
Например, для задачи двух классов dom(c) = {1, 2} линейная решающая функция задается в виде
Если входной вектор x находится на положительной стороне гиперплоскости, определяемой вектором ; и смещением ;0 , мы относим его к классу 1, в противном случае к классу 2. (Мы вернемся к геометрической интерпретации этого в главе(17)). В этом случае эмпирический риск становится функцией параметров ; = {;, ;0 },
Оптимальные параметры ; задаются путем минимизации эмпирического риска относительно ;,
Решение для новой точки данных x; затем задается формулой f (x; |;opt ).
При таком подходе к минимизации эмпирического риска, поскольку мы усложняем функцию принятия решения f (x|;), эмпирический риск снижается. Если мы сделаем f (x|;) слишком сложным, у нас не будет уверенности в том, что f (x|;) будет хорошо работать с новыми входными данными x; . Чтобы ограничить сложность f (x|;), мы можем минимизировать эмпирический риск, связанный с штрафами\ пенальти , наказанный
Для приведенной выше линейной функции принятия решений разумно наказывать за резко меняющиеся классификации в это означает, что если мы изменим входное значение x лишь на небольшую величину, мы ожидаем (в среднем) минимального изменения в метке класса. Квадрат разности в ;T х + ;0 для двух входных переменных x1 и x2 является (;T ;x)2, где ;x ; x2 ; x1 . Ограничивая длину ; , чтобы она была небольшой , мы бы ограничили способность классификатора изменять класс только при небольшом изменении входного пространства2 . Это приводит к штрафному риску формы
где ; - регуляризующая константа,. Впоследствии мы минимизируем этот эмпирический риск в отношении к ;, ;0 . Ниже мы обсудим, как найти подходящее значение для постоянной регуляризации ;.
Утверждение\ проверка
Для минимизации эмпирического риска, связанного со штрафами, нам необходимо установить параметр регуляризации ;. Этого можно достичь, оценив производительность обученного классификатора f (x|;) на основе данных проверки Dvalidate для нескольких различных значений ; и выбрав тот, который обладает наилучшей производительностью. Важно, чтобы данные проверки не совпадали с данными, на основе которых была обучена модель, поскольку мы знаем, что оптимальная настройка для ; в этом случае случай равен нулю, и снова у нас не будет уверенности в возможности обобщения.
2 Предположим, что расстояние между двумя точками данных распределено в соответствии с изотропной многомерной гауссовой функцией с нулевым средним значением и ковариация ;2I, среднее квадратичное изменение равно <(; T ;x)2 >= ;2 ; T ;, что объясняет выбор евклидовой квадратичной длины параметра ; в качестве штрафного члена.
256
ПРЕДВАРИТЕЛЬНЫЙ вариант от 9 марта 2010 г. Обучение под наблюдением
Алгоритм 12 Установка параметров регуляризации с использованием перекрестной проверки.
1: Выберите набор параметров регуляризации ;1 , ... , ;A
2: Выберите набор разделов для обучения и проверки
3: от a = 1 до A выполните
4:от a = 1 до I выполните
6:окончание для
8: конец для
Учитывая исходный набор данных D, мы разбиваем его на непересекающиеся части, Dtrain, Dvalidate , где размер набора данных для проверки обычно выбирается меньшим, чем набор данных для поездов. Для каждого параметра ;a затем определяется минимальный эмпирический параметр риска ;a. Эта процедура разделения повторяется, каждый раз создавая отдельную тренировочную цепочку и валидационную проверку устанавливается вместе с оптимальным эмпирическим параметром риска ;ai с учетом штрафных санкций и соответствующей (нерегулируемой) эффективностью валидации R(;ai |Dvalidatei). Эффективность параметра регуляризации ;a берется как среднее значение показателей валидации за i. Затем задается наилучший параметр регуляризации с минимальной средней ошибкой проверки, см. алгоритм(12) и рис.(13.2). Используя оптимальный параметр регуляризации ;, многие специалисты-практики переобучаются ; на основе всего набора данных D.
При перекрестной проверке набор данных многократно разбивается на обучающие и проверочные наборы, при этом результаты проверки получаются для каждого раздела. Более конкретно, при K-кратной перекрестной проверке данные D разбиваются на K непересекающиеся части одинакового размера D1 , . . . , DK. Затем выполните двойную проверку Dvalidate= Di и Dtrain = D\Dvalidate. Это дает в сумме K различных наборов данных для проверки обучения, по которым усредняется производительность, см. рис. 13.3. На практике популярна 10-кратная перекрестная проверка, а также однократная перекрестная проверка, при которой наборы данных для проверки состоят только из одного примера.
Преимущества эмпирического подхода к оценке рисков
Для полезности U (ctrue , cpred ) и штрафных санкций P (;) эмпирический подход к оценке рисков представлен на рисунке(13.4).
• В случае большого объема обучающих данных эмпирическое распределение будет стремиться к правильному распределению.
• Дискриминантная функция выбирается на основе минимального риска, который является той величиной, которая нас в конечном итоге интересует.
• Процедура концептуально проста.
Поезд
Проверить данные
Рисунок 13.3: При перекрестной проверке исходный набор данных разбивается на несколько наборов валидации для обучения. Показана трехкратная перекрестная валидация. Для ряда параметров регуляризации оптимальный параметр регуляризации определяется на основе результатов эмпирической валидации, усредненных по различным разделениям.
ЧЕРНОВИК от 9 марта 2010 года 257 Обучение под наблюдением
Рисунок 13.4: Эмпирический подход к оценке риска. Учитывая набор данных X, C, строится модель данных p(x, c), обычно с использованием эмпирического распределения. Для классификатора f (x|;) параметр ; обучается путем максимизации оцененной эмпирической полезности (или минимизации эмпирического риска) с помощью\ относительно ;. Штрафной параметр ; устанавливается путем проверки. Затем новый входной сигнал x; присваивается классу f (x; |;), учитывая этот оптимальный ;.
Рисунок 13.5: (а): Нерегламентированное соответствие (; = 0) для обучения, заданное с помощью ;. Хотя данные обучения хорошо согласованы, ошибка в примерах проверки, +, высока. (b): Стандартизованное соответствие (; = 0,5). Хотя погрешность при составлении поезда высока, погрешность при проверке (что очень важно) невелика. Истинная функция, которая сгенерировала эти зашумленные данные, обозначена пунктирной линией; функция, полученная на основе данных, обозначена сплошной линией.
Недостатки эмпирического подхода к оценке рисков
• Кажется чрезмерным предполагать, что данные соответствуют эмпирическому распределению, особенно для небольших компаний. большое количество обучающих данных. Чтобы хорошо обобщить, нам нужно сделать разумные предположения относительно p (x) – это распределение для всех x, которое может возникнуть.
• Если функция полезности (или потерь) изменяется, дискриминантную функцию необходимо переобучить.
• Для решения некоторых задач требуется оценка достоверности прогноза. Хотя могут существовать эвристические способы оценки достоверности прогноза, это не является неотъемлемой частью системы.
• При наличии нескольких штрафных параметров выполнение перекрестной проверки в дискретизированной таблице параметров становится невозможным.
• Кажется позорным отказываться от всех этих обученных моделей при перекрестной проверке - нельзя ли их каким–то образом объединить и использовать для получения лучшего прогнозирующего показателя?
Пример 60 (Поиск хорошего параметра регуляризации). На рисунке(13.5) мы подгоняем функцию asin(wx) к данным, обучая параметры a и w. Нерегламентированное решение, показанное на рисунке (13.5a), плохо соответствует данным и имеет высокую ошибку проверки. Для обеспечения более плавного решения используется термин регуляризации Ereg = w2. Была вычислена ошибка проверки, основанная на нескольких различных значениях параметра регуляризации ;, вывод о том, что ; = 0,5, дал низкую ошибку проверки. Полученное соответствие новым данным, рис.13.5b, является приемлемым.
13.2.4 Байесовский подход к принятию решений
Альтернативой использованию эмпирического распределения является сопоставление модели p(c, x|;) с данными поезда D. С учетом этой модели решающая функция c(x) автоматически определяется исходя из максимальной ожидаемой полезности (или
258 ЧЕРНОВИК от 9 марта 2010 г. Контролируемое обучение
Рисунок 13.6: Байесовский подход к принятию решений. К данным применяется модель p(x, c|;). После доработки эта модель используется для вычисления p(c|x, ;). Для нового x; , затем мы находим распределение предполагаемой ‘истины’, p(c|x; , ;). Затем прогноз ( решение) определяется тем c; , которое максимизирует ожидаемую полезность <U (c, c; )>p(c|x; ,;) .
минимального риска), применительно к этой модели, как в уравнении (13.2.5), в котором неизвестное p(ctrue |x) заменено на p(c|x, ;). Таким образом, этот подход отделяет обучение параметров ; в p(c, x|;) от оценки полезности (или потерь).
Преимущества байесовского подхода к принятию решений
• Это концептуально "чистый" подход, при котором человек пытается наилучшим образом смоделировать окружающую среду, независимо от последующего процесса принятия решения. В этом случае обучение окружающей среды отделено от конечного эффекта, который это окажет на ожидаемую полезность.
• Конечное решение c; для новых входных данных x; может быть очень сложной функцией от x; из-за операции максимизации.
Недостатки байесовского подхода к принятию решений
• Если модель окружающей среды p(c, x|;) плоха, прогноз c; может быть очень неточным, поскольку моделирование окружающей среды отделено от прогнозирования.
• Чтобы избежать полного отрыва изучения модели p(c, x|;) от ее влияния на принимаемые решения, необходимо на практике часто включать в себя условия регуляризации в модели среды p(c, x|;), которые устанавливаются путем проверки на основе эмпирической полезности.
Существует два основных подхода к подгонке p(c, x|;) к данным D. Мы могли бы параметризовать совместное распределение, используя
p(c, x|;) = p(c|x, ;c|x )p(x|;x ) дискриминационный подход (13.2.16)
или
p(c, x|;) = p(x|c, ;x|c )p(c|;c ) генеративный подход (13.2.17)
Ниже мы рассмотрим эти два подхода в контексте попыток создать систему, способную отличить мужское лицо от женского. У нас есть база данных изображений лиц, в которой каждое изображение представлено в виде вещественнозначного вектора xn , n = 1, . . . , N), а также метка cn ; {0, 1}, указывающая, является ли изображение мужским или женским.
Порождающий подход p(x, c|;) = p(x|c, ;x|c )p(c|;c )
Для простоты мы используем обучение с Максимальным Правдоподобием для параметров ;. Предполагая, что данные D равны i.i.d., мы получаем логарифмическую правдоподобность
Как мы видим, зависимость от ;x|c имеет место только в первом семестре, а ;c - только во втором. Это означает, что изучение оптимальных параметров эквивалентно выделению данных для мужского класса и
ПРОЕКТ от 9 марта 2010 г.
259 Обучение под наблюдением
Рисунок 13.7: Две общие стратегии вероятностной классификации. (а): Генеративная модель x, зависящая от класса. После обучения параметров производится классификация путем подтверждения x и вывода p (c|x). (b): Метод дискриминантной классификации p(c|x).
подгонка модели p(x|c = мужской, ;x|мужской ). Аналогичным образом мы выделяем данные о женщинах и подгоняем отдельную модель p (x|c = женский, ;x|женский ). Распределение по классам p(c|;c ) можно легко установить в соответствии с соотношением мужчин и женщин в наборе обучающих данных.
Чтобы классифицировать новое изображение x; как мужское или женское, мы можем использовать
Исходя из соотношения потерь ноль-один, если эта вероятность больше 0,5, мы классифицируем x; как мужчину, в противном случае - как женщину. В более общем плане мы можем использовать эту вероятность как часть процесса принятия решения, как в уравнении (13.2.5).
Преимущества Предварительная информация о структуре данных часто наиболее естественным образом задается с помощью обобщающей модели p(x|c). Например, для лиц мужского пола мы ожидали бы увидеть более густые брови, более квадратную челюсть и т.д.
Недостатки Генеративный подход не нацелен непосредственно на классификационную модель p(c|x), поскольку целью генеративного обучения является, скорее, моделирование p(x|c). Если данные x сложны, поиск подходящей генеративной модели данных p(x|c) является сложной задачей. С другой стороны, может оказаться, что построение модели p(c|x) проще, особенно если граница принятия решений между классами имеет простую форму, даже если распределение данных по каждому классу сложное, см. рис.13.8. Кроме того, поскольку каждая генеративная модель обучается отдельно для каждого класса, между моделями нет конкуренции за объяснение данных.
Дискриминационный подход p(c, x) = p(c|x, ;c|x )p(x|;x )
Предполагая, что данные i.i.d., логарифмическая правдоподобность равна
Параметры выделены в двух терминах, так что обучение с Максимальным Правдоподобием эквивалентно нахождению параметров ;c|x, которые наилучшим образом предскажут класс c для данного входного сигнала обучения x. Параметры ;x для моделирования данных указаны отдельно во втором предложении выше, и поэтому их настройку можно рассматривать как отдельную проблему обучения без контроля. Таким образом, этот подход изолирует моделирование процесса принятия решения границы, полученной при моделировании распределения входных данных, см. рис.13.8.
Классификация новой точки x; основана на параметре
Что касается порождающего случая, то этот подход по-прежнему учит совместному распределению p(c, x) = p(c|x)p(x), которое при необходимости может быть использовано как часть процесса принятия решения.
Преимущества Дискриминативный подход непосредственно направлен на создание точного классификатора на основе p(c|x), моделирующего границу принятия решения, в отличие от условного распределения данных по классам в обобщающем подходе. Хотя данные из каждого класса могут быть распределены сложным образом, можно сделать так, что границу принятия решения между ними относительно легко смоделировать.
260 ЧЕРНОВИК от 9 марта 2010 года для самостоятельного изучения
Рисунок 13.8: Каждая точка представляет собой многомерный вектор с соответствующей меткой класса, либо мужской, либо женской. Точка x; - это новая точка, для которой мы хотели бы предсказать, будет ли это мужчина или женщина. При генеративном подходе мужская модель p(x|male) генерирует данные, аналогичные точкам ‘m’. Аналогично, женская модель p(x|female) генерирует точки, аналогичные точкам "f", указанным выше. Затем мы используйте правило Байеса для вычисления вероятности p(male|x; ) с использованием двух подобранных моделей, как указано в тексте. При дискриминативном подходе мы непосредственно создаем модель p(male|x; ), которая меньше заботится о том, как распределены точки "m" или "f", но больше об описании границы, которая может разделять два класса, как указано линией.
Рисунок 13.9: Стратегия обучения под контролем пользователя. Если cn отсутствует, то и термин p(cn |hn) отсутствует. Большой объем обучающих данных помогает модели хорошо обучить более низкое измерение/сжатое представление h данных x. Затем классификационная модель p(c|h), используя это представление с меньшей размерностью может быть намного проще подогнана, чем подгонка модели непосредственно из сложных данных класса p(c|x).
Недостатки Дискриминационные подходы обычно разрабатываются как классификаторы "черного ящика", в которые встроено мало предварительных знаний о том, как могут выглядеть данные для данного класса. Знание предметной области часто легче выразить с помощью генеративной структуры.
Гибридные генеративно-дискриминационные подходы
Можно было бы использовать обобщающее описание p (x|c), основанное на предварительной информации, и использовать его для формирования совместного распределения p (x, c), из которого может быть сформирована дискриминантная модель p (c|x), используя правило Байеса.
В частности, мы можем использовать
и используйте отдельную модель для p(x|;x ). Впоследствии параметры ; =( ;x|c , ;c ) для этой гибридной модели могут быть найдены путем максимизации вероятности попадания в правильный класс. Такой подход, по-видимому, позволит использовать преимущества как дискриминативной, так и порождающей структур, поскольку мы можем с большей готовностью включать знания предметной области в порождающую модель p(x|c, ;x|c ), но при этом обучать ее дискриминативным образом. Этот подход редко применяется на практике, поскольку результирующая функциональная форма вероятности сложным образом зависит от параметров. В этом случае не происходит разделения (как это было ранее в случае
генеративного и дискриминативного подходов).
13.2.5 Изучение низкоразмерных представлений в процессе обучения под наблюдением
Один из способов использовать большое количество немаркированных обучающих данных для улучшения моделирования классификации — попытаться найти представление данных x с меньшей размерностью h. Исходя из этого, отображение из h в c может быть гораздо проще для изучения, чем прямое отображение из x в c. Для этого мы можем сформировать вероятность, используя, смотрите рис.13.9,
, а затем задайте любые параметры , например , используя максимальное правдоподобие
ПРОЕКТ от 9 марта 2010 г. 261 Возражение против эмпирических решений
13.2.6 Особенности и предварительная обработка
Часто бывает так, что при попытке создать прогнозирующую модель, преобразование необработанных входных данных x в форму, которая более точно отражает соответствующую информацию на этикетке, может значительно повысить производительность. Для например, в случае классификации мужчин и женщин может возникнуть проблема с построением классификатора непосредственно на основе элементов вектора x лица. Однако использование "признаков", содержащих геометрическую информацию, такую как расстояние между глазами, ширина рта и т.д., может упростить поиск классификатора. На практике данные часто предварительно обрабатываются для удаления шума, центрирования изображения и т.д.
13.3 Байесовские решения против эмпирических
Эмпирический риск и байесовский подходы находятся на крайних рубежах философского спектра. В эмпирический подход к оценке рисков предполагает, на первый взгляд, чрезмерно упрощенное получение данных. Однако параметры функции принятия решений устанавливаются в зависимости от задачи принятия решений. С другой стороны, байесовский подход пытается изучить p(c, x) без учета его конечного использования в рамках более масштабного процесса принятия решений. Какой "объективный" критерий мы можем использовать для определения p(c, x), особенно если нас интересует классификация только с низким тестовым риском? Следующий пример предназначен для обобщения двух общих байесовских и эмпирических подходов к оценке рисков, которые мы рассматривали.
Пример 61 (Две общие стратегии принятия решений). Рассмотрим ситуацию, в которой на основе информации о пациенте x нам необходимо принять решение d о том, проводить операцию или нет. Целесообразность операции u(d, c) зависит от того, есть ли у пациента рак или нет. Например,
У нас есть независимые достоверные оценки того, был ли у пациента рак, что приводит к набору исторических данных D = {(xn , cn ), n = 1, . . . , N }. Столкнувшись с новым пациентом, обладающим информацией x, мы должны принять решение, действовать или нет.
В байесовском подходе к принятию решений сначала можно построить модель p(c|x, D) (например, логистическую регрессию). Используя эту модель, принимается решение, которое максимизирует ожидаемую полезность
При таком подходе обучение модели p(c|x, D) отделено от конечного использования модели в процессе принятия решений. Преимущество этого подхода заключается в том, что с точки зрения ожидаемой полезности, это оптимально при условии, что модель p(c|x, D) является "правильной". К сожалению, это редко бывает так. Учитывая ограниченные ресурсы модели, возможно, имеет смысл сосредоточиться на обеспечении правильного прогнозирования рака, поскольку это оказывает более существенное влияние на полезность. Однако формально это невозможно в рамках данной модели.
Альтернативный подход, основанный на эмпирической полезности, предполагает, что задача может быть сформулирована так: преобразовать информацию о пациенте x в решение о проведении операции d. Для этого можно параметризовать это как d(x) = f (x|;), а затем узнать ; при максимизации эмпирической полезности
Например, если x - это вектор, представляющий информацию о пациенте, а ; - параметр, мы могли бы использовать линейную функцию принятия решения, такую как
Преимущество этого подхода заключается в том, что параметры решения напрямую связаны с полезностью принятия решения. Недостатком является то, что мы не можем легко включить знания предметной области в функцию принятия решений. Возможно, у нас есть хорошая модель p (c|x), и мы хотели бы ее использовать.
262 ЧЕРНОВИК от 9 марта 2010 г. - Проверка байесовской гипотезы для анализа результатов
Оба подхода широко используются на практике, и выбор предпочтительного во многом зависит от проблемы. Хотя формально байесовский подход кажется оптимальным, он подвержен неправильной спецификации модели. Прагматичный альтернативный байесовский подход заключается в подгонке параметризованного распределения p(c, x|;) к данным D, где ; снижает "сложность" подобранного распределения, устанавливая ; с использованием проверки риска. Это имеет потенциальное преимущество, поскольку позволяет использовать разумную предварительную информацию о p(c, x) при оценке конкурирующих моделей в свете их фактического прогнозируемого риска. Аналогичным образом, для эмпирического подхода к оценке риска можно изменить допущение о экстремальном эмпирическом распределении, используя более правдоподобную модель p(x, c) данных.
13.4 Представляющие данные
Цифровое кодирование данных может существенно повлиять на производительность, и поэтому понимание вариантов представления данных имеет большое значение.
13.4.1 Категориальный
Для категориальных (или номинальных) данных наблюдаемое значение относится к одному из нескольких классов и не имеет внутренних значений. упорядочение классов. Примером категориальной переменной может быть описание типа работы, которую выполняет человек, например, в сфере здравоохранения, образования, финансовых услуг, транспорта, надомный работник, безработный, инженер и т.д.
Один из способов преобразовать эти данные в числовые значения - использовать кодировку 1 из m. Вот пример: Существует 4 вида профессий: солдат, матрос, жестянщик, шпион. Солдат представлен как (1,0,0,0), моряк - как (0,1,0,0), лудильщик - как (0,0,1,0) и шпион - как (0,0,0,1). В этой кодировке расстояние между векторами, представляющими две разные профессии - это константа. Очевидно, что кодировка 1 из m приводит к зависимостям в атрибутах профессии, поскольку, если один из атрибутов профессии равен 1, остальные должны быть равны нулю.
13.4.2 Порядковый \Обыкновенный
Порядковая переменная состоит из категорий с упорядочением или ранжированием категорий, например, холодно, прохладно, тепло, горячо. В этом случае, чтобы сохранить порядок, мы могли бы использовать -1 для холодного, 0 для холодного, +1 для теплого и +2 для горячего. Этот выбор в некоторой степени произвольный, и следует иметь в виду, что результаты, как правило, будут зависеть от используемого числового кодирования.
13.4.3 Численный
Числовые данные принимают значения, которые являются вещественными числами, например, температуру, измеряемую термометром, или зарплату, которую кто-то зарабатывает.
13.5 Проверка Байесовской Гипотезы для Анализа Результатов
Как мы можем оценить, работают ли два классификатора по-разному? Для методов, основанных на байесовских классификаторах p(c, ;|D, M ), в принципе, всегда будет существовать прямой способ оценить пригодность модели M путем вычисления p(M |D). Здесь мы рассматриваем менее удачную ситуацию, когда единственной предполагаемой доступной информацией являются результаты тестирования двух классификаторов.
Чтобы обозначить основную проблему, давайте рассмотрим два классификатора A и B, которые предсказывают класс из 55 тестовых примеров. Классификатор A допускает 20 ошибок и 35 правильных классификаций, тогда как классификатор B допускает 23 ошибки и 32 правильные классификации. Является ли классификатор A лучше классификатора B? Наша неуверенность в том, что A лучше, чем B, объясняется небольшим количеством тестовых примеров. С другой стороны, если классификатор A допускает 200 ошибок и 350 правильных классификаций, в то время как классификатор B допускает 230 ошибок и 320 правильных классификации, интуитивно мы были бы более уверены в том, что классификатор A лучше, чем классификатор B.
Возможно, наиболее актуальным вопросом с точки зрения машинного обучения является вероятность того, что классификатор A превосходит классификатор B, учитывая доступную информацию о тестировании. Хотя этот вопрос может
ЧЕРНОВИК от 9 марта 2010 года
263 Проверка байесовской гипотезы для анализа результатов
будет рассмотрена с использованием байесовской процедуры, раздел (13.5.5), сначала мы сосредоточимся на более простом вопросе, а именно, являются ли классификаторы A и B одинаковыми[16].
13.5.1 Анализ результатов
Обработка, приведенная в этом разделе, относится к результатам и количественно определяет, могут ли данные быть получены из одного и того же мультиномиального распределения. В основном мы будем применять этот метод для оценки того, являются ли два классификатора по существу одинаковыми, хотя следует иметь в виду, что этот метод применим в более общем плане к оценке того, могут ли результаты быть получены в результате одних и тех же или разных базовых процессов.
Рассмотрим ситуацию, когда два классификатора A и B были протестированы на некоторых данных, так что для каждого примера в тестовом наборе у нас есть пара результатов
где N - количество точек тестовых данных, а oa ; {1, . . . , Q} (и аналогично для ob ). То есть существует Q возможных типов исходов, которые могут иметь место.
Например, для бинарной классификации мы обычно используем четыре варианта
dom(o) = {Истинно положительный, ложноположительный, истинно отрицательный, ложноотрицательный} (13.5.2)
Если классификатор предсказывает класс c ; {истина, ложь}, а истинным является класс t ; {истина, ложь}, то они определяются как
Истинно положительные
ложноположительные
Истинно отрицательные
Ложноотрицательный
c = истинный
c = ложный
Мы называем oa = {oa (n), n = 1, . . . , N } результатами для классификатора A и аналогично для ob = {ob (n), n = 1, . . . , N } для классификатора B. Чтобы быть конкретными, у нас есть две гипотезы, которые мы хотим проверить:
1. Hdiff : oa и ob относятся к разным категориальным распределениям.
2. Hsame: oa и ob относятся к одному и тому же категориальному распределению.
В обоих случаях мы будем использовать категориальные модели p(oc = q|;, H) = yqc с неизвестными параметрами ; (гипотеза 2 будет соответствовать использованию одних и тех же параметров ; a = ; b для обоих классификаторов, а гипотеза 1 — использованию различных параметров, о чем мы поговорим ниже). В байесовской модели мы хотим определить, насколько вероятно, что за генерацию данных отвечает модель/гипотеза. Для любой гипотезы H вычисляем
где p(H) - это наше предварительное убеждение в том, что H является правильной гипотезой. Обратите внимание, что нормализующая константа p(oa , ob ) не зависит от гипотезы.
Во всех гипотезах мы будем исходить из предположения о независимости испытаний
Чтобы добиться дальнейшего прогресса, нам нужно сформулировать, что означают конкретные гипотезы.
264
ЧЕРНОВИК от 9 марта 2010 г. Проверка байесовской гипотезы для анализа результатов
Рисунок 13.10: (a): Hdiff : Соответствует результатам для двух независимо сгенерированных классификаторов. (b): Hsame: оба результата получены из одного и того же распределения. (c): Hdep: результаты являются зависимыми (‘коррелированными’).
13.5.2 Hdiff: правдоподобность модели
Теперь мы используем вышеуказанные предположения для вычисления вероятности Гипотезы:
Итоговая модель для классификатора A задается с использованием параметров ;, дающих значение p(oa |;, Hdiff), и аналогично мы используем ; для классификатора B. Ограниченный объем данных означает, что мы не уверены в значениях этих параметров, и поэтому общий член в числителе выше равен
где мы предположили, что
Обратите внимание, что можно было бы ожидать наличия определенного ограничения, заключающегося в том, что две модели A и B отличаются друг от друга. Однако, поскольку предполагается, что модели независимы и каждая из них имеет параметры, выбранные из фактически бесконечного набора (; и ; непрерывны), вероятность того, что выбранные параметры ; и ; двух моделей одинаковы, равна нулю.
Поскольку мы имеем дело с категориальными распределениями, удобно использовать априор Дирихле, который сопряжен с категориальным распределением:
Гиперпараметр априора u определяет, насколько сильно масса распределения смещена к углам симплекса, см. рис. 8.5. Значение uq = 1 для всех q соответствует равномерному априору. Вероятность oa определяется формулой
, где #a - это вектор с компонентами #aq, представляющими собой количество раз, когда переменная a находится в состоянии q в данных.
Следовательно
где Z(u) задается уравнением (13.5.10).
13.5.3 Hsame : правдоподобность модели
В Hsame гипотеза заключается в том, что результаты для двух классификаторов генерируются на основе одного и того же категориального распределения. Следовательно
ДРАФТ от 9 марта 2010 265 Проверка байесовской гипотезы для анализа результатов
Коэффициент Байеса
Если мы предположим, что у нас нет предварительного предпочтения ни для одной из гипотез (p(Hdiff ) = p(Hsame )), то
Это свидетельствует о том, что данные были получены с помощью двух различных категориальных распределений.
Пример 62. Два человека классифицируют выражение каждого изображения на счастливое, грустное или нормальное, используя состояния 1, 2, 3 соответственно. Каждый столбец приведенных ниже данных представляет собой изображение, классифицированное двумя людьми (person 1 - это верхний ряд, а человек 2 - второй ряд). Согласны ли эти два человека по существу?
Чтобы помочь ответить на этот вопрос, мы проводим тест Hdiff в сравнении с тестом Hsame. Исходя из этих данных, вектор подсчета для человека 1 равен [13, 3, 4], а для человека 2, [4, 9, 7]. Основываясь на плоском априоре для категориального распределения и не предполагая предварительного предпочтения ни одной из гипотез, мы получаем коэффициент Байеса
где функция Z задана в уравнении (13.5.10). Это убедительное доказательство того, что два человека классифицируют изображения по-разному.
Ниже мы обсудим некоторые другие примеры для теста Hdiff и теста Hsame. Как указано выше, единственные величины, которые нам нужны для этого теста, - это количество векторов в данных. Давайте предположим, что существует три вида результатов, Q = 3. Например, dom(o) = {хороший, плохой, уродливый} - это наш набор результатов, и мы хотим проверить, дают ли два классификатора одинаковые распределения результатов или разные.
Пример 63 (Hdiff в сравнении с Hsame ).
• У нас есть два подсчета результатов: #a = [39, 26, 35] и #b = [63, 12, 25]. Тогда коэффициент Байеса (13.5.15) равен 20,7 – убедительное доказательство в пользу того, что эти два классификатора различаются.
• В качестве альтернативы рассмотрим два исхода: #a = [52, 20, 28] и #b = [44, 14, 42]. Тогда коэффициент Байеса (13.5.15) равен 0,38 – слабое доказательство того, что эти два классификатора различаются.
• В качестве последнего примера рассмотрим числа #a = [459, 191, 350] и #b = [465, 206, 329]. Это дает байесовскую’ коэффициент уравнения (13.5.15) равен 0,008 – убедительное доказательство того, что два классификатора статистически совпадают.
Во всех случаях результаты согласуются с моделью, которая фактически использовалась для получения данных подсчета – два результата для A и B действительно были получены из разных категориальных распределений. Чем больше у нас данных для тестирования, тем больше мы уверены в наших утверждениях.
13.5.4 Анализ зависимых результатов
Здесь мы рассмотрим (возможно, более распространенный) случай, когда результаты зависят друг от друга. Например, часто тот случай, когда если классификатор A работает хорошо, то и классификатор B также будет работать хорошо. Таким образом, мы хотим оценить
266 ЧЕРНОВИК от 9 марта 2010 г. Проверка байесовской гипотезы для анализа результатов:
гипотезы:
Hdep: результаты, которые дают два классификатора, зависят друг от друга (13.5.17)
Для этого мы предполагаем категориальное распределение по объединенным состояниям:
Здесь P - матрица вероятностей Q ; Q:
таким образом, [P ]ij - это вероятность того, что A приведет к исходу i, а B - к исходу j. Тогда
где, для удобства, мы записываем o = (oa , ob ). Предполагая, что Дирихле предшествует P с гиперпараметрами U, мы имеем
где vec(D) - это вектор, сформированный путем объединения строк матрицы D. Здесь # - это матрица подсчета, где [#]ij равно количеству случаев, когда общий результат (oa = i, ob = j) происходил в N точках данных. Как и прежде, мы можем использовать это при расчете коэффициента Байеса. Для однородной априорной модели [U ]ij = 1, ;i, j.
Тестирование на наличие зависимостей в результатах: Hdep и Hdiff
Чтобы проверить, зависят ли результаты классификаторов Hdep от гипотезы о том, что они
независимы, мы можем использовать Hdiff, предполагая, что p(Hdiff) = p(Hdep ),
Пример 64 (Hdep в сравнении с Hdiff ).
• Рассмотрим матрицу подсчета результатов #
так что #a = [511, 32, 457] и #b = [198, 344, 458]. Затем
- убедительные доказательства того, что классификаторы работают независимо.
• Рассмотрим матрицу подсчета результатов #
так что #a = [359, 485, 156] и #b = [284, 273, 443]. Затем
- убедительные доказательства того, что классификаторы работают в зависимости друг от друга.
Эти результаты на самом деле согласуются с тем, как были получены данные в каждом конкретном случае.
ЧЕРНОВИК от 9 марта 2010 г.
267 Проверка байесовской гипотезы для анализа результатов
Проверка на наличие зависимостей в результатах: Hdep против Hsame
На практике разумно полагать, что в результатах, которые дают классификаторы, вполне вероятно наличие зависимостей. Например, два классификатора часто хорошо справляются с "простыми" тестовыми примерами и плохо - со ‘сложными’. Являются ли эти зависимости достаточно сильными, чтобы заставить нас поверить, что результаты получены в результате одного и того же процесса? В этом смысле мы хотим проверить
Пример 65 (Hdep против Hsame).
• Рассмотрим эксперимент, который дает матрицу подсчета результатов тестирования #
так что #a = [339, 290, 371] и #b = [319, 116, 565]. Тогда
– убедительные доказательства того, что классификаторы работают по-разному.
• Рассмотрим эксперимент, который дает матрицу подсчета результатов тестирования #
так что #a = [33, 24, 43] и #b = [33, 17, 50]. Тогда
– убедительные доказательства того, что классификаторы работают одинаково.
Эти результаты на самом деле соответствуют способу получения данных.
13.5.5 Является ли классификатор A лучше, чем B?
Мы возвращаемся к вопросу, с которого мы начали этот анализ результатов. Учитывая распространенный сценарий наблюдения количества ошибок для классификатора A в тестовом наборе и количества ошибок для B, можем ли мы сказать, какой классификатор лучше? Это соответствует частному случаю бинарных классов Q = 2 при dom(e) = {правильный, неправильный}. В соответствии с Hdiff для этого особого случая имеет смысл использовать Бета распределение (которая соответствует Дирихле, когда Q = 2). Тогда, поскольку ;a - вероятность того, что классификатор A сгенерирует правильную метку, мы имеем
Аналогично
Мы предполагаем независимые идентичные предварительные значения Бета — распределения
268 ПРОЕКТ от 9 марта 2010 года Код
Рисунок 13.11: Два классификатора A и B и их апостериорные распределения вероятности того, что они правильно классифицируют (используя стандартные Бета значения). (a): Для A с 35 правильными и 20 неправильными надписями, B (x|1 + 35, 1 + 20) (сплошная кривая); B с 32 правильными и 23 неправильными значениями B (y|1 + 32, 1 + 23) (пунктирная кривая). p(x >y) = 0,719 (b): Для A с 350 правильными и 200 неправильными надписями (сплошная кривая), B (x|1 + 350, 1 + 200); B с 320 правильными и 230 неправильными надписями (y|1 + 320, 1 + 230) (пунктирная кривая), p(x > y) = 0,968. По мере увеличения объема данных совпадение между распределениями уменьшается, и соответственно возрастает уверенность в том, что один классификатор лучше другого.
где плоское предварительное значение соответствует использованию значения гиперпараметра u1 = u2 = 1. Апостериорные распределения для ;a и ;b независимы:
Затем вопрос о том, лучше ли A, чем B, может быть решен путем вычисления
где
Пример 66. Классификатор A допускает 20 ошибок и 35 правильных классификаций, в то время как классификатор B допускает 230 ошибки и 320 правильные классификации. При использовании плоского априора это дает
С другой стороны, если классификатор A допускает 200 ошибок и 350 правильных классификаций, в то время как классификатор B допускает 230 ошибок и 320 правильных классификаций, мы имеем
Это демонстрирует интуитивный эффект, заключающийся в том, что даже несмотря на то, что доля правильных/неправильных классификаций для обоих сценариев значение не меняется, поскольку, по мере того как у нас появляется больше данных, наша уверенность в выборе лучшего классификатора возрастает.
13.6 Код
demoBayesErrorAnalysis.m: Демонстрация для Байесовского Анализа Ошибок
betaXbiggerY.m: p(x > y) для x~ B (x|a, b), y ~B (y|c, d)
ДРАФТ от 9 марта 2010 года 269 Упражнения
13.7 Записи \ Заметки, Отметим
Общее введение в машинное обучение приведено в [200]. Отличным справочником по байесовской теории принятия решений является [33]. Подходы, основанные на эмпирическом риске, обсуждаются в работе [282].
13.8 Упражнения
Упражнение 150. Учитывая распределения p(x|class1) = N (x |;1 , ;12 )и p(x|class2) = N (x |;2 , ;22) , с соответствующим предшествующим появлением классов p1 и p2 (p1 + p2 = 1), явно вычислите границу принятия решения как функцию µ1 , µ2 , ;12 , ;22 , p1 , p2 . Сколько существует решений для границы принятия решения и все ли они разумны?
Упражнение 151. Предположим, что вместо использования правила Байеса для выбора класса k, если p(Ck |x) > p(Cj |x) для всех j;k, мы используем случайное правило принятия решений, выбирая класс j с вероятностью Q(Cj |x). Вычислите ошибку для этого решающего правила и покажите, что ошибка минимизируется с помощью решающего правила Байеса.
Упражнение 152. Рассмотрим точки данных, сгенерированные из двух разных классов. Класс 1 имеет распределение p(x|c = 1) ; N (x\ m1 , ;2 ), а класс 2 имеет распределение p(x|c = 2) ; N( x \m2 , ;2) . Предыдущие вероятности каждого класса равны p(c = 1) = p(c = 2) = 1/2. Покажите, что апостериорная вероятность p(c = 1|x) имеет вид
и определите a и b в терминах m1 , m2 и ;2 .
Упражнение 153. WowCo.com это новая стартап-компания по прогнозированию. После многих лет неудач они в конце концов находят нейронную сеть с триллионом скрытых элементов, которая обеспечивает нулевую ошибку тестирования при решении каждой задачи обучения опубликовано в Интернете на прошлой неделе. Каждая учебная задача включала в себя тренировочный и тестовый набор. Гордясь своими достижениями, они активно продвигают свой продукт, заявляя, что он "идеально решает все известные задачи". Вы бы купили этот продукт? Обоснуйте свой ответ.
Упражнение 154. Три человека классифицируют изображения по одной из трех категорий. Каждый столбец в таблице ниже представляет классификацию каждого изображения, причем верхняя строка класса соответствует ответам человека 1, средняя - человека 2 и нижняя - человека 3.
Предполагая отсутствие предварительного предпочтения среди гипотез и одинаковое количество баллов, вычисляем
человек классифицировал различно
одинаково
Упражнение 155 (Лучше, чем случайное угадывание?). Рассмотрим классификатор, который дает R правильных и W неправильных классификаций. Действительно ли классификатор лучше, чем случайное угадывание? Пусть D - это тот факт, что существует R правильных и W неправильных ответов. Предположим также, что классификации одинаковы \ i.i.d- независимы одинаково распределенные .
1. Покажите, что в соответствии с гипотезой данные генерируются чисто случайным образом,
p(D|Hrandom ) = 0,5R+W (13.8.3)
2. Определите ; как вероятность того, что классификатор допустит ошибку. Затем
p(D|;) = ;R (1 ; ;) W (13.8.4)
270 ПРЕДВАРИТЕЛЬНЫЕ от 9 марта 2010 г. Упражнения
Затем рассмотрим
Покажем, что для бета-априора p(;) = B (;|a, b)
где B(a, b) - бета-функция.
3. Рассматривая случайную и неслучайную Гипотезы как априори равновероятные, покажите, что
4. Для плоского априора a = b = 1 вычислите вероятность того, что для 10 правильных и 12 неправильных классификаций данных получены из чисто случайного распределения (согласно уравнению (13.8.7)). Повторите это для 100 правильных и 120 неправильных классификаций.
5. Покажите, что стандартное отклонение числа ошибок случайного классификатора равно 0,5 ;(R + W), и соотнесите это с приведенным выше вычислением.
Упражнение 156. Для модели прогнозирования ~p(y|x) и истинных данных, генерирующих распределение p(x, y), мы определяем точность как
1. Определив
и учитывая, что
покажите, что для любого распределения q(x, y)
2. Вам предоставляется набор обучающих данных D = {xn , yn , n = 1, . . . , N }. Выбрав q(x, y) в качестве эмпирического распределения
показать, что
Это показывает, что точность прогнозирования ниже из-за точности обучения и "разрыва" между эмпирическим распределением и неизвестным истинным механизмом генерации данных. В таких теориях, как как и в случае с PAC Bayes, можно ограничить этот разрыв, что приведет к ограничению точности прогнозирования. Согласно этой наивной оценке, лучшее, что можно сделать для повышения точности прогнозирования, - это повысить точность обучения (поскольку первый член Кульбака-Лейблера не зависит от предиктора). По мере увеличения N первый семестр Кульбака-Лейблера становится меньше, и минимизация ошибки тренировки оправдана.
ПРОЕКТ от 9 марта 2010 г.
271 упражнение
Предполагая, что обучающие данные получены из распределения p(y|x), которое является детерминированным, покажите, что
и, следовательно, при условии, что данные обучения правильно предсказаны (q(yn |xn ) = p(yn |xn ), точность может быть связана с эмпирическим распределением входных данных и истинным распределением входных данных с помощью
272 ЧЕРНОВИК главы от 9 марта 2010 года
Глава 14
Классификация ближайших соседей
14.1 Поступай Так, Как Поступает Твой Сосед
Успешное предсказание обычно зависит от гладкости данных – если метка класса может произвольно изменяться при небольшом перемещении во входном пространстве, то проблема, по сути, случайна, и никакой алгоритм ее не решит./ хорошо не обобщит.- поэтому исследователи в области машинного обучения разрабатывают соответствующие показатели гладкости для решения стоящей перед ними задачи. Методы ближайшего соседа являются хорошей отправной точкой, поскольку они легко кодируют базовые интуитивные представления о плавности хода и просты в программировании, образуя полезный базовый метод.
В задаче классификации каждому входному вектору x соответствует метка класса, cn ; {1, . . . , C}. Учитывая набор данных из N таких обучающих примеров, D = {xn , cn } , n = 1, . . . , N , и новый x, мы стремимся чтобы вернулся правильный класс c(x). Простая, но часто эффективная стратегия для решения этой задачи контролируемого обучения может быть сформулирована следующим образом: для нового x найдите ближайший входной сигнал в обучающем наборе и используйте класс этого ближайшего входного сигнала, по алгоритму(13).
Для векторов x и x`, представляющих две разные точки данных, мы измеряем "близость", используя функцию различия \не подобности d(x, x` ). Общим отличием является квадрат евклидова расстояния
d(x, x` ) = (x ; x` )T (x ; x` ). (14.1.1)
который может быть более удобно записан (x ; x` )2 . Основываясь на квадрате евклидова расстояния, решение граница определяется линиями, которые являются перпендикулярными биссектрисами ближайших обучающих точек с разными обучающими метками, см. рис.14.1. Это называется тесселяцией Вороного.
Алгоритм ближайшего соседа прост и интуитивно понятен. Однако есть некоторые проблемы:
• Как мы должны измерять расстояние между точками? Хотя Евклидово квадратичное расстояние популярно, оно не всегда может быть подходящим. Фундаментальное ограничение Евклидова расстояния заключается в том, что оно не учитывает способ распределения данных. Например, если шкала длины x сильно различаются, наибольшая шкала длины будет определять квадрат расстояния, при этом потенциально полезная информация, относящаяся к конкретному классу, в других компонентах x теряется. Расстояние Махаланобиса
где ; - ковариационная матрица входных данных (из всех классов), может решить некоторые из этих проблем, поскольку она масштабирует все шкалы длин, чтобы они были практически одинаковыми.
• Для классификации необходимо сохранить весь набор данных. Это может быть устранено с помощью метода, называемого редактированием данных, при котором точки данных, которые практически не влияют на границу принятия решения, удаляются из обучающего набора данных.
273K- Ближайшие соседи
Рисунок 14.1: В классификации ближайших соседей новому вектору присваивается метка ближайшего вектора в обучающем \тренирующем\ наборе. Здесь представлены три класса, с точками обучения, обозначенными кружочками, и их классом. Точки указывают класс ближайшего обучающего вектора. Граница принятия решения является кусочно-линейной, причем каждый сегмент соответствует перпендикулярной биссектрисе между двумя точками данных, принадлежащими к разным классам, что приводит к тесселяции входного пространства по методу Вороного.
Алгоритм 13 Алгоритм ближайшего соседа для классификации нового вектора x с учетом набора обучающих данных D = {(xn , cn ), n = 1, . . . , N }:
1: Вычислите отличие тестовой точки x от каждой из сохраненных точек, dn = d (x, xn ), n = 1, . . . , N .
2: Найдите тренировочную точку xn*, которая находится ближе всего к x :
3: Присвоить классу метку c(x) = cn* .
4: В случае, если есть два или более "равноудаленных" соседа с разными метками класса, выбирается наиболее многочисленный класс. Если нет ни одного наиболее многочисленного класса, мы используем случай K-ближайших соседей, как описано в следующем разделе.
• Каждое вычисление расстояния может быть дорогостоящим, если точки данных имеют большую размерность. Анализ Принципиальных Компонентов, см. главу(15), является одним из способов решения этой проблемы и заменяет xn на проекцию с малой размерностью
p. Евклидово расстояние между двумя точками данных (xa ; xb )2 тогда приблизительно определяется как (pa ; pb)2 , см. раздел(15.2.4). Это не только ускоряет вычисления, но и может повысить точность классификации, поскольку в проекциях PCA сохраняются только крупномасштабные характеристики данных.
• Неясно, как работать с отсутствующими данными или учитывать предыдущие предположения и знания предметной области.
• Для больших баз данных вычисление ближайшего соседа новой точки x; может занять очень много времени, поскольку x; необходимо сравнивать с каждой из точек обучения. В зависимости от геометрии обучающих точек, поиск ближайшего соседа может быть ускорен путем обучения значений каждого из компонентов xi из x по очереди. Такое пространственное разделение, выровненное по оси, называется KD-деревом [202] и может уменьшить возможный набор возможных ближайших соседей в обучающем наборе для нового x; , особенно в малых измерениях.
14.2 K-Ближайшие соседи
Классификация, основанная только на одном ближайшем соседе, может привести к неточностям. Если ваш сосед просто ошибается (у него неправильная метка учебного класса) или не является особенно репрезентативным представителем своего класса, то такие ситуации, как правило, приводят к неправильной классификации. Включив в него больше, чем одного ближайшего соседа, мы надеемся создать более надежный классификатор с более плавной границей принятия решения (в меньшей степени зависит от мнений отдельных соседей). Для точек данных, которые несколько аномальны по сравнению с
274 ПРОЕКТ от 9 марта 2010 г. Вероятностная интерпретация ближайших соседей
Рисунок 14.2: В K-ближайших соседях мы центрируем гиперсферу вокруг точки, которую хотим классифицировать (здесь это центральная точка). Внутренний круг соответствует ближайшему соседу. Однако, используя 3 ближайших соседа, мы обнаруживаем, что существует два "синих" класса и один "красный", и поэтому мы бы классифицировали точку как "синий" класс. В случае совпадения можно увеличивать K до тех пор, пока связь не будет нарушена.
соседями из того же класса, их влияние будет в меньшинстве.
Если мы примем Евклидово расстояние в качестве меры различия, алгоритм K-ближайшего соседа будет рассматривать гиперсферу с центром в контрольной точке x. Мы увеличиваем радиус r до тех пор, пока гиперсфера не будет содержать ровно K точек в обучающих данных. Затем классовая метка c(x) присваивается самому многочисленному классу в пределах гиперсферы.
Выбираем K
Хотя есть некоторый смысл в том, чтобы сделать K > 1, нет особого смысла в том, чтобы сделать K = N (N — это количество обучающих баллов). При очень большом K все классификации станут одинаковыми – просто присвойте каждому новому классу x наиболее многочисленный класс в обучающих данных. Это говорит о том, что существует "оптимальное" промежуточное значение K, которое обеспечивает наилучшие результаты обобщения. Это можно определить с помощью перекрестной проверки, как описано в разделе (13.2.3).
Пример 67 (Пример Цифр, Написанных от Руки). Рассмотрим два класса цифр, написанных от руки, - нули и единицы. Каждая цифра содержит 28 ; 28 = 784 пикселя. Обучающие данные состоят из 300 нулей и 300 единиц, подмножества некоторые из них изображены на рис. 14.3а,б). Для проверки работоспособности метода ближайшего соседа (основанного на Евклидовом расстоянии) мы используем независимый тестовый набор, содержащий еще 600 цифр. Метод ближайшего соседа, примененный к этим данным, правильно определяет классовую принадлежность всех 600 тестовых точек. Причина высокой вероятности успеха заключается в том, что примеры нулей и единиц достаточно различны, чтобы их можно было легко отличить.
Более сложная задача - отличить единицы от семерок. Мы повторяем вышеупомянутый эксперимент, теперь используя 300 обучающих примеров из единиц и 300 обучающих примеров из семерок, рис.14.3б, в). И снова, для оценки эффективности были использованы 600 новых тестовых примеров (содержащих 300 единиц и 300 семерок). На этот раз при использовании метода ближайшего соседа найдено 18 ошибок, что составляет 3% ошибок для этой задачи двух классов. 18 контрольных точек, в которых метод ближайшего соседа допускает ошибки, показаны на рисунке(14.4). Если мы используем K = 3 ближайших соседа, ошибка классификации уменьшается до 14 – незначительное улучшение. Кроме того, ошибка классификации лучших методов машинного обучения классифицировать реальные цифры (по всем 10 классам) составляет менее 1% (yann.lecun.com/exdb/mnist) – что лучше, чем у ‘среднестатистического’ человека.
14.3 Вероятностная Интерпретация Ближайших Соседей
Рассмотрим ситуацию, когда у нас есть (для простоты) данные из двух классов – класса 0 и класса 1. Мы создаем следующую комбинированную модель для данных из класса 0:
где D - размерность точки данных x, а N0 - количество обучающих точек данных класса 0, а
;2 - дисперсия. Это оценка Парцена, которая моделирует распределение данных как равномерную взвешенную сумму распределений, сосредоточенных на точках обучения, рис.14.5.
ЧЕРНОВИК от 9 марта 2010 г. 275A Вероятностная интерпретация ближайших соседей
Рисунок 14.3: Некоторые обучающие примеры цифр ноль и (a), единица (b) и семь (c). Существует 300 обучающих примеров для каждого из этих трехзначных классов.
Рисунок 14.4: Классификация "1" по сравнению с "7", используемая нами метод NN. (Вверху) 18 из 600 тестовых примеров, которые были неправильно классифицированы; (внизу) ближайшие соседи в обучающем наборе, соответствующие каждой контрольной точке, указанной выше.
Аналогично, для данных из класса 1:
Чтобы классифицировать новую точку данных x; , мы используем правило Байеса
Значение Максимального Правдоподобия для p(c = 0) равно N0 /(N0 + N1), а p(c = 1) = N1 /(N0 + N1 ). Выражение, аналогичное уравнению (14.3.3), справедливо для p(c = 1|x;). Чтобы определить, какой класс является наиболее вероятным, мы можем использовать соотношение
Если это отношение больше единицы, мы классифицируем x; как 0, в противном случае как 1.
Уравнение (14.3.4) является сложной функцией от x;. Однако, если ;2 очень мало, то в числителе, представляющем собой сумму экспоненциальных членов, будет преобладать тот член, для которого точка данных xn0 в классе 0 является ближайшей к точке x;. Аналогично, в знаменателе будет преобладать та точка данных xn1 в классе 1, которая ближе всего к x; . Следовательно, в этом случае
Принимая предел ;2 ; 0, мы с уверенностью относим x; к классу 0, если x; имеет точку в данных класса 0, которая находится ближе, чем ближайшая точка в данных класса 1. Таким образом, метод ближайшего (единственного) соседа является восстановленным, как предельный случай вероятностной порождающей модели, см. рис. 14.5.
Мотивация использования K ближайших соседей состоит в том, чтобы получить результат, устойчивый к нерепрезентативным ближайшим соседям. Чтобы обеспечить аналогичную надежность в вероятностной интерпретации, мы можем использовать конечное значение ;2 > 0. Это сглаживает крайние вероятности классификации и означает, что большее число точек (не только ближайших) будут иметь эффективный вклад в уравнение (14.3.4). Расширение до более чем
276 ЧЕРНОВИК от 9 марта 2010 года Упражнения
Рисунок 14.5: Вероятностная интерпретация ближайших соседей. Для каждого класса мы используем смесь гауссиан для моделирования данных из этого класса p (x|c), помещая в каждую точку обучения изотропную гауссиану шириной ;2. Ширина каждой гауссовой точки обозначена кружком. В пределе ;2 ; 0 новой точке (черной) присваивается класс ее ближайшего соседа. Для конечного ;2 > 0 влияние не ближайших соседей имеет значение, что приводит к созданию мягкой версии ближайших соседей.
использование двух классов является простым, для каждого класса требуется условная порождающая модель класса. Чтобы выйти за рамки методов ближайшего соседа, мы можем отказаться от предположения об использовании оценки Парцена и использовать более богатую генеративную модель. Мы рассмотрим такие случаи более подробно в последующих главах, в частности в главе (20).
14.3.1 Когда ваш ближайший сосед находится далеко
Для нового входного сигнала x;, который находится далеко от всех точек обучения, ближайшие соседи и его мягкий вероятностный вариант уверенно классифицируют x; как принадлежащий классу ближайшей точки обучения. Это, возможно, противоречит тому, чего бы нам хотелось, а именно тому, что классификация должна основываться на предшествующих вероятностях класс основан на количестве обучающих данных для каждого класса. Способ избежать этой проблемы заключается в том, чтобы для каждого класса включить фиктивный компонент смеси в среднее значение всех данных с большой дисперсией, одинаковое для каждого класса. Для новых входных данных, близких к обучающим данным, эта дополнительная фиктивная точка данных не будет иметь заметного эффекта. Однако, по мере удаления от областей с высокой плотностью обучающих данных, этот дополнительный фиктивный компонент будет доминировать. Поскольку расстояние от x; до каждой точки фиктивного класса одинаково, в пределе поскольку x; находится далеко от обучающих данных, в результате информация о классе из позиции x; отсутствует. Пример приведен в разделе(20.3.3).
14.4 Код
nearNeigh.m: K Ближайших соседей
14.4.1 Служебные процедуры \ Полезные способы
majority.m: Найдите основную запись в каждом столбце матрицы.
14.4.2 Демонстрационный
demoLearneigh.m: K Демонстрация ближайшего соседа
14.5 Упражнения
Упражнение 157. Файл NNdata.mat содержит обучающие и тестовые данные для рукописных цифр 5 и 9. Используя перекрестную проверку, найдите оптимальное значение K в K-ближайших окрестностях и используйте его для вычисления точность классификации метода на основе тестовых данных.
Упражнение 158. Напишите процедуру SoftNearNeigh(xtrain,xtest,trainlabels,sigma) для реализации soft nearest neighbors, аналогичную nearNeigh.m. Здесь sigma - это дисперсия ;2 в уравнении (14.3.1). Как указано выше, файл NNdata.mat содержит обучающие и тестовые данные для написанных от руки цифр 5 и 9. Используя перекрестную проверку без учета одного, найдите оптимальное значение ;2 и используйте его для вычисления точности классификации метода на основе тестовых данных. Подсказка: при использовании этого метода у вас могут возникнуть проблемы с числами. Чтобы избежать этого, рассмотрим использование логарифма и то, как численно вычислить логарифм log( ea + eb ) для больших (отрицательных) значений a и b. Смотрите также проект logsumexp.m.
от 9 марта 2010 г. 277 Упражнения
Упражнение 159. В тексте мы предложили использовать расстояние Махаланобиса
как способ улучшить Евклидово расстояние, используя ; как ковариационную матрицу объединенных данных из обоих классов. Рассмотрим модификацию, основанную на использовании модели смеси
и
1. Объясните, как алгоритм soft Nearest Neighbors может справиться с проблемой, связанной с тем, что распределение данных из разных классов может сильно отличаться.
2. Для случая, когда ;0 = ;2 ;`0 и ;1 = ;2 ;`1 и ;2 мало, выведите простое выражение, которое приблизительно равно
Упражнение 160. Редактору YoMan! (мужского журнала) только что пришла в голову отличная идея. Основываясь на результатах недавнего национального опроса по тестированию IQ, она решила провести тест на "Коэффициент красоты" (BQ). Она собирает как можно больше изображений мужских лиц, стараясь, чтобы все изображения были примерно одинакового размера и при одинаковом освещении. Затем она присваивает каждому мужскому лицу оценку BQ от 0 (‘С серьезными эстетическими недостатками") до 100 ("С большой эстетической одаренностью"). Таким образом, для каждого изображения x существует соответствующее значение b в диапазоне от 0 до 100. В общей сложности она собрала N изображений и соответствующих оценок, {(xn , bn ) , n = 1, . . . , N }, где каждое изображение представлено D-мерным вещественнозначным вектором x. Однажды утром она заходит к вам в офис и сообщает хорошие новости: ваша задача - составить тест для мужчин нации, чтобы определить их коэффициент красоты. Идея, объясняет она, заключается в том, что мужчина может отправить онлайн -изображение своего лица x; в YoMan! и "мгновенно" получит автоматический ответ BQ b; .
1. В качестве первого шага вы решаете использовать метод K ближайших соседей (KNN), чтобы присвоить оценку BQ b; новому тестовому изображению x;.
Опишите, как определить оптимальное количество соседей K для использования.
2. Ваш линейный менеджер доволен вашим алгоритмом, но разочарован тем, что он не дает простого объяснения красоты, которое она может представить в будущей версии YoMan! журнала.
Чтобы решить эту проблему, вы решили создать модель, основанную на линейной регрессии. То есть
где w - вектор параметров (весовых коэффициентов), выбранный для минимизации
(a) После обучения (поиска подходящего w), как может YoMan! объяснить своим читателям простым способом какие черты лица важны для определения BQ человека?
(b) Опишите полностью и математически метод обучения этой модели линейной регрессии. Ваше объяснение должно быть достаточно подробным, чтобы программист мог непосредственно реализовать его.
(c) Обсудите любые последствия ситуации D > N .
(d) Обсудите любые преимущества/недостатки использования модели линейной регрессии по сравнению с использованием подхода KNN.
278
ЧЕРНОВИК главы от 9 марта 2010 года
15 ГЛАВА
Неконтролируемое уменьшение линейных размеров
15.1 Многомерные пространства – многообразия низкой размерности
В задачах машинного обучения данные часто имеют большую размерность – изображения, многословные описания, экспрессия генов и т.д. В таких случаях мы не можем ожидать, что обучающие данные будут плотно заполнять пространство, а это означает, что будут большие части, в которых о данных мало что известно. Для цифр, написанных от руки в главе (14), данные имеют размерность 784. Для двоичных значений в пикселях возможное количество изображений, которые когда-либо могли существовать, равно 2784 ; 10236 . Тем не менее, мы ожидали бы, что только несколько примеров цифр должны быть достаточными (для человека), чтобы понять, как распознать цифру 7. Таким образом, изображения, похожие на цифры, должны занимать сильно ограниченное подпространство из 784 измерений, и мы ожидаем, что для описания данных с приемлемой точностью будет достаточно небольшого числа направлений. Несмотря на то, что векторы данных могут быть очень многомерными, они, как правило, лежат близко к "многообразию" с гораздо меньшей размерностью (неофициально двумерное многообразие соответствует искривленному листу бумаги, помещенному в пространство с большей размерностью), что означает, что распределение данных сильно ограничено.
Здесь мы сосредоточимся на методах уменьшения линейных размеров, для которых существуют эффективные в вычислительном отношении подходы. В этом подходе точка данных x с высокой размерностью "проецируется" на вектор y с меньшей размерностью с помощью
где неквадратичная матрица F имеет размеры dim (y) ; dim (x), где dim (y) < dim (x). Методы, описанные в этой главе, в основном не являются вероятностными, хотя многие из них имеют естественную вероятностную интерпретацию. Например, PCA тесно связан с Факторным Анализом, описанным в главе (21).
15.2 Анализ Основных \Принципиальных\ Компонентов
Если данные лежат близко к гиперплоскости, как на рис. 15.1, мы можем точно аппроксимировать каждую точку данных, используя векторы, которые охватывают только гиперплоскость. По сути, мы пытаемся найти систему координат малой размерности, в которой мы могли бы приблизительно представлять данные. Мы выражаем приближение для точки данных xn как
Здесь вектор c является константой и определяет точку на гиперплоскости, а bi определяют векторы на гиперплоскости (также известные как "коэффициенты главных компонент" или "нагрузки"). yin - это низкоразмерные значения, которые могут быть использованы для определения координаты данных. Уравнение(15.2.1) описывает, как найти реконструкцию ~xn, учитывая представление с меньшей размерностью yn (которое имеет компоненты yin , i = 1, . . . , M). Для пространства данных размерности
279 Анализ основных компонентов
Рисунок 15.1: При уменьшении линейных размеров гиперплоскость подбирается таким образом, чтобы среднее расстояние между точками данных (красные кольца) и их проекциями на плоскость (черные точки) было минимальным.
dim (x) = D, мы надеемся точно описать данные, используя лишь небольшое число M« D координат y.
Чтобы определить наилучшее представление с меньшим размером, удобно использовать квадратичную ошибку расстояния между x и его восстановлением ~x:
Несложно показать, что оптимальное смещение c определяется как среднее значение данных ;n xn /N . Поэтому мы предполагаем, что данные были отцентрированы (имеют нулевое среднее значение ; nxn = 0), так что мы можем установить c равным нулю и сосредоточиться на поиске оптимального базиса B, приведенного ниже.
15.2.1 Получение оптимальной линейной реконструкции
Для нахождения наилучших базисных векторов B= [b1,….,bM]( определив [B]i,j = bij ) и соответствующие низкоразмерные координаты Y =[ y1 , . . . , yN ], мы можем минимизировать сумму квадратов разностей между каждым вектором x и его реконструкцией ~x:
где X = [x1 , . . . , xN ].
Рассмотрим преобразование Q базиса B таким образом, чтобы ~ B ; BQ было ортонормированной матрицей, ~BT ~B = I. Поскольку Q обратимо, мы можем записать BY = ~BQ;1 Y ; ~B;, что имеет ту же форму, что и BY, хотя и с ограничением ортонормированности для ~B. Следовательно, без потери общности мы можем рассмотреть уравнение (15.2.3) в соответствии с ограничением ортонормированности BT B = I, а именно, что базисные векторы взаимно ортогональны и имеют единичную длину.
Дифференцируя уравнение (15.2.3) относительно ykn, мы получаем (используя ограничение ортонормированности)
Следовательно, квадратичная ошибка E(B, Y) имеет нулевую производную, когда
280 ЧЕРНОВИК от 9 марта 2010 г. Анализ основных компонентов
Теперь мы подставим это решение в уравнение (15.2.3), чтобы записать квадрат ошибки только как функцию от B. С помощью
Цель E(B) становится
Поскольку ( I ; BBT )2, (используя BT B = I)
Следовательно, цель становится
где S - выборочная ковариационная матрица данных 1
Чтобы минимизировать уравнение (15.2.8) при ограничении BT B = I, мы используем набор множителей Лагранжа L, так что цель состоит в минимизации
(пренебрегая постоянным предиктором N ; 1). Поскольку ограничение симметрично, мы можем предположить, что L также симметрично. Дифференцируя относительно B и приравнивая к нулю, мы получаем, что при оптимальном
SB = BL (15.2.11)
Это форма собственного уравнения, так что решение задается путем принятия L за диагональ и B как матрица, столбцы которой являются соответствующими собственными векторами S. В этом случае trace (SBBT )= trace (L), что равно сумма собственных значений, соответствующих собственным векторам, образующим B. Поскольку мы хотим минимизировать E(B), мы берем собственные векторы с наибольшими соответствующими собственными значениями.
Если мы упорядочим собственные значения ;1 ; ;2 , . . ., то квадрат ошибки будет задан следующим образом, из уравнения (15.2.8)
Хотя решение этой собственной задачи уникально, это служит только для определения подпространства решений, поскольку можно поворачивать и масштабировать B и Y таким образом, чтобы значение квадрата потерь было точно таким же. То обоснование выбора неповоротного собственного решения дается дополнительным требованием о том, чтобы основные компоненты соответствовали направлениям максимальной дисперсии, как объяснено в разделе (15.2.2).
1 Здесь мы используем несмещенную выборочную ковариацию просто потому, что это стандартно в литературе. Если бы мы заменили это на выборочную ковариацию, как определено в главе (8), единственное требуемое изменение ; это заменить N - 1 на N во всем, что не влияет на форму решений, найденных PCA.
ЧЕРНОВИК от 9 марта 2010 г. 281 Анализ основных компонентов
Рисунок 15.2: Проекция двумерных данных с использованием одномерного PCA. Показаны исходные данные- точки x (большие кольца) и их реконструкции x (маленькие точки) с использованием одномерного PCA. Линии представляют собой ортогональную проекцию исходной точки на первый собственный вектор. Стрелки — это два собственных вектора, масштаб которых равен квадратному корню из их соответствующих собственных значений. Данные были привязаны к нулевому среднему значению. Для каждой "высокоразмерной" точки данных x "низкоразмерное" представление y в данном случае задается расстоянием (возможно, отрицательным) от начала координат вдоль направления первого собственного вектора до соответствующей ортогональной точки проекции.
15.2.2 Критерий максимальной дисперсии
Сначала мы ищем единственное направление b, такое, чтобы при проецировании данных в это направление дисперсия этой проекции была максимальной среди всех возможных таких проекций. Используя уравнение (15.2.4) для одного вектора b, мы имеем
Проекция точки данных на направление b равна bT xn для вектора b единичной длины. Следовательно, сумма квадратов проекций равна
, который, игнорируя константы, является просто отрицательным значением уравнения (15.2.8) для единственного сохраненного собственного вектора b (с Sb = ;b). Следовательно, оптимальное единичное значение b , которое максимизирует дисперсию проекции, задается собственным вектором, соответствующим наибольшему собственному значению S. В соответствии с критерием, согласно которому следующее оптимальное направление должно быть ортонормировано первому, можно легко показать, что b(2) задается вторым по величине собственным вектором и так далее. Это объясняет, почему, несмотря на то, что уравнение потерь в квадрате (15.2.8) инвариантно по отношению что касается произвольного поворота (и масштабирования) базисных векторов, то векторы, заданные собственным разложением, обладают дополнительным свойством, заключающимся в том, что они соответствуют направлениям максимальной дисперсии. Эти направления максимальной дисперсии, найденные с помощью PCA, называются главными \принципиальными \ направлениями.
15.2.3 Алгоритм PCA
Процедура для PCA представлена в алгоритме (14). В обозначении y = Fx проекционная матрица F соответствует ET . Аналогично для уравнения реконструкции (15.2.1) координата yn соответствует ET xn и bi соответствуют ei . Реконструкции PCA представляют собой ортогональные проекции данных на подпространство, охватываемое собственными векторами, соответствующими M наибольшим собственным значениям ковариационной матрицы, см. рис.(15.2).
Рисунок 15.3: Верхний ряд: выборка цифры 5, взятая из базы данных, содержащей 892 примера. Под каждой цифрой показана реконструкция с использованием 100, 30 и 5 собственных векторов (сверху вниз). Обратите внимание, что реконструкции для меньшего количества собственных векторов выражают меньшую вариабельность друг от друга и больше напоминают среднее значение из 5 цифр.
282 ЧЕРНОВИК от 9 марта 2010 г. Анализ основных компонентов
Алгоритм 14 Анализ Основных Компонентов для формирования M-мерной аппроксимации набора данных {xn , n = 1, . . . , N} с параметром dim xn = D.
1: Найдите вектор среднего значения выборки D ; 1 и ковариационную матрицу D ; D
2. Найдите собственные векторы e1 , . . . , eM ковариационной матрицы S, отсортированные таким образом, чтобы собственное значение ei было больше, чем ej для i < j. Сформируйте матрицу E = [e1 , . . . , eM ].
3: Представление каждой точки данных xn в меньшем размере задается через
4: Приблизительная реконструкция исходной точки данных xn равна
5: Общая квадратичная ошибка по всем обучающим данным, полученным в результате аппроксимации, равна
, где ;M +1 . . . ;N - собственные значения, отбрасываемые в проекции.
Пример 68 (Уменьшение размерности цифр). У нас есть 892 примера рукописных 5-х, где каждое изображение состоит из пикселей реального размера 28 ; 28, см. рис. 15.3. Каждая матрица изображений складывается в 784 размерный вектор, дающий матрицу данных X размером 784 ; 892. Ковариационная матрица этих данных имеет спектр собственных значений, как показано на рис. 15.4, где мы отображаем только 100 самых больших собственных значений. Обратите внимание, что примерно после 40 компонентов среднеквадратичная ошибка восстановления мала, что указывает на то, что данные действительно лежат близко к 40-мерной гиперплоскости. Собственные значения вычисляются с использованием pca.m.
Реконструкции с использованием различного числа собственных векторов (100, 30 и 5) показаны на рис. 15.3. Примечание как при использовании лишь небольшого числа собственных векторов реконструкция больше напоминает среднее изображение.
Пример 69 (Собственные поверхности). На рис. 15.5 мы приводим примеры изображений, для которых мы хотим найти представление с меньшим размером. С помощью PCA представлены первые 49 "собственных поверхностей", а также реконструкции исходных данных с использованием этих собственных поверхностей, см. рис.15.6.
собственное значение
Рисунок 15.4: Для данных digits, состоящих из 892 примеров цифры 5, каждое изображение представлено 784-мерным вектором. На графике представлены 100 наибольших собственных значений (, масштабированных таким образом, что наибольшее собственное значение выборочной ковариационной матрицы равно 1,) выборочной ковариационной матрицы .
ПРОЕКТ от 9 марта 2010 283 Анализ основных компонентов
Рисунок 15.5: 100 из 120 обучающих изображений (40 человек, по 3 изображения каждого человека). Каждое изображение состоит из 92;112 = 10304 пикселей в оттенках серого. Обучающие данные масштабируются таким образом, что при представлении в виде изображения компоненты каждого изображения суммируются в 1. Среднее значение каждого пикселя по всем изображениям составляет 9,70 ; 10-5 . Это лишь часть из 400 изображений, представленных в полном объеме на сайте Olivetti Research Face Базы данных.
Рисунок 15.6: (а): SVD- реконструкция изображений на рисунке (15.5) с использованием комбинации из 49 собственных изображений. (б): Собственные изображения получены с помощью SVD на рис. (15.5) и выбирает 49 собственных векторов с наибольшим собственным значением. Изображения, соответствующие наибольшим собственным значениям, содержатся в первом ряду, а затем в следующем 7 в следующем ряду и т.д. Среднеквадратичная ошибка восстановления составляет 1,121 ; 10-5, что является небольшим улучшением по сравнению с PLSA (см. рис. 15.14).
15.2.4 PCA и ближайшие соседи
Для обработки многомерных данных вычисление квадрата Евклидова расстояния между векторами может быть дорогостоящим, а также чувствительным к шуму. Поэтому часто бывает полезно спроецировать данные в виде таблицы\ типа сперва представления\ меньшей размерности. Например, при создании классификатора для различения цифр 1 и 7, пример (67), мы можем сначала сформировать представление с меньшим размером, игнорируя метку класса (чтобы создать набор данных из 1200 обучающих точек). Каждая из обучающих точек xn затем проецируется в меньшую размерность PCA-представление yn. Впоследствии все вычисления расстояния (xa ; xb )2 заменяются на (ya ; yb )2 . Чтобы обосновать это, рассмотрим
где последнее равенство обусловлено ортонормированностью собственных векторов : ET E = I.
Использование 19 основных компонентов (см. пример (70), почему было выбрано это число) и правила ближайшего соседа для классификации единиц и семерок дало ошибку тестового набора, равную 14 в 600 примерах, по сравнению с 18 при использовании стандартного метода для непроецированных данных. Как может быть, что эффективность классификации улучшилась? Правдоподобным объяснением является то, что новое представление данных в формате PCA является более надежным, поскольку сохраняются только направления крупномасштабных изменений в пространстве, а направления с низкой дисперсией отбрасываются.
284 ЧЕРНОВИК от 9 марта 2010 г. Данные большого размера
Количество ошибок -
количество собственных значений
Рисунок 15.7: Определение оптимального размера PCA для классификации цифр, написанных от руки, с использованием ближайших соседей. Использовано 400 обучающих примеров, а ошибка проверки отображена на графике еще 200 примеров. Основываясь на ошибке проверки, мы видим, что значение 19 является разумным.
Пример 70 (Поиск наилучшего измерения PCA). Имеется 600 примеров с цифрой 1 и 600 примеров с цифрой 7. Половину данных мы будем использовать для обучения, а другую половину - для тестирования. 600 обучающих данных примеры были дополнительно разделены на обучающий набор из 400 примеров и отдельный набор для проверки, состоящий из 200 примеров. Для уменьшения размерности входных данных был использован PCA, а затем для классификации 200 примеров проверки были использованы ближайшие соседи. Были рассмотрены различные уменьшенные размеры, и, основываясь на результатах
проверки, в качестве оптимального количества сохраненных компонентов PCA было выбрано 19, см. рис.15.7. Ошибка независимого тестирования на 600 независимых примерах с использованием 19 размеров составила 14.
15.2.5 Комментарии к PCA
‘Внутреннее’ измерение \размерность \ данных
Сколько измерений должно иметь линейное подпространство? Из уравнения (15.2.12) следует, что ошибка восстановления пропорциональна сумме отброшенных собственных значений. Если мы построим спектр собственных значений (набор собственных значений, упорядоченных по убыванию значения), мы могли бы надеяться увидеть несколько больших значений и много маленьких значений. Если данные действительно лежат близко к M-мерной гиперплоскости, мы увидим M больших собственных значений, а остальные будут очень малы. Это даст представление о количестве степеней свободы в данных, или о внутренней размерности. Направления, соответствующие малым собственным значениям, затем интерпретируются как "шум".
Нелинейное уменьшение размерности
В PCA мы предполагаем, что данные лежат близко к гиперплоскости. Действительно ли это хорошее описание? В более общем плане мы ожидали бы, что данные будут лежать на криволинейных многообразиях малой размерности. Кроме того, данные часто группируются – примеры рукописных "4" выглядят похожими друг на друга и образуют кластер, отдельный от кластеров «8». Тем не менее, поскольку уменьшение линейных размеров является относительно простым в вычислительном отношении процессом, это один из наиболее распространенных методов уменьшения размеров.
15.3 Данные с Высокой Размерностью
Вычислительная сложность вычисления собственного разложения матрицы D ; D равна O (D3 ). Поэтому вам может быть интересно, как можно выполнить PCA с данными большой размерности. Например, если у нас есть 500 изображений, каждое размером 1000 ; 1000 = 106 пикселей, ковариационная матрица будет иметь размерность 106 ; 106. Вычисление собственного разложения этой матрицы может оказаться сложной вычислительной задачей. Однако в этом случае, поскольку таких векторов всего 500, число ненулевых собственных значений не могут превышает 500. Можно использовать этот факт, чтобы ограничить сложность O( min(D, N )3) , как описано ниже.
ЧЕРНОВИК от 9 марта 2010 года 285 Данных Высокой Размерности
15.3.1 Собственное разложение для N < D
Сначала обратите внимание, что для нулевых средних данных выборочная ковариационная матрица может быть выражена как
В матричной записи это может быть записано как
где матрица X размером D ; N содержит все векторы данных:
Поскольку собственные векторы матрицы M равны собственным векторам ;M для скаляра ;, можно более просто рассмотреть собственные векторы XXT. Записывая матрицу собственных векторов D ; N в виде E (это неквадратичная тонкая матрица, поскольку собственных значений будет меньше, чем размеров данных), а собственные значения - в виде диагональной матрицы ; размером N ; N, собственное разложение ковариации S равно
где мы определили ~E = XT E. Последнее выражение, приведенное выше, представляет собой уравнение собственного вектора для XTX. Это матрица размерности N ;N, так что вычисление собственного разложения требует O( N3) операций, по сравнению с обычными операциями в исходном многомерном пространстве . Таким образом, мы можем более легко вычислить собственные векторы ~E и собственные значения ; этой матрицы. Найдя, мы используем тот факт, что собственные значения S задаются диагональными элементами ;, а собственные векторы -
15.3.2 PCA с помощью разложения по сингулярным значениям
Альтернативой использованию процедуры собственной декомпозиции для поиска решения PCA является использование Сингулярной Декомпозиции Значения (SVD) матрицы X размерности D ; N. Это задается формулой
где UT U = ID и VT V = IN, а D - диагональная матрица (положительных) сингулярных значений. Мы предполагаем, что при разложении сингулярные значения упорядочены таким образом, что верхний левый диагональный элемент D содержит наибольшее сингулярное значение. Затем матрица XXT может быть записана в виде
Поскольку UD2 UT имеет форму собственного разложения, решение PCA эквивалентно задается путем выполнения SVD-разложения X, для которого собственные векторы затем задаются через U, а соответствующие собственные значения - через квадрат сингулярных значений.
Уравнение(15.3.6) показывает, что PCA является формой метода матричной декомпозиции:
где UM , DM , VM соответствуют принятию только первых M сингулярных значений полных матриц.
286 ЧЕРНОВИК от 9 марта 2010 г. Латентный семантический анализ
Рисунок 15.8: Данные документа для словаря содержат- 10 слов и 1200 документов. Черный цвет указывает на то, что в документе присутствовало слово. Данные состоят из двух ‘похожих’ тем (отличающихся только использованием первых двух слов) и случайной фоновой темы.
15.4.Латентный Семантический Анализ
В литературе по анализу документов PCA также называется латентно-семантическим анализом и связан с анализом набора из N документов, где каждый документ dn , n = 1, . . . , N представлен вектором
количества встречающихся слов. Например, первый элемент xn1 может подсчитывать, сколько раз встречается слово ‘кошка" в документе n, xn2 указано количество встречаемости слова "собака" и т.д. Этот набор \пакет, баг\ слов 2 формируется путем предварительного выбора словаря из D слов. Векторный элемент xni - это (возможно, нормализованное) количество вхождений слова i в документе n. Обычно D будет большим, порядка 106, а x будет очень редким, поскольку любой документ содержит лишь малую часть доступных слов в словаре. Учитывая набор документов D, целью LSA является формирование представления каждого документа в меньшем размере. Вся база данных документов представлена так называемой матрицей терминов-документов
который имеет размер D ; N , см., например, рис.15.8. В этом небольшом примере матрица термина -документ " является "короткой и толстой", тогда как на практике чаще всего матрица будет "высокой и тонкой’.
Пример 71 (Скрытая тема). У нас есть небольшой словарь, содержащий слова грипп, простуда, головная боль, нос, температура, кровать, кошка, дерево, автомобиль, нога. База данных содержит большое количество статей, в которых обсуждаются болезни, а также статьи, в которых, как представляется, говорится о последствиях гриппа, в дополнение к некоторой справочной информации документы, не относящиеся к конкретным заболеваниям. В некоторых более официальных документах используется исключительно термин "грипп -инфлюенца \ОРВИ", в то время как в других, более "бульварных" документах используется неофициальный термин "ринит, грипп -флю \гриппозная инфекция, ринит". Каждый документ представлен простым описанием в стиле набора слов, а именно 10-мерным вектором, в котором элементу i этого вектора присваивается значение 1, если в документе встречается слово i, и 0 в противном случае. Данные представлены на рисунке(15.8). Данные генерируются с использованием искусственного механизма, описанного в demoLSI.m.
Результат использования PCA для обработки этих данных представлен на рис. 15.9, где мы строим собственные векторы, масштабированные по их собственному значению. Первый собственный вектор объединяет все слова, обозначающие "грипп \ОРВИ", а второй описывает различное использование терминов "грипп" и "ринит\ гриппозная инфекция".
Изменение масштаба
В LSA принято масштабировать преобразование таким образом, чтобы проецируемые векторы имели приблизительно единичную ковариацию (при условии центрированных данных). С помощью
ковариация проекций получается из
2 В более общем плане можно рассмотреть подсчет терминов, в котором терминами могут быть отдельные слова, наборы слов или даже подзаголовки.
ЧЕРНОВИК от 9 марта 2010 г. 287 Латентный семантический анализ
Рисунок 15.9: Диаграмма Хинтона матрицы собственных векторов E, где каждый столбец собственных векторов масштабируется соответствующим собственным значением. Красный цвет обозначает положительный результат, а зеленый - отрицательный (площадь каждого квадрата соответствует величина), показывая, что существует всего несколько больших собственных значений. Обратите внимание, что общий знак любого собственного вектора не имеет значения. Первый собственный вектор соответствует теме, в которой преобладают слова грипп, простуда, головная боль, нос, температура, постель. Второй собственный вектор указывает на то, что существует отрицательная корреляция между заболеваемостью гриппом и ОРВИ\ ринитом.
Учитывая y, приблизительная реконструкция ~x равна
Тогда Евклидово расстояние между двумя точками xa и xb приблизительно равно
Обычно игнорируют член D2M (и коэффициент 1/ (N ; 1)) и считают мерой различия в проецируемом пространстве, т.е. просто Евклидово расстояние между векторами y.
15.4.1 LSA для поиска информации
Рассмотрим большую коллекцию документов из Интернета, создав базу данных D. Наш интерес заключается в том, чтобы найти документ, наиболее похожий на указанный в запросе документ. Используя представление в виде набора слов для документа n, xn и аналогично для документа запроса, x;, мы решаем эту задачу, сначала определяя меру о различиях между документами, например
Затем выполняется поиск документа, который сводит к минимуму это различие:
и возвращает документ xn opt в качестве результата поискового запроса. Сложность этого подхода заключается в том, что представление в виде набора слов будет содержать в основном нули (т.е. будет очень редким). Следовательно, различия могут быть вызваны скорее "шумом", чем каким-либо реальным сходством между запросом и документом базы данных. LSA устраняет эту проблему использованием представления y с меньшей размерностью по сравнению с представлением x с большей размерностью. Представление y отражает основные вариации в данных и менее чувствительно к случайному некоррелированному шуму. Таким образом, использование различий, определенных в терминах меньшего размера y, является более надежным и, вероятно, позволяет извлекать больше полезных документов.
Разница в квадрате между двумя документами также может быть записана как
Если, как это обычно делается, представления в виде набора слов масштабируются так, чтобы иметь единичную длину,
, так что ;xT ;x = 1, расстояние равно
288 ЧЕРНОВИК Отчета от 9 марта 2010 года С недостающими данными РСА
Рисунок 15.10: (а): Два вектора-мешка слов. Евклидово расстояние между ними велико. (б): Нормализованные векторы. Евклидово расстояние теперь напрямую связано с углом между векторами. В этом случае два документа с одинаковой относительной частотой встречаемости слов будут иметь одинаковые различия, даже если количество встречаемости слов различно.
Рисунок 15.11: Вверху: исходная матрица данных X. Черный цвет отсутствует, белый присутствует. Данные построены из набора всего из 5 базисных векторов. Посередине: X с отсутствующими данными (разреженность 80%). Внизу : найдена реконструкция с использованием svdm.m, SVD для поиска недостающих данных. Эта проблема, по сути, проста, поскольку, несмотря на множество пропущенных элементов, данные действительно построены на основе модели, для которой подходит SVD. Такие методы находят применение в коллаборативной фильтрации и системах рекомендаций, где требуется "заполнить" недостающие значения в матрице.
и можно эквивалентно рассмотреть косинусоидальное сходство
где ; - угол между единичными векторами ;x и ;x` , рис.15.10.
PCA, возможно, не является оптимальным для анализа документов, поскольку мы ожидаем, что наличие скрытой темы будет способствовать получению только положительных результатов в данных. Родственная версия PCA, в которой декомпозиция ограничена наличием положительных элементов, называется PLSA и обсуждается в разделе (15.6).
Пример 72. Продолжая пример с Гриппом, пользователь, загружающий документ с запросом, который использует термин "ринит \грипп" также может быть заинтересован в документах о "гриппе". Однако поисковый запрос ‘ринит \грипп’ не содержит слова "грипп", так как же можно получить такие документы? Поскольку первый компонент, использующий PCA (LSA), группирует все термины "грипп" вместе, если мы используем только первый компонент представления y для сравнения документов, это позволит получить документы независимо от того, используется ли термин "ринит\ грипп, флю’ или ‘грип\ инфлюэнца’.
15.5 PCA С Пропущенными Данными
Если значения матрицы данных X отсутствуют, стандартный алгоритм PCA, описанный выше, не может быть реализован. К сожалению, не существует "быстрого" решения PCA, когда некоторые из xni отсутствуют и необходимо использовать более сложные числовые процедуры. Наивный подход в этом случае — запросить, чтобы
ЧЕРНОВИК от 9 марта 2010 г. 289 PCA С недостающими данными
ошибка восстановления в квадрате была небольшой только для существующих элементов X. То есть
, где ;in = 1, если доступна i-я запись n-го вектора, и равно нулю в противном случае. Дифференцируя, как и прежде, мы находим, что оптимальные веса удовлетворяют (при условии, что BT B = I),
затем я подставляю это выражение в квадрат ошибки и минимизирую ошибку относительно B в соответствии с ограничением ортонормированности. Альтернативная итеративная процедура оптимизации заключается в следующем: Сначала выберите случайную матрицу ;B размером D ; M. Затем повторяйте до сходимости следующие два шага:
Оптимизировать Y для фиксированного B
Для фиксированного ;B указанная выше E (;B, Y) является квадратичной функцией матрицы Y, которая может быть оптимизирована непосредственно. Дифференцируя и приравнивая к нулю, получаем условие неподвижной точки
Определяем
тогда в матричной записи мы имеем набор линейных систем:
Можно решить каждую линейную систему, используя исключение по Гауссу (можно избежать явной инверсии матрицы, используя оператор \ в MATLAB). Возможно, одна или несколько из вышеперечисленных линейных систем недостаточно определены – это может произойти, когда в n-м столбце данных X меньше наблюдаемых значений чем есть компоненты M. В этом случае можно использовать псевдоинверсию, чтобы получить решение минимальной длины.
Оптимизировать B для фиксированного Y
Теперь замораживаем ; и рассматриваем функцию
Для фиксированного ; приведенное выше выражение является квадратичным в матрице B, которая снова может быть оптимизирована с помощью линейной алгебры. Это соответствует решению набора линейных систем для i-й строки матрицы B:
, где
Математически это означает, что b(i) = F(i);1 m (i).
Таким образом, гарантируется итеративное уменьшение значения квадрата потери погрешности до тех пор, пока не будет достигнут минимум. Этот метод реализован в svdm.m. Обратите внимание, что доступны эффективные методы, основанные на обновлении решения по мере поступления нового столбца X по одному (обновление в режиме онлайн), см., например [49].
290 ЧЕРНОВИК от 9 марта 2010 г. С недостающими данными PCA
15.5.1 Определение основных \принципиальных направлений
Для случая с отсутствующими данными базис B, найденный с использованием описанного выше метода, основан только на минимизации квадратичной ошибки восстановления и, следовательно, не обязательно удовлетворяет критерию максимальной дисперсии (или основных направлений), а именно, что столбцы B указывают вдоль собственных направлений. Для заданных B, Y с приближенным разложением X ; BY мы можем вернуть новый ортонормированный базис U, выполнив SVD для завершенных данных, BY = USVT, чтобы вернуть ортонормированный базис B ; U. В общем случае, однако, это это потенциально требует больших вычислительных затрат. Если требуются только основные направления, альтернативой является явное преобразование решения B с использованием обратимой матрицы Q:
Используя новый базис ~B = BQ, чтобы привести решение в соответствие с основными направлениями, нам нужно
Другими словами
Формируя SVD из B,
и подставляя в уравнение (15.5.12), мы получаем требование
Поскольку UT U = I и VT V = VVT = I, мы можем использовать
Следовательно, учитывая решение B, мы можем найти основные направления из SVD в B, используя
Если матрица B размером D ; M неквадратична M < D, то матрица D будет неквадратичной и необратимой. Чтобы сделать вышеприведенное более понятным, можно добавить D к столбцам идентификатора:
где IK - это K-й столбец единичной матрицы, и используйте D` вместо D, указанного выше.
15.5.2 Коллаборативная фильтрация с использованием PCA с пропущенными данными
База данных содержит набор векторов, каждый из которых описывает рейтинги фильмов для пользователя в базе данных. i-ая запись в векторе x указывает оценку, которую пользователь дает i-му фильму. Матрица X = [x1 , . . . , xN] для всех N пользователей содержит много пропущенных значений, поскольку любой отдельный пользователь выставит оценку только небольшому набору возможных D фильмов. В практическом примере у вас может быть D = 10 000 фильмов и N = 1 000 000 пользователей. Для любого пользователя n задача состоит в том, чтобы предсказать разумные значения для отсутствующих элементов вектора рейтинга xn, тем самым предложив, какие фильмы он хотел бы посмотреть. Рассматривается как недостающие данные проблема в том, что можно подогнать B и Y, используя svdm.m, как указано выше. Учитывая B и Y, мы можем построить реконструкцию для всех элементов X, используя
таким образом, мы получаем прогноз для недостающих значений.
ЧЕРНОВИК от 9 марта 2010 г. 291 Метод Матричной Декомпозиции
Рисунок 15.12: (а): Неполное представление. Слишком мало базисных векторов для представления точек данных. (b): Слишком полное представление. Существует слишком много базисных векторов, чтобы сформировать уникальное представление точки данных в виде линейной комбинации базисных векторов.
Рисунок 15.13: (а): Общий PLSA. (b): Условный PLSA. Несмотря на то, что модель представлена в виде графа, при интерпретации требуется соблюдать некоторую осторожность, см. текст.
15.6 Методы Матричной Декомпозиции
Учитывая матрицу данных X, для которой каждый столбец представляет точку данных, приблизительное разложение матрицы имеет вид X ; BY на базисную матрицу B и весовую (или координатную) матрицу Y. Символически, разложение матрицы имеет вид
X : Данные; ;
B : Основа
Y : Веса/компоненты;
В этом разделе мы рассмотрим некоторые распространенные методы матричной декомпозиции.
Неполная декомпозиция
Когда M < D, базисных векторов меньше, чем размерностей, рис.15.12a). Тогда матрица B называется "высокой" или "тонкой’. В этом случае матрица Y формирует приближенное представление данных X с меньшей размерностью, классическим примером которого является PCA.
Чрезмерно полные разложения
Для M > D базис является чрезмерно полным, поскольку базисных векторов больше, чем измерений, рис.15.12b). В таких случаях либо на основу, либо на компоненты накладываются дополнительные ограничения. Например, может потребоваться что только небольшое число из большого числа доступных базисных векторов используется для формирования представления для любого заданного x. Такие разреженные представления распространены в теоретической нейробиологии, где представляют интерес вопросы энергоэффективности, скорости обработки и надежности [214, 155, 252].
15.6.1 Вероятностный латентный семантический анализ
Рассмотрим два объекта, x и y, где dom(x) = {1, ... , I} и dom(y) = {1, ... , J}. У нас есть счетная
матрица с элементами Cij, которая описывает количество раз, когда наблюдались значения x = i, y = j. Мы можем преобразуйте эту счетную матрицу в ‘частотную’ матрицу p с элементами
Наш интерес состоит в том, чтобы найти разложение этой частотной матрицы в виде, показанном на рис. 15.13а)
ПРОЕКТ от 9 марта 2010 г. Методы Матричной Декомпозиции
, представляющие собой форму разложения матрицы на базис B и координаты Y. Это можно интерпретировать как обнаружение скрытых признаков z, которые описывают совместное поведение x и y.
Алгоритм обучения в стиле EM
Чтобы найти приближенную декомпозицию, нам сначала нужна мера разницы между матрицей с элементами pij и аппроксимацией с элементами ~pij . Поскольку все элементы ограничены от 0 до 1 и в сумме равны 1, мы можем интерпретировать p как общую вероятность, а ~p- как приближение к ней. Для вероятностей полезной мерой расхождения является дивергенция Кульбака-Лейблера
Поскольку p является фиксированным, минимизация расхождения Кульбака-Лейблера относительно аппроксимации p эквивалентна максимизации ‘вероятностного’ члена <log ~p>p . Это
Удобно вывести алгоритм в стиле EM для изучения ~p(x|z), ~p(y|z) и ~p(z). Для этого рассмотрим
, где ;z подразумевает суммирование по всем состояниям переменной z. При перестановке это дает оценку,
Подключив это к приведенному выше термину "вероятность", мы получим ограничение
M-шаг
Для фиксированных ~p(x|z), ~p(y|z) вклад в оценку от ~p(z) равен
Несложно заметить, что оптимальное значение ~p(z) равно
поскольку уравнение (15.6.9) с точностью до константы равно KL(;x,y q(z|x, y)p(x, y)| ~p(y|z)). Аналогично, для фиксированных ~p(y|z), ~p(z), вклад в оценку от ~p(x|z) равен
Следовательно, оптимально
и аналогично,
ЧЕРНОВИК от 9 марта 2010 г. 293 Метод Матричной Декомпозиции
Рисунок 15.14: (а) Условная реконструкция PLSA изображений на рисунке (15.5) с использованием положительной (выпуклой) комбинации из 49 положительных базовых изображений рисунка (b). Среднеквадратичная ошибка восстановления составляет 1,391 ; 10;5 . Базовые изображения, как правило, более "локализованы", чем соответствующие собственные изображения (рис.15.6, б). Здесь можно просматривать локальные структуры, такие как лбы, подбородки и т.д.
Электронный \Е- шаг
Оптимальная настройка для распределения q на каждой итерации -
который фиксируется на протяжении всего M-го шага.
Процедура приведена в алгоритме(15), а демонстрация приведена в demoPLSA.m. Уравнение ‘правдоподобия’ (15.6.5) гарантированно увеличивается (а уравнение дивергенции Кульбака-Лейблера (15.6.4) уменьшается) при итерации между E и M-шагами, поскольку метод аналогичен обобщениям процедуры EM, такие, как использование более простых q-распределений (соответствующих обобщенным процедурам EM), являются немедленными на основе модификации приведенного выше вывода.
Соответствующая вероятностная модель
Для переменных x, y, z, где z скрыто, и dom(x) = {1, . . . , I} , dom(y) = {1, . . . , J} , dom(z) = {1, . . . , K} рассмотрим распределение
и данные D = {(xn , yn ) , n = 1, . . . , N }. Предполагая, что данные получены из уравнения (15.6.15), логарифмическая вероятность равна
, где
Если xn , yn выборки взяты из распределения p(x, y), то в пределе бесконечного числа выборок, N ; ;, уравнение (15.6.16) принимает вид
что и является уравнением (15.6.5). С этой точки зрения, несмотря на то, что мы начали с набора выборок, в пределе имеет значение только распределение наблюдаемых данных, p(x, y). Общий код для случая с конечной выборкой, обученный с помощью EM, приведен в demoMultinomialpXYgZ.m. Смотрите также упражнение(168).
Полностью вероятностная интерпретация PLSA может быть выполнена с помощью Пуассоновских процессов[56]. Связанная с этим вероятностная модель представляет собой скрытое распределение Дирихле, которое описано в разделе (20.6.1).
294 ПРОЕКТ методов декомпозиции матрицы от 9 марта 2010 г.
Алгоритм 15 PLSA: Задана частотная матрица p(x = i, y = j), возвращаем разложение
k)p(y = j|z = k)p(z = k). Смотрите plsa.m
1: Инициализируем p(z), p(x|z), p(y|z).
2: пока не сходится, делаем
3: Устанавливаем q(z|x, y) = Pp(z|x, y). . E-шаг
4: Задаем p(x|z) ; P y p(x, y)q(z|x, y) . M-шаг
5: Установить p(y|z) ; x p(x, y)q(z|x, y)
6: завершить, пока
7: Установите p(z) = x,y p(x, y)q(z|x, y)
Алгоритм 16 Условное PLSA: Учитывая частотную матрицу p(x = i|y = j), возвращаем разложение k p(x = i|z = k)p(z = k|y = j). Смотрите plsaCond.m
1: Инициализируем p(x|z), p(z|y).
2: пока не сходится, делаем
3: Устанавливаем q(z|x, y) =Pp(z|x, y). . Электронный\Е- шаг
4: Задаем p(x|z) ; P y p(x|y)q(z|x, y) . M-шаг
5: Установите p(z|y) ; x p(x|y)q(z|x, y)
6: завершите цикл
Условный PLSA
В некоторых случаях более естественно рассматривать условную частотную матрицу
p(x = i|y = j) (15.6.19)
и найдите приблизительное разложение
, как показано на рис. 15.13б). Вывод алгоритма в стиле EM для этого прост (см. упражнение (167)) и представлен в алгоритме (16), который эквивалентен алгоритму факторизации неотрицательной матрицы из [171].
Пример 73 (Определение базиса). Набор изображений представлен на рис. 15.15, а. Они были созданы первым определением 4-кратных базовых изображений рис.(15.15б). Каждое базовое изображение является положительным и масштабируется таким образом, чтобы сумма пикселей была равна единице, ;i p(x = i|z = k) = 1, где k = 1, ... , 4, а x индексирует пиксели, см. рис.(15.15). Затем мы суммируем каждое из этих изображений, используя случайно выбранный положительный набор из 4 весов (при условии, что сумма весов равна 1), чтобы сгенерировать обучающее изображение с элементами p (x = i|y = j), и j индексирует обучающее изображение. Это повторяется 144 раза, чтобы сформировать полный обучающий набор, рис.15.15а. Задача состоит в том, чтобы, учитывая только обучающий набор изображений, чтобы восстановить основу, из которой были сформированы изображения. Мы предполагаем, что знаем правильное количество базовых изображений, а именно 4. Результаты использования условного PLSA в этой задаче представлены на рисунке (15.15c), а с использованием SVD - на рисунке (15.15d). В этом случае PLSA находит правильную ‘естественную’ основу, соответствующую способу создания изображений. Собственная база данных столь же хороша с точки зрения возможности представления любого из обучающих изображений, но в данном случае не соответствует ограничениям, в соответствии с которыми были сгенерированы данные
15.6.2 Расширения и вариации
Неотрицательная матричная факторизация
Неотрицательная Матричная факторизация (NMF) рассматривает декомпозицию, в которой и базисная, и весовая матрицы имеют неотрицательные элементы. Ранний пример этой работы - это форма ограниченного Множителя
ЧЕРНОВИК от 9 марта 2010 г. 295 Методы матричной декомпозиции
Рисунок 15.15: (a): Обучающие данные, состоящие из положительной (выпуклой) комбинации базовых изображений. (b): Выбранные базовые изображения, из которых извлекаются обучающие данные. (c): Базис, изученный с использованием условных PLSA на основе обучающих данных. Это практически неотличимо от истинного базиса. (d): Собственный базис (иногда называемый "собственными поверхностями’).
Анализа[217]. Тесно связана с этим работа [171], которая является обобщением PLSA (поскольку нет требования, чтобы базис или компоненты сводились к единице). Во всех случаях существуют алгоритмы обучения в стиле EM, хотя их сходимость может быть медленной. Естественное ослабление - это когда только один из факторов в разложении должен быть неотрицательным. Мы столкнемся с подобными моделями при обсуждении Независимого Анализа Компонентов, раздел (21.6).
Обучение на основе градиента
Алгоритмы в стиле EM просты в разработке и реализации, но могут демонстрировать низкую сходимость. Были разработаны методы на основе градиента, позволяющие одновременно оптимизировать базис и компоненты, но требуют параметризации, обеспечивающей достоверность решений[217].
Декомпозиции массивов
Несложно распространить этот метод на декомпозицию многомерных массивов, основанную также на более чем одном базисе. Например
Такие расширения требуют только дополнительной бухгалтерии \ библиотеки.
15.6.3 Применение PLSA/NMF
Физические модели
Неотрицательные разложения могут возникать естественным образом в определенных физических ситуациях. Например, в акустике положительные количества энергии линейно объединяются\ суммируются от различных источников сигнала, образуя наблюдаемый сигнал. Давайте представим, что в акустическом сигнале присутствуют два вида сигналов, скажем, от фортепиано и певца. Используя NMF, можно обучить две отдельные базы для этих случаев, а затем восстановить данный сигнал, используя только одну из этих основ. Это означает, что потенциально можно удалить певца из записи, оставив только пианино. Более стандартную вероятностную модель в акустике см. также в [285]. Это было бы аналогично восстановлению изображений на рис. 15.15а, используя, скажем, только одно из обученных базовых изображений, см. пример (73).
Моделирование цитат
У нас есть коллекция исследовательских документов, в которых цитируются другие документы. Например, в документе 1 могут содержаться ссылки на документы 3, 2, 10 и т.д. Можем ли мы определить ключевые исследования, основываясь только на списке ссылок для каждого документа статьи и сообщества, которые их цитируют? Обратите внимание, что это не то же самое, что поиск наиболее цитируемых документов – скорее, мы хотим идентифицировать документы с сообществами и определить их значимость для конкретного проекта \определить их отношения с сообществом.
296 ЧЕРНОВИК от 9 марта 2010 г. Методы декомпозиции матрицы фактор 1
(Обучение с подкреплением)
Обучение прогнозированию с помощью методов временных различий. Саттон.
Нейронные адаптивные элементы, которые могут решать сложные задачи контроля обучения. Барто и др.
Практические вопросы обучения с временными различиями. Тесауро.
(Обучение правил)
Обобщение, основанное на объяснении: объединяющий подход. Митчелл и др.
Обучение внутренних представлений путем распространения ошибок. Румельхарт и др.
Обучение, основанное на объяснении: альтернативный подход. Деджонг и др.
(Нейронные сети)
Обучение внутренних представлений путем распространения ошибок. Румельхарт и др.
Нейронные сети и дилемма смещения и дисперсии. Геман и др.
Архитектура обучения на основе каскадной корреляции. Фалман и др.
(Теория)
Деревья классификации и регрессии. Брейман и др.
Обучаемость и измерение Вапника-Червоненкиса. Блюмер и др.
Быстрое обучение в условиях изобилия нерелевантных атрибутов. Литтлстоун.
(Вероятностные рассуждения)
Вероятностные рассуждения в интеллектуальных системах: сети правдоподобных выводов. Жемчужина.
Максимальное правдоподобие на основе неполных данных с помощью алгоритма em. Демпстер и др.
Локальные вычисления с вероятностями на графических структурах. Лауритцен и др.
(Генетические алгоритмы)
Генетические алгоритмы в поиске, оптимизации и машинном обучении. Голдберг.
Адаптация в естественных и искусственных системах. Голландия.
Генетическое программирование: О программировании компьютеров посредством естественного отбора. Коза.
(Логика)
Эффективное создание логических программ. Магглтон и др.
Обучение логических определений на основе соотношений. Квинлан.
Методы и приложения индуктивного логического программирования. Лаврак и др.
Таблица 15.1: Документы с наивысшим рейтингом по p(c|z). Метки тем factor - это задания, сделанные вручную , основанные на сходстве с темами Cora. Воспроизведено по [63].
сообществом.
Мы используем переменную d ; {1, . . . , D} для индексации документов и c ; {1, . . . , D} для индексации цитат (и d, и c имеют один и тот же домен, а именно индекс научной статьи). Если документ d = i ссылается на статью c = j, то мы устанавливаем значение матрицы Cij = 1. Если ссылки отсутствуют, значение Cij равно нулю. Мы можем сформировать "распределение" по документам и цитатам, используя
Пример 74 (Моделирование цитат). Корпус Cora (www.cs.umass.edu/;mccallum) содержит
архив, содержащий около 30 000 научных работ в области компьютерных наук. Из этого архива авторы в [63] извлекли статьи в категории "машинное обучение", состоящие из 4220 документов и 38 372 цитат. С их помощью было сформировано уравнение распределения (15.6.22). Документы были дополнительно разделены вручную на 7 разделов: Рассуждения на основе Конкретных Случаев, Генетические Алгоритмы, Нейронные Сети, Вероятностные Методы, Обучение с Подкреплением, Обучение Правил и Теория.
В [63] совместный метод PLSA адаптирован к данным с использованием z = 7 тем. Из обученной модели следует, что выражение p(c = j|z = k) определяет, насколько авторитетной является статья j по мнению сообщества z = k. Результаты представлены в таблице(15.1) и показывают, как метод выявляет интуитивно понятные темы.
Моделирование веб-
Рассмотрим набор веб-сайтов, проиндексированных по i. Если веб-сайт j указывает на веб-сайт i, задается значение Cij = 1, что дает ориентированный график ссылок с веб-сайта на веб-сайт. Поскольку веб-сайт обычно содержит только небольшое количество
Черновик, 9 марта 2010 г. 297 Kernel \Ядро PCA
в разделе "темы" мы могли бы объяснить, почему существует связь между двумя веб-сайтами, используя декомпозицию PLSA. Эти алгоритмы оказались полезными для поиска в Интернете, например, для определения скрытой тематики веб-сайтов и выявления наиболее авторитетных веб-сайтов. Обсуждение см. в [64].
15.7 Ядро PCA
Ядро PCA является нелинейным расширением PCA, предназначенным для обнаружения нелинейных многообразий. Здесь мы лишь кратко опишем подход и отсылаем читателя к [242] для получения подробной информации. В ядре PCA мы заменяем каждый x вектором "признаков" ~x ; ;(x). Обратите внимание, что использование ~x здесь не имеет той интерпретации, которую мы использовали ранее, как приблизительную реконструкцию. Карта объектов ; использует вектор x и создает вектор ~x с большей размерностью. Например, мы могли бы отобразить двумерный вектор x = [x1 , x2 ]T с помощью
Идея состоит в том, чтобы затем выполнить PCA для этих векторов признаков более высокой размерности, затем отобразив собственные векторы в исходное пространство x. Основная задача состоит в том, чтобы записать это без явного вычисления PCA в потенциально очень многомерном пространстве векторов признаков. Напомним, что в стандарте PCA для нулевые средние данные, единица формирует собственное разложение матрицы выборки 3
Для простоты мы сосредоточимся здесь на нахождении первого главного компонента ;, который удовлетворяет
для соответствующего собственного значения ; (записываем ;` = N ;). ‘Двойственное" представление получается путем предварительного умножения на ~XT , так что в терминах ~f ; ~XT ; стандартная собственная задача PCA сводится к решению:
Затем восстанавливается собственный вектор ; объекта с использованием
Отметим, что матрица ~XT ~X содержит элементы
и распознаем это как скалярное произведение векторов. Это означает, что матрица положительна (полуопределена) и мы можем эквивалентно использовать положительно определенное ядро, см. раздел (19.3),
Тогда уравнение (15.7.4) можно записать в виде
Затем решается это собственное уравнение, чтобы найти N-мерный главный вектор двойного признака ~f . Проекция признака ~x задается через
В более общем плане, для большего числа компонентов проекция PCA i-го ядра может быть выражена в виде
3 Мы используем нормализацию N в отличие от N ; 1 просто для удобства записи – на практике разница невелика.
ПРОЕКТ от 9 марта 2010г. 298 Данные для обучения PCA
тренировочные данные
истинная модель
обученная модель
Рисунок 15.16: Канонический корреляционный анализ. (а): Обучающие данные. Верхняя панель содержит X-матрицу из 1000 15-мерных точек, а внизу - соответствующая 30-мерная Y-матрица. (b): Данные в (a) были получены с использованием X = Ah, Y = Bh, где A - матрица 15 ; 1, а B - матрица 30 ; 1. (c): Матрицы A и B были получены с помощью CCA. Обратите внимание, что они близки к истинным A и B вплоть до изменения масштаба и знака. Смотрите demoCCA.m.
, где i - метка собственного значения.
Приведенный выше вывод неявно предполагает нулевое среднее значение признаков ~x. Даже если исходные данные x имеют нулевое среднее значение, из-за нелинейного отображения объекты могут не иметь нулевого среднего значения. Чтобы исправить это, можно показать, что единственное требуемое изменение - заменить матрицу K в приведенном выше уравнении (15.7.8) на
Поиск реконструкций
Выше приведена процедура для нахождения проекции KPCA y. Однако во многих случаях мы также хотели бы получить приблизительную реконструкцию, используя меньшую размерность y. Это не так просто, поскольку отображение от y к x, как правило, сильно нелинейно. Здесь мы описываем процедуру достижения этой цели.
Сначала мы находим реконструкцию ~x; пространства признаков ~x. Сейчас
Учитывая ~x;, мы пытаемся найти ту точку x` в исходном пространстве данных, которая соответствует ~x; . Это можно найти путем минимизации
С точностью до пренебрежимо малых величин это
Так затем вычисляется x` путем минимизации E(x` ) численно.
ПРОЕКТ от 9 марта 2010 г. 299 канонический корреляционный анализ
15.8 Канонический Корреляционный Анализ
Рассмотрим x и y, которые имеют размеры dim (x) и dim (y) соответственно. Например, x может представлять собой фрагмент видео, а y - соответствующий звук. При наличии коллекции (xn , yn ) , n = 1, . . . , N интересная задача состоит в том, чтобы определить, какие части аудио- и видеофайлов сильно коррелируют. Можно было бы ожидать, например, что область рта в видео сильно коррелирует со звуком.
Один из способов добиться этого - спроецировать все x и y в одно измерение, используя aT x и bT y таким образом, чтобы корреляция между проекциями была максимальна. Ненормализованная корреляция между проекциями aT x и bT y равна
, а нормализованная корреляция равна
где Sxy - выборочная матрица взаимной корреляции x, y. Когда учитывается совместная ковариация сложенных векторов zn = [xn , yn ], Sxx , Sxy , Syx , Syy являются блоками совместной ковариационной матрицы.
Поскольку уравнение (15.8.2) инвариантно относительно масштабирования длины a, а также b, мы можем рассмотреть эквивалентную задачу
при условии, что aT Sxx a = 1 и bT Syy b = 1. Чтобы найти оптимальные проекции a, b с учетом ограничений, мы используем Лагранжиан,
из которого мы получаем критерий нулевой производной
Следовательно
Поскольку при aT Sxx b = 1 и bT Syy a мы должны иметь ;a = ;b = ; в оптимальном состоянии. Если предположить, что Syy обратимо, то
Используя это для исключения b из уравнения (15.8.5), мы имеем
что является обобщенной собственной задачей. Предполагая, что Sxx обратимо, мы можем эквивалентно записать
что является стандартной собственной задачей (хотя и с ;2 в качестве собственного значения). Как только это будет решено, мы сможем найти b, используя уравнение (15.8.7).
300 ЧЕРНОВИК от 9 марта 2010 года Упражнения
15.8.1 Рецептура \формулировка SVD
Несложно показать, что мы можем найти a, сначала вычислив SVD из
в виде UDVT и извлекаем максимальный сингулярный вектор u1 из U (первый столбец в U). Затем получаем a- это оптимально Sxx -1/2 u1 , и аналогично, b - это оптимально Syy -1/2 v1 , где v1 - это первый столбец V. Таким образом, расширение для нахождения M множественных направлений A = [a1 , . . . , aM] и B = [b1 , . . . , bM ] понятно – нужно взять соответствующие первые M сингулярных значений соответственно. Это максимизирует критерий
Этот подход используется в cca.m – смотрите иллюстрацию (15.16) для демонстрации. Можно также показать, что CCA соответствует модели вероятностного Факторного Анализа при блочном ограничении на форму факторных нагрузок, см. раздел (21.2.1).
CCA и связанные с ним расширения ядра были применены в контексте машинного обучения, например, для моделирования корреляции между изображениями и текстом, чтобы улучшить поиск изображений из текстовых запросов, см. [126].
15.9 Записи \Заметки
PCA также известен как разложение Кархунена-Лева, особенно в инженерной литературе.
15.10 Код
pca.m: Анализ Основных Компонентов
demoLSI.m: Демонстрация Скрытой Семантической Индексации/Анализа
svdm.m: Разложение по Сингулярным Значениям с недостающими данными
demoSVDmissing.m: Демонстрация SVD с недостающими данными
plsa.m: Вероятностный Скрытый Семантический Анализ
plsaCond.m: Условно-Вероятностный Латентный Семантический Анализ
demoPLSA.m: Демонстрация PLSA
demoMultnomialPXYGZ.m: Демонстрация "конечной выборки’ PLSA
cca.m: Канонический Корреляционный Анализ (CCA)
demoCCA.m: Демонстрация Канонического Корреляционного Анализа
15.11 Упражнения
Упражнение 161. Рассмотрим набор данных в двух измерениях, где данные расположены на окружности единичного радиуса. Каков будет эффект от использования PCA для этого набора данных, в котором мы пытаемся уменьшить размерность до 1? Предложите альтернативное одномерное представление данных.
Упражнение 162. Рассмотрим два вектора xa и xb и соответствующие им аппроксимации PCA c+ Mi=1 ai ePM и c + i=1 bi ei , где собственные векторы ei , i = 1, . . . , M взаимно ортогональны и имеют единичную длину. Собственный вектор ei имеет соответствующее собственное значение ;i . Приблизьте значение (xa ; xb )2, используя представления данных в формате PCA, и покажите, что оно равно (a - b)2 .
Упражнение 163. Покажите, как решение для a задачи CCA в уравнении (15.8.8) может быть преобразовано в форму, выраженную уравнением (15.8.10), как указано в тексте.
ЧЕРНОВИК от 9 марта 2010 г. 301 Упражнения
Упражнение 164. Пусть S - ковариационная матрица данных. Расстояние Махаланобиса между xa и xb определяется как
Объясните, как приблизительно рассчитать это расстояние, используя M-мерные аппроксимации PCA.
Упражнение 165 (PCA с внешними входными данными). В некоторых приложениях можно заподозрить, что определенные внешние переменные v оказывают сильное влияние на то, как распределяются данные x. Например, если x представляет изображение, возможно, мы знаем условия освещения v, при которых было сделано изображение, – это будет иметь большое значение, эффект на изображение. Поэтому было бы целесообразно учитывать известные условия освещения при формировании представления изображения в меньших размерах. Обратите внимание, что мы не хотим формировать представление с меньшим размером соединения x, v, скорее, мы хотим сформировать представление с меньшим размером только для x, учитывая, что некоторая наблюдаемая изменчивость может быть связана с v.
Поэтому мы предполагаем приближение
, где должны быть определены коэффициенты yin , i = 1, . . . , N , n = 1, . . . , N и базисные векторы bj , j = 1, . . . , J и ck , k =1, . . . , K. Даны внешние входные данные v1 , . . . , vN. Сумма квадратов потерь при ошибке между xn и их уравнением линейной реконструкции (15.11.2) равна
Найдите параметры, которые минимизируют значение E.
Упражнение 166. Рассмотрим следующие трехмерные точки данных:
(1.3, 1.6, 2.8)(4.3, ;1.4, 5.8)(;0.6, 3.7, 0.7)(;0.4, 3.2, 5.8)(3.3, ;0.4, 4.3)(;0.4, 3.1, 0.9)
(15.11.4)
Выполните Анализ Главных Компонент с помощью:
1. Вычислите среднее значение c для данных.
2. Вычислите ковариационную матрицу S = 1/6;6n=1 xn (xn )T ; ccT данных.
3. Нахождение собственных значений и векторов ei ковариационной матрицы.
Вы должны обнаружить, что только два собственных значения являются большими, и, следовательно, данные могут быть хорошо представлены с использованием только двух компонентов. Пусть e1 и e2 - два собственных вектора с наибольшими собственными значениями.
1. Вычислите двумерное представление каждой точки данных (e1 ·(xn ;c), e2 ·(xn ;c)), n = 1, . . . , 6.
2. Вычислите реконструкцию каждой точки данных c + (e1T (xn ; c))e1 + (e2T (xn ; c))e2 , n = 1, . . . , 6.
Упражнение 167. Рассмотрим "условную частотную матрицу’
p(x = i|y = j) (15.11.5)
Покажите, как вывести алгоритм в стиле EM для приближенного разложения этой матрицы в виде
, где k = 1, . . . , Z, i = 1, . . . , X, j = 1, . . . , Y .
Упражнение 168. Для многочленной модели ~p(x, y, z), описанной в уравнении (15.6.15), выведите в явном виде Разработайте алгоритм и реализуйте его в среде MATLAB. Для получения случайно выбранных значений условных вероятностей извлеките 10000 выборок из этой модели для X = 5, Y = 5, Z = 4 и вычислите по ним матрицу с элементами
Теперь запустите PLSA (используйте plsa.m) с настройками X = 5, Y = 5, Z = 4, чтобы изучить и сравнить свои результаты с результатами, полученными из уравнения модели с конечной выборкой (15.6.15).
302 ЧЕРНОВИК от 9 марта 2010 года Главa 16
Главa 16
Контролируемое Уменьшение Линейных Размеров
16.1 Контролируемые Линейные Проекции
В главе (15) мы обсуждали уменьшение размерности с использованием процедуры, не требующей контроля. В тех случаях, когда информация о классе доступна, и наша конечная цель - уменьшить размерность для улучшения классификации, имеет смысл использовать доступную информацию о классе при формировании прогнозов. Использование информации о метке класса для улучшения проекции является одной из форм контролируемого уменьшения размера. Давайте рассмотрим данные из двух разных классов. Для класса 1 у нас есть набор данных, содержащий N1 точек данных,
и аналогично для класса 2, у нас есть набор из N2 точек данных
Тогда наш интерес состоит в том, чтобы найти линейную проекцию,
где dim W = D ;L, L < D, так что для точек данных xi , xj одного класса расстояние между их проекциями yi , yj должно быть небольшим. И наоборот, для точек данных, относящихся к разным классам, расстояние между их проекциями должно быть большим. Это может быть полезно для целей классификации, поскольку для новой точки x;, если ее проекция
близок к прогнозируемым данным класса 1, мы ожидаем, что x; будет принадлежать классу 1. При формировании контролируемого проецирования сохраняются только те части данных, которые различают классы, так что процедуру можно рассматривать как форму контролируемого извлечения признаков.
16.2 Линейный дискриминант Фишера
Мы ограничим внимание данными бинарного класса. Также, для простоты, мы проецируем данные в одно измерение. Алгоритм канонических вариаций, описанный в разделе (16.3), имеет дело с обобщениями.
Допущение Гаусса
Мы моделируем данные из каждого класса с помощью Гауссовой модели. То есть
303 Линейный дискриминант Фишера
Рисунок 16.1: Большие крестики представляют данные из класса 1, а большие кружки - из класса 2. Их проекции на измерение 1 представлены их маленькими аналогами. (а): Линейный дискриминант Фишера. Анализ. Здесь в прогнозах наблюдается небольшое совпадение классов. (b): Неконтролируемое уменьшение размеров с использованием Анализа Главных Компонент для сравнения. В проекте наблюдается значительное совпадение классов. Как в (а), так и в (b) одномерная проекция представляет собой расстояние вдоль линии, измеренное от произвольно выбранной фиксированной точки на линии.
где m1 - выборочное среднее значение данных класса 1, а S1 - выборочная ковариация; аналогично для класса 2. Проекции точек из двух классов затем задаются как
Поскольку проекции являются линейными, прогнозируемые распределения также являются Гауссовыми,
Мы ищем проекцию w такую, чтобы прогнозируемые распределения имели минимальное перекрытие. Это может быть достигается, если прогнозируемые средние значения по Гауссу максимально разделены, (µ1 ; µ2 )2 велико. Однако, если дисперсии ;12 , ;22 также велики, в классах все еще может наблюдаться значительное перекрытие. Поэтому полезной целевой функцией является
где ;i представляет собой долю набора данных в классе i. В терминах проекции w объективное уравнение (16.2.5) имеет вид
где
Оптимальное значение w можно найти, дифференцируя уравнение (16.2.6) относительно w. Это дает значение
, и, следовательно, требование к нулевой производной равно
304 ЧЕРНОВИК от 9 марта 2010 г. Канонические изменения
Умножая на величину, обратную B, получаем
Это означает, что оптимальная проекция явно задается формулой
Хотя коэффициент пропорциональности зависит от w, мы можем считать его постоянным, поскольку целевая функция F (w) уравнения (16.2.6) инвариантна к изменению масштаба w. Поэтому мы можем принять
Обычно масштабирование w изменяют, чтобы получить единичную длину, wT w = 1, так что
Иллюстрация этого метода приведена на рис. 16.1, где показано, как контролируемый размер уменьшает- это может привести к получению представлений с меньшей размерностью, более подходящих для последующей классификации, чем неконтролируемый метод, такой как PCA.
К уравнению (16.2.12) можно также прийти, исходя из другой исходной цели. Рассматривая проекцию как регрессионную задачу y = wT x+b, в которой выходные данные y определены как y1 и y2 для классов 1 и 2 соответственно, можно показать, что для надлежащим образом выбранных y1 и y2 решение с использованием критерия наименьших квадратов задается уравнением (16.2.12). [83, 42]. Это также указывает на способ упорядочения LDA, см. упражнение (171). Возможны расширения ядра LDA, см., например, [78, 248].
Когда наивный метод не работает
Приведенный выше вывод основан на существовании обратной функции B. Однако на практике значение B может быть необратимым, и описанная выше процедура требует модификации. Случай, когда B не является обратимым, - это когда точек данных N1 + N2 меньше, чем измерений D. Другой случай - когда есть элементы входных векторов, которые никогда не меняются. Например, в случае с цифрами, написанными от руки, пиксели на краях углов равны фактически всегда равен нулю. Назовем этот угловой пиксель z. Тогда в матрице B будет нулевая запись для [B]z,z (на самом деле вся z-я строка и столбец будут равны нулю), так что для любого вектора
Это показывает, что знаменатель цели Фишера может стать равным нулю, а сама цель плохо определена. Мы рассмотрим эти вопросы в разделе (16.3.1).
16.3 Канонические Переменные
Метод Канонических Переменных обобщает метод Фишера на проекции более чем в одном измерении и более чем в двух классах. Проекция любой точки задается через
где W - матрица D ; L. Предполагая, что данные x из класса c распределены по Гауссу,
, проекции y также являются Гауссовыми
Для расширения более чем на два класса мы определяем следующие матрицы:
ПРОЕКТ от 9 марта 2010 г. 305 Канонические переменные
Между Разбросами по классам Найдем m, среднее значение для всего набора данных, и mc, среднее значение для каждого класса c. Формула
где Nc - количество точек данных в классе c, c = 1, . . . , C.
В пределах Разброса классов для каждого класса c формируют ковариационную матрицу Sc и среднее значение mc. Определим
Это, естественно, приводит к определению коэффициента Роли
след
Предполагая, что B обратимо (в противном случае смотрите раздел (16.3.1)), мы можем определить коэффициент Холецкого ~B с помощью
Тогда, определяя
, цель может быть записана в виде ~W:
Если мы примем ограничение ортонормированности для ~W, то мы эквивалентно потребуем максимизации
F (W) - трассировка WT CW , при условии, что WT W = I
, где
Поскольку C симметричен и положительно полуопределен, он имеет действительное собственное разложение
где ; = diag (;1 , ;2 , ... , ;D ) - диагональ с неотрицательными элементами, содержащими собственные значения, отсортированные в порядке убывания, ;1 ; ;2 ; ... и ET E = I. Следовательно
При задании ~W = [e1 , ... , eL ], где el - l-й собственный вектор, цель становится суммой первых L собственных значений. Эта настройка максимизирует целевую функцию, поскольку формирование ~W из любых других столбцов E дало бы меньшую сумму. Затем мы возвращаем
в качестве матрицы проекции. Процедура описана в алгоритме (17). Обратите внимание, что, поскольку A имеет ранг C, ненулевых собственных значений и соответствующих направлений может быть не более C ; 1.
306 ЧЕРНОВИК от 9 марта 2010 г. Канонические изменения
Алгоритм 17 канонических вариаций
1: Вычислите матрицы рассеяния A между классами и внутри них, уравнение (16.3.4) и B, уравнение (16.3.5).
2: Вычислите коэффициент Холецкого ~B из B.
3: Вычислите L главных собственных векторов [e1 , . . . , eL ] из B;T AB;1 .
4: W = [e1 , . . . , eL ]
5: Верните W = B;1w в качестве матрицы проекции.
16.3.1 Работа с нулевым пространством
Приведенный выше вывод канонических переменных (а также LDA Фишера) требует обратимости матрицы B. Однако, как мы обсуждали в разделе (16.2), могут возникнуть ситуации, когда B не является обратимой. Решение состоит в том, чтобы требовать, чтобы W находилось только в подпространстве, охватываемом данными (то есть не может быть вклад из нулевого пространства). Для этого мы сначала объединяем обучающие данные из всех классов в одну большую матрицу X. Базис для X можно найти, используя, например, метод thin-SVD \тонкий-, который возвращает ортонормированный базис Q. Затем мы требуем, чтобы решение W было выражено в этом базисе:
для некоторой матрицы W` . Подставляя ее в каноническое уравнение с переменной целью (16.3.6), получим
Это имеет ту же форму, что и стандартное частное, уравнение (16.3.6), при замене промежуточного рассеяния A при
и внутренний рассеиватель B при
В этом случае B` гарантированно обратим, и можно выполнять канонические изменения, как в разделе(16.3) выше. Это вернет матрицу W`. Затем мы возвращаем
Смотрите также CanonVar.m.
Пример 75 (С использованием канонических переменных для цифровые данных ). Мы применяем канонические вариации, чтобы спроецировать цифровые данные на два измерения, см. рис. 16.3. Имеется 800 примеров для трех, 800 примеров для пяти и 800 примеров для семи. Таким образом, в целом имеется 2400 примеров, расположенных в пространстве размером 784 (28 ; 28 пикселей). Обратите внимание, что проецируемые данные канонические вариации на два измерения имеют очень небольшое перекрытие по классам, см. рис. 16.3а). Для сравнения, проекции, сформированные на основе PCA, в которых информация о классе отбрасывается, показывают высокую степень перекрытия классов. Различные масштабы канонических вариаций и прогнозов PCA
Рисунок 16.2: Каждая трехмерная точка данных лежит в двумерной плоскости, что означает, что матрица B не имеет полного ранга и, следовательно, не обратима. Решение дается путем нахождения векторов q1, q2, которые охватывают плоскость и выражают решение канонических вариаций в членах только от этих векторов.
ПРОЕКТ от 9 марта 2010 г. 307 Упражнения
Рисунок 16.3: (а): Проекция канонических вариаций для примеров рукописных цифр 3(‘+’), 5(‘о’) и 7(ромб). Имеется по 800 примеров из каждого класса цифр. Показаны проекции в двух измерениях. (b): проекции PCA для сравнения.
это связано с различными ограничениями на матрицы проекций W. В PCA W является унитарным; в каноническом изменяет значение WT BW = I, что означает, что значение W будет масштабироваться с использованием обратного квадратного корня из наибольших собственных значений матрицы рассеяния внутри класса. Поскольку цель канонического изменения не зависит от линейного масштабирования, при желании W можно масштабировать с помощью произвольного скалярного префактора ;W.
16.4 Использование неГауссовских Распределений Данных
Применимость канонических переменных зависит от нашего предположения, что гауссово распределение является хорошим описанием данных. Очевидно, что если данные являются мультимодальными, то для моделирования данных в каждом классе используется один Гауссиан, что неверное предположение. Это может привести к получению прогнозов с большим совпадением\перекрытием классов. В принципе, нет концептуальных трудностей в использовании более сложных распределений, скажем, с более общими критериями, такими как расхождение по Куллбэк-Лейблеру между прогнозируемыми распределениями, используемыми в качестве цели. Однако такие критерии обычно приводят к сложным задачам оптимизации. Метод канонических вариаций популярен благодаря своей простоте и отсутствию проблем с локальными оптимумами при построении проекции.
16.5 Код
CanonVar.m: Канонические варианты
demoCanonVarDigits.m: Демонстрация для канонических вариантов
16.6 Упражнения
Упражнение 169. Что произойдет с линейным дискриминантом Фишера, если точек данных будет меньше, чем измерений?
Упражнение 170. Измените demoCanonVarDigits.m, чтобы спроецировать и визуализировать численные данные в трех измерениях.
Упражнение 171. Рассмотрим N1 точек данных класса 1 xn1 , n1 = 1, . . . , N1 и точки данных класса 2 xn2 , n2 = 1, . . . , N2 . Мы построим линейный предиктор для этих данных,
308 ПРОЕКТ от 9 марта 2010 г. Упражнения
с целью прогнозирования значения y1 для данных из класса 1 и y2 для данных из класса 2. Степень соответствия определяется как
Покажите, что при задании y1 = (N1 + N2 ) /N1 и y2 = (N1 + N2 ) /N2 значение w, которое минимизирует значение E, соответствующее решению LDA Фишера. Подсказка: сначала покажите, что два условия нулевой производной равны
и
, которое можно свести к одному уравнению
где B соответствует определению для LDA в тексте, уравнение (16.2.7).
Обратите внимание, что это указывает на способ упорядочения LDA, а именно путем добавления члена ;wTw к E(w, b|y1 , y2). Это может быть учтено при переопределении уравнения (16.3.5) в виде
B ` = B + ;I (16.6.6)
Другими словами, можно увеличить ковариацию B на дополнительную величину ;I. Оптимальная регуляризация константа ; может быть установлена путем перекрестной проверки. В более общем плане можно рассмотреть возможность использования регуляризующей матрицы ;R, где R - положительно определенное значение.
Упражнение 172. Рассмотрим цифровые данные из 892 пятизначных цифр digit5.mat и 1028 семизначных цифр digit7.mat. Составьте обучающий набор, состоящий из первых 500 примеров из каждого класса цифр. Используйте канонические переменные, чтобы сначала спроецировать данные на 50 измерений и вычислить показатели ближайших соседей по оставшимся цифрам. Сравните точность классификации с использованием прогнозов ближайших соседей по PCA, используя 50 компонентов.
Упражнение 173. Рассмотрим целевую функцию вида
где A(w) и B(w) - положительные функции, и наша задача состоит в том, чтобы максимизировать F (w) относительно w. Возможно, эта задача не имеет простого алгебраического решения, хотя A(w) и B (w) являются простыми функциями.
Мы можем рассмотреть альтернативную цель, а именно
J(w, ;) = A(w) ; ;B(w) (16.6.8)
где ; - постоянный скаляр. Произвольно выберите начальную точку wold и задайте
;old ; A(wold )/B(wold ) (16.6.9)
В этом случае J(wold , ;old ) = 0. Теперь выберем w таким образом, чтобы
J(w, ;old) = A(w) ; ;old B(w) ; 0 (16.6.10)
Это, безусловно, возможно, поскольку J(wold , ;old ) = 0. Если мы сможем найти w таким образом, чтобы J(w, ;old ) > 0, то
A(w) ; ;old B(w) > 0 (16.6.11)
Покажите, что для такого w, F (w) > F (wold), и предложите итеративную процедуру оптимизации для целевых функций вида F (w).
ПРОЕКТ от 9 марта 2010 г. 309 упражнений
310
ЧЕРНОВИК главы от 9 марта 2010 года
13-16Байесовские рассуждения смыслы и машинное обу
© Copyright: Джон Темплтон, 2025
Свидетельство о публикации №125110906780
Свидетельство о публикации №125110906780
Рецензии