Урок 1 Знакомство с машинным обучением
 Скачать 1.57 Mb.
|
|
4.1.7. Вероятностный смысл квантильной ошибки Чтобы разобраться, почему такая функция потерь называется квантильной, нужно разобраться с ее вероят- ностным смыслом. Пусть один и тот же объект x с одним и тем же признаковым описанием повторяется в выборке n раз, но на каждом из повторов — свой ответ y 1 , ..., y n Такое может возникнуть при измерении роста человека. Измерения роста одного и того же человека могут отличаться ввиду ошибки прибора, а также зависеть от самого человека (может сгорбиться или выпрямиться). При этом алгоритм должен для одного и того же признакового описания возвращать одинаковый прогноз. Другими словами, необходимо решить, какой прогноз оптимален для x с точки зрения различных функцио- налов ошибки. Оказывается, что если используется квадратичный функционал ошибки, то наиболее оптимальным про- гнозом будет средний ответ на объектах, если абсолютный, то медиана ответов. Если же будет использоваться квантильная функция потерь, наиболее оптимальным прогнозом, будет τ-квантиль. В этом и состоит веро- ятностный смысл квантильной ошибки. 2 4.2. Метрика качества классификации В этом блоке речь пойдет о том, как измерять качество в задачах классификации. 4.2.1. Доля правильных ответов Как меру качества в задачах классификации естественно использовать долю неправильных ответов: 1 ` ` X i=1 [a(x i ) 6= y i ] Однако в задачах классификации принято выбирать метрики таким образом, чтобы их нужно было максими- зировать, тогда как в задачах регрессии — так, чтобы их нужно было минимизировать. Поэтому определяют: accuracy(a, X) = 1 ` ` X i=1 [a(x i ) = y i ] . Эта метрика качества проста и широко используется, однако имеет несколько существенных недостатков. 4.2.2. Несбалансированные выборки Первая проблема связана с несбалансированными выборками. Показателен следующий пример. Пусть в вы- борке 1000 объектов, из которых 950 относятся к классу −1 и 50 — к классу +1. Рассматривается бесполезный (поскольку не восстанавливает никаких закономерностей в данных) константный классификатор, который на всех объектах возвращает ответ −1. Но доля правильных ответов на этих данных будет равна 0.95, что несколько много для бесполезного классификатора. Чтобы «бороться» с этой проблемой, используется следующий факт. Пусть q 0 — доля объектов самого крупного класса, тогда доля правильных ответов для разумных алгоритмов accuracy ∈ [q 0 , 1] , а не [1/2, 1], как это можно было бы ожидать. Поэтому, если получается высокий процент правильных ответов, это может быть связано не с тем, что построен хороший классификатор, а с тем, что какого-то класса сильно больше, чем остальных. 4.2.3. Цены ошибок Вторая проблема с долей верных ответов состоит в том, что она никак не учитывает разные цены разных типов ошибок. Тогда как цены действительно могут быть разными. Например, в задаче кредитного скоринга, то есть в задаче принятия решения относительно выдачи кре- дита, сравниваются две модели. При использовании первой модели кредит будет выдан 100 клиентам, 80 из которых его вернут. Во второй модели, более консервативной, кредит был выдан только 50 клиентам, причем вернули его в 48 случаях. То, какая из двух моделей лучше, зависит от того, цена какой из ошибок выше: не дать кредит клиенту, который мог бы его вернуть, или выдать кредит клиенту, который его не вернет. Таким образом, нужны дополнительные метрики качества, которые учитывают цены той или иной ошибки. 4.3. Точность и полнота 4.3.1. Цены ошибок В этом разделе пойдет речь о метриках качества классификации, которые позволяют учитывать разные це- ны ошибок. В конце предыдущего разделе уже было сказано, что цены ошибок действительно могут быть разными. Так, в задаче банковского скоринга необходимо принять решение, что хуже: выдать кредит «плохо- му» клиенту или не выдать кредит «хорошему» клиенту. Доля верных ответов не способна учитывать цены разных ошибок и поэтому не может дать ответа на этот вопрос. 3 4.3.2. Матрица ошибок Удобно классифицировать различные случаи, как соотносятся между собой результат работы алгоритма и истинный ответ, с помощью так называемой матрицы ошибок. y = 1 y = −1 a(x) = 1 True Positive (TP) False Positive (FP) a(x) = −1 False Negative (FN) True Negative (TN) Когда алгоритм относит объект к классу +1, говорят, что алгоритм срабатывает. Если алгоритм сработал и объект действительно относится к классу +1, имеет место верное срабатывание (true positive), а если объект на самом деле относится к классу −1, имеет место ложное срабатывание (false positive). Если алгоритм дает ответ −1, говорят, что он пропускает объект. Если имеет место пропуск объекта класса +1, то это ложный пропуск (false negative). Если же алгоритм пропускает объект класса −1, имеет место истинный пропуск (true negative). Таким образом, существуют два вида ошибок: ложные срабатывания и ложные пропуски. Для каждого из них нужна своя метрика качества, чтобы измерить, какое количество ошибок какого типа совершается. 4.3.3. Точность и полнота Пусть для примера рассматриваются две модели a 1 (x) и a 2 (x) . Выборка состоит из 200 объектов, из которых 100 относятся к классу 1 и 100 — к классу −1. Матрицы ошибок имеют вид: y = 1 y = −1 a 1 (x) = 1 80 20 a 1 (x) = −1 20 80 y = 1 y = −1 a 2 (x) = 1 48 2 a 2 (x) = −1 52 98 Введем две метрики. Первая метрика, точность (precision), показывает, насколько можно доверять клас- сификатору в случае срабатывания: precision(a, X) = T P T P + F P Вторая метрика, полнота (recall), показывает, на какой доле истинных объектов первого класса алгоритм срабатывает: recall(a, X) = T P T P + F N В примере выше точность и полнота первого алгоритма оказываются равными: precision(a 1 , X) = 0.8, precision(a 2 , X) = 0.96 recall(a 1 , X) = 0.8, recall(a 2 , X) = 0.48 Вторая модель является очень точной, но в ущерб полноте. 4.3.4. Примеры использования точности и полноты Первый пример — использование в задаче кредитного скоринга. Пусть в задаче кредитного скоринга ставит- ся условие, что неудачных кредитов должно быть не больше 5%. В таком случае задача является задачей максимизации полноты при условии precision(a, X) ≥ 0.95. Второй пример — использование в медицинской диагностике. Необходимо построить модель, которая опре- деляет, есть или нет определенное заболевание у пациента. При этом требуется, чтобы были выявлены как минимум 80% пациентов, которые действительно имеют данное заболевание. Тогда ставят задачу максими- зации точности при условии recall(a, X) ≥ 0.8. Следует особо обратить внимание на то, как точность и полнота работают в случае несбалансированных выборок. Пусть рассматривается выборка со следующей матрицей ошибок: y = 1 y = −1 a(x) = 1 10 20 a(x) = −1 90 10000 4 Доля верных ответов (accuracy), точность(precision) и полнота(recall) для данного случая: accuracy(a, X) = 0.99, precision(a, X) = 0.33, recall(a, X) = 0.1. То, что доля верных ответов равняется 0.99, ни о чем не говорит: алгоритм все равно делает 66% ложных срабатываний и выявляет только 10% положительных случаев. Благодаря введению точности и полноты становится понятно, что алгоритм нужно улучшать. 4.4. Объединение точности и полноты В этом разделе пойдет речь о том, как соединить точность и полноту в одну метрику качества классификации. 4.4.1. Точность и полнота (напоминание) Точность показывает, насколько можно доверять классификатору в случае срабатывания: precision(a, X) = T P T P + F P Полнота показывает, на какой доле истинных объектов первого класса алгоритм срабатывает: recall(a, X) = T P T P + F N В некоторых задачах есть ограничения на одну из этих метрик, тогда как по второй метрике будет произво- диться оптимизация. Но в некоторых случаях хочется максимизировать и точность, и полноту одновременно. Встает вопрос об объединении этих двух метрик. 4.4.2. Арифметическое среднее Единая метрика может быть получена как арифметическое среднее точности и полноты: A = 1 2 (precision + recall) Пусть есть алгоритм, точность которого равна 10%, а полнота — 100%: precision = 0.1 recall = 1. Это может быть случай, когда в выборке всего 10% объектов класса +1, а алгоритм является константным и всегда возвращает +1. Очевидно, что этот алгоритм плохой, но введенная выше метрика для него равна A = 0.55 . В свою очередь другой, гораздо более лучший алгоритм, с precision = 0.55 и recall = 55 также характеризуется A = 0.55. Ситуация, когда константный и разумный алгоритмы могут лежать на одной линии, является недопусти- мой, поэтому следует искать другой способ построения единой метрики. 5 recall precision 0.0 0.0 0.2 0.2 0.4 0.4 0.6 0.6 0.8 0.8 1 1 Рис. 4.2: Линии A = 1 2 (precision + recall) = const в координатах precision–recall 4.4.3. Минимум Чтобы констрантный и разумный алгоритмы не лежали на одной линии уровня, можно рассматривать: M = min(precision, recall). Данный подход решает вышеупомянутую проблему, например: precision = 0.05, recall = 1 =⇒ M = 0.05. Но есть другой нюанс: два алгоритма, для которых точности одинаковы, но отличаются значения полноты, будут лежать на одной линии уровня M: precision = 0.4, recall = 0.5 =⇒ M = 0.4, precision = 0.4, recall = 0.9 =⇒ M = 0.4. Такое тоже недопустимо, так как второй алгоритм существенно лучше первого. recall precision 0.0 0.0 0.2 0.2 0.4 0.4 0.6 0.6 0.8 0.8 1 1 Рис. 4.3: Линии M = min(precision, recall) = const в координатах precision–recall 6 4.4.4. F-мера «Сгладить» минимум можно с помощью гармонического среднего, или F -меры: F = 2 · precision · recall precision + recall Для двух упомянутых выше алгоритма значения F -меры, в отличие от M, будут отличаться: precision = 0.4, recall = 0.5 =⇒ F = 0.44, precision = 0.4, recall = 0.9 =⇒ F = 0.55. Если необходимо отдать предпочтение точности или полноте, следует использовать расширенную F -меру, в которой есть параметр β: F = (1 + β 2 ) precision · recall β 2 · precision + recall Например, при β = 0.5 важнее оказывается полнота, а в случае β = 2, наоборот, важнее оказывается точность. recall precision 0.0 0.0 0.2 0.2 0.4 0.4 0.6 0.6 0.8 0.8 1 1 recall precision 0.0 0.0 0.2 0.2 0.4 0.4 0.6 0.6 0.8 0.8 1 1 recall precision 0.0 0.0 0.2 0.2 0.4 0.4 0.6 0.6 0.8 0.8 1 1 Рис. 4.4: Линии F = const в координатах precision–recall при значениях β = 1, β = 0.5 и β = 2 соответственно 4.5. Качество оценок принадлежности классу 4.5.1. Оценка принадлежности Многие алгоритмы бинарной классификации устроены следующим образом: сначала вычисляется некоторое вещественное число b(x), которое сравнивается с порогом t. a(x) = [b(x) > t], где b(x) — оценка принадлежности классу +1. Другими словами, b(x) выступает в роли некоторой оценки уверенности, что x принадлежит классу +1. В случае линейного классификатора a(x) = [hw, xi > t] оценка принадлежности классу +1 имеет вид b(x) = hw, xi Часто бывает необходимо оценить качество именно оценки принадлежности, а порог выбирается позже из соображений на точность или полноту. 4.5.2. Оценка принадлежности в задаче кредитного скоринга Пусть рассматривается задачного кредитного скоринга и была построена некоторая функция b(x), которая оценивает вероятность возврата кредита клиентом x. Далее классификатор строится следующим образом: a(x) = [b(x) > 0.5] При этом получилось, что точность (precision) равна 10%, а полнота (recall) — 70%. Это очень плохой алго- ритм, так как 90% клиентов, которым будет выдан кредит, не вернут его. При этом не понятно, в чем дело: был плохо выбран порог или алгоритм не подходит для решения данной задачи. Именно для этого необходимо измерять качество самих оценок b(x). 7 4.5.3. PR-кривая Первый способ оценки принадлежности классу основан на использовании кривой точности-полноты. По оси X откладывается полнота, а по оси Y — точность. Каждой точке на этой кривой будет соответствовать классификатор с некоторым значением порога. precision recall 0.0 0.0 0.2 0.2 0.4 0.4 0.6 0.6 0.8 0.8 1 1 Рис. 4.5: Кривая полноты–точности Для примера будет приведено построение PR-кривой для выборки из 6 объектов, три из которых относятся к классу 1 и 3 — к классу 0. Соответствующий ей график изображен выше. b(x) 0.14 0.23 0.39 0.54 0.73 0.90 y 0 1 0 0 1 1 1. При достаточно большом пороге ни один объект не будет отнесен к классу 1. В этом случае и точность и полнота равны 0. 2. При таком пороге, что ровно один объект отнесен к классу 1, точность будет 100% (поскольку этот объект действительно из 1 класса), а полнота — 1/3 (поскольку всего 3 объекта 1 класса). 3. При дальнейшем уменьшении порога уже два объекта отнесены к классу 1, точность также остается 100 %, а полнота становится равной 2/3. 4. При таком пороге, что уже три объекта будут отнесены к классу 1, точность становится равной 2/3, а полнота остается такой же. 5. При таком пороге, что четыре объекта отнесены к классу 1, точность уменьшится до 0.5, а полнота опять не изменится. 6. При дальнейшем уменьшении порога уже 5 объектов будут отнесены к 1 классу, полнота станет равной 100 %, а точность — 3/5. В реальных задачах с числом объектов порядка нескольких тысяч или десятков тысяч, кривая точности- полноты выглядит примерно следующим образом. 8 Рис. 4.6: Кривая точности-полноты в реальных задачах с десятками тысяч объектов Следует отметить, что начинается PR-кривая всегда из точки (0, 0), а заканчивается точной (1, r), где r — доля объектов класса 1. В случае идеального классификатора, то есть если существует такой порог, что и точность, и полнота рав- ны 100%, кривая будет проходить через точку (1, 1). Таким образом, чем ближе кривая пройдет к этой точке, тем лучше оценки. Площадь под этой кривой может быть хорошей мерой качества оценок принадлежности к классу 1. Такая метрика называется AUC–PRC, или площадь под PR-кривой. 4.5.4. ROC-кривая Второй способ измерить качество оценок принадлежности к классу 1 — ROC-кривая, которая строится в осях False Positive Rate (ось X) и True Positive Rate (ось Y ): F P R = F P F P + T N , T P R = T P T P + F N ROC-кривая строится аналогично PR-кривой: постепенно рассматриваются случаи различных значений по- рогов и отмечаются точки на графике. Для упомянутой выше выборки ROC-кривая имеет следующий вид: TPR FPR 0.0 0.0 0.2 0.2 0.4 0.4 0.6 0.6 0.8 0.8 1 1 Рис. 4.7: ROC–кривая 9 В случае с большой выборкой ROC-кривая выглядит следующим образом: Рис. 4.8: Кривая ROC в реальных задачах с десятками тысяч объектов Кривая стартует с точки (0, 0) и приходит в точку (1, 1). При этом, если существует идеальный классифи- катор, кривая должна пройти через точку (0, 1). Чем ближе кривая к этой точке, тем лучше будут оценки, а площадь под кривой будет характеризовать качество оценок принадлежности к первому классу. Такая метрика называется AUC–ROC,или площадь под ROC-кривой. 4.5.5. Особенности AUC-ROC Как было написано выше, ROC-кривая строится в осях F P R и T P R, которые нормируются на размеры классов: F P R = F P F P + T N , T P R = T P T P + F N Следовательно, при изменении баланса классов величина AUC-ROC и неизменных свойствах объектов вы- борки площадь под ROC-кривой не изменится. В случае идеального алгоритма AUC − ROC = 1, а в случае худшего AUC − ROC = 1 2 Значение AUC−ROC имеет смысл вероятности того, что если были выбраны случайный положительный и случайный отрицаельный объекты выборки, положительный объект получит оценку принадлежности выше, чем отрицательный объект. 4.5.6. Особенности AUC-PRC PR-кривая строится в осях precision и recall: precision = T P T P + F P , recall = T P T P + F N , а следовательно изменяется при изменении баланса классов. 10 Урок 3 Проблема переобучения и борьба с ней 3.1. Проблема переобучения 3.1.1. Пример: проблема переобучения в задачах классификации Допустим при решении задачи классификации был построен некоторый алгоритм, например линейный клас- сификатор, причем доля ошибок на объектах из обучающей выборки была равна 0.2, и такая доля ошибок является допустимой. Но поскольку алгоритм не обладает обобщающей способностью, нет никаких гарантий, что такая же доля ошибок будет для новой выборки. Вполне может возникнуть ситуация, что для новой выборки ошибка станет равной 0.9. Это значит, что алгоритм не смог обобщить обучающую выборку, не смог извлечь из нее закономерности и применить их для классификации новых объектов. При этом алгоритм как-то смог подогнаться под обучающую выборку и показал хорошие результаты при обучении без извлечения истинной закономерности. В этом и состоит проблема переобучения. 3.1.2. Пример: проблема переобучения в задачах линейной регрессии Глубже понять проблему переобучения можно на данном примере. На следующем графике изображена ис- тинная зависимость и объекты обучающей выборки: 0 1 2 3 4 5 6 7 8 9 4 2 0 2 4 Рис. 3.1: Истинная зависимость (зеленая линия) и элементы обучающей выборки (изображены синими точ- ками). Видно, что истинная зависимость является нелинейной и имеет два экстремума. 1 В модели a(x) = w 0 , после того, как она будет настроена под данные, на графике получается некоторая горизотальная кривая, которая довольно плохо обобщает информацию об объектах из выборки. 0 1 2 3 4 5 6 7 8 9 10 5 0 5 10 Рис. 3.2: Модель a(x) = w 0 Имеет место недообучение. Хороший алгоритм не был построен, поскольку семейство алгоритмов слишком мало и с его помощью невозможно уловить закономерность. В линейной регрессии используется семейство алгоритмов a(x) = w 0 + w 1 x 0 1 2 3 4 5 6 7 8 9 10 5 0 5 10 Рис. 3.3: Модель a(x) = w 0 + w 1 x В этом случае также будет иметь место недообучение. Получилось лучше, но прямая тоже плохо описывает данные. Если семейство алгоритмов — множество многочленов 4-ей степени: a(x) = w 0 + w 1 x + w 2 x 2 + ... + w 4 x 4 , то после обучения получившаяся кривая будет достаточно хорошо описывать и обучающую выборку, и ис- тинную зависимость. 2 0 1 2 3 4 5 6 7 8 9 10 5 0 5 10 Рис. 3.4: Модель a(x) = w 0 + w 1 x + w 2 x 2 + ... + w 4 x 4 В таком случае качество алгоритма хорошее, но нет идеального совпадения. Встает вопрос, а можно ли добиться совпадения увеличением сложности алгоритма. При использовании многочленов 9-ой степени уже имеет место переобучение. 0 1 2 3 4 5 6 7 8 9 10 5 0 5 10 Рис. 3.5: Модель a(x) = w 0 + w 1 x + w 2 x 2 + ... + w 9 x 9 Восстановленная зависимость дает идеальные ответы на всех объектах обучающей выборки, но при этом в любой другой точке сильно отличается от истинной зависимости. Такая ситуация называется переобучением. Алгоритм слишком сильно подогнался под обучающую выборку ценой того, что он будет давать плохие ответы на новых точках. |