2015 Методичка по ММО (сделана частично_ не все темы), страница 3

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

Пример:

в нашей местности вероятность встретить опасного животного 0.0001%

у 95% опасных животных и у 2% неопасных животных есть острые клыки

90% опасных животных и 5% неопасных рычат

Выйдя за ворота вы встретили льва, он рычит и имеет острые клыки. Он опасен?

Вероятность, что он опасен = P = 0,95*0,90*0,0001 / (0,95*0,90*0,0001 + 0,02*0,05*0,9999) =

0,0000855 / (0,0000855 + 0,0009999) = 8%

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

1. Кажущееся vs целесообразное

Важен размер выборки, на малых выборках степень уверенности, о верности принятого решения - меньше. (например, мы вылечили 8 из 10 или 800 из 1000).

Люди на практике часто принимают решения, не являющиеся оптимальными в соответствии со статистикой.

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

Логически нужно выбрать то решение, которое даст лучший результат (!!! с чего бы это?)

Вообще человек как правило выбирает решение, балансируя между 2-мя критериями: больше profit vs надёжность. В зависимости от ситуации (формулировки вопроса, важности цели, настроения, ...) человек будет по-разному полагаться на “авось повезёт”.

Теорема фон Неймана-Моргенштерна (Von Neumann–Morgenstern utility theorem):

Человек следующий рациональному поведению должен вести себя в соответствии с 4-мя аксиомами:

1. completeness (у индивида есть предпочтение между любыми 2-мя лотереями (<, >, ==)) - т.е. на множестве лотерей задано некоторое отношение

2. transitivity - заданное отношение транзитивно

3. continuity - есть некоторый переломный момент, когда индивид начинает склоняться от одной лотереи к другой (пусть L <= M <= N, существует 0 <= p <= 1, такое что pL + (1-p)N == M)

4. independence - пусть L < M, тогда для любого N и 0 < p <= 1, выполнено pL + (1-p)N < pM + (1-p)N (какой смысл в этой аксиоме?)

Санкт-Петербургский парадокс:

Питер подбрасывает монетку, если орёл, то платит 1$, если решка, то н подрасывает ещё раз и если орёл, то платит 2$, … по степеням двойки

Среднее ожидаемое значение = ½ *1 + ¼ * 2 + ⅛ * 4 + 1/16 * 8 + … = ½ + ½ + ½ + … = бесконечности

Но обычно окружающие люди согшалаются играть за 20$, не смотря на то, что они бы были в плюсе при постоянной игре, при абсолютно любой начальной ставке.

Elsberg paradox (парадокс неопределённости):

Известные вероятности предпочтительнее неизвестных.

Примеры:

1. Выбрая между лотереей, где человек получит 100 баксов в 1 из 80 случаев (т.е. средний выигрыш = 1.25$) и просто гарантированной разовой выплатой в 1$, люди выбирают первое.

(!!! возможно на слайде лажа, и нужно было сделать так, чтобы было 80 баксов на 100 случаев, чтобы ожидаемая выплата была меньше бакса, тогда если человек выберет лотерею - то это ещё более противоречиво, в то время как пример выше - это в целом нормальное поведение) (ну или люди выберут 2 вариант, то есть гарантированный выигрыш, что вполне коррелирует с вышесказанным)

1. Пример на парадокс Элсберга: пусть есть 2 урны, в одной 50 белых и 50 чёрных, а в другой просто есть 100 каких-то шариков. Сначала вам дано задание вынять белый шарик, люди лезут в первую урну, потом их просят вынят чёрный - и они снова лезут в первую урну. Хоте их первый выбор урны предполагал, что в первой урне белых шариков больше, чем во второй (иначе зачем было брать именно первую урну), и тогда второй раз они должны были полезть рукой во вторую урну, но нет.

2. Выбирая между лотереей, в которой гарантированно дадут 3000$ и лотереей, в которой дадут 4000$ с вероятностью 80% или ничего. 80% людей выбирают первое.

Выбирая между лотереей, в которой 3000$ с вероятностью 25% и лотереей 4000$ с ероятностью 20%, 35% выбрали первое, а 65% выбрали второе.

Теперь проанализируем средний выигрыш для первого выбора и второго выбора: 3000 против 3200 vs 750 против 800.

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

Этот эффект называется эффектом определённости (certainty effect).

Т.е. людям пресуще не рациональное поведение в соответствии с аксиомами теоремы фон неймана-...

1. Аналогично предыдущему случаю с certainty effect. Людям так же свойственно переоценивать важность малых (например, 0.001) вероятностей. - overweighting of small probabilities.

2. 1 выбор: что выбирете? “спасти 400 наверняка” или “не спасти никого с вероятностью ⅓ или всех 600 с вероятностью ⅔”.

2 выбор: что выбирете? “200 человек умрёт наверняка” или “спасти всех 600 с вероятностью ⅔ или никого”

Выборы абсолютно одинаковы, но в первом случае выбрают 9 к 17, а во втором 10 к 17.

Этот эффект называется framing effect.

Эффект определённости (certainty effect) - людей в среднем надёжность близкая к 1, привлекает больше обычного.

Overweighting of small probabilities - переоценка людьми малых вероятностей (например, 0.001)

Framing effect - отет людей в среднем зависит от того, ка поставить вопрос

1. Скользящий контроль

Скользящий контроль или кросспроверка или кроссвалидация (cross-validation, CV) — процедура эмпирического оценивания обобщающей способности алгоритмов, обучаемых по прецедентам.

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

Различные варианты скользящего контроля отличаются видами функционала качества и способами разбиения выборки.

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

Скользящий контроль является стандартной методикой тестирования и сравнения алгоритмов классификации, регрессии и прогнозирования.

Математические выкладки, о скользящем контроле можно прочесть в файле “4.1. Скользящий контроль - MachineLearning.pdf” или ссылке:

“http://www.machinelearning.ru/wiki/index.php?title=%D0%A1%D0%BA%D0%BE%D0%BB%D1%8C%D0%B7%D1%8F%D1%89%D0%B8%D0%B9_%D0%BA%D0%BE%D0%BD%D1%82%D1%80%D0%BE%D0%BB%D1%8C”

Доверительного оценивания - вроде не было на лекциях

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

Утверждение: Если разбиения осуществлялись независимо и равновероятно то (N - количество разбиений, случайная величина функционала качества Q, Q⁽ⁱ⁾ - упорядоченные по возрастанию функционалы качества разных разбиений)

1. с вероятностью t/(N+1) значение случайной величины Q не превосходит Q^{(N -t +1)}

   1. можно взять частный случай t=1 и тогда можно будет посчитать верхнюю оценку, в частности для получения верхней оценки с надёжностью 95% достаточно взять N = 20 разбиений.

2. с вероятностью 2t/(N+1) значение случайной величины Q лежит в интервале [Q^(t);Q^(N-t+1)]

   1. можно взять частный случай t=1 и тогда можно будет посчитать оценку для интервала [Q⁽¹⁾;Q^(N)], в частности для получения верхней оценки с надёжностью 95% достаточно взять N = 40 разбиений.

Стратификация выборки — это способ уменьшить разброс (дисперсию) оценок скользящего контроля, в результате чего получаются более узкие доверительные интервалы и более точные (tight) верхние оценки. Стратификация заключается в том, чтобы заранее поделить выборку на части (страты), и при разбиении на обучение длины m и контроль длины k гарантировать, что каждая страта будет поделена между обучением и контролем в той же пропорции m/k.

Стратификация классов в задачах классификации означает, что каждый класс делится между обучением и контролем в пропорции m/k.

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

Разновидности скользящего контроля:

1. Полный скользящий контроль - т.е. строятся все возможные разбиения при некоторм фиксированном k (k - количество элементов для контроля, остальное - идёт в обучающую выборку)

   1. частный случай при k = 1 - “контроль по отдельным объектам” (leave-one-out CV) (Было показано, что контроль по отдельным объектам является ассимптотически оптиальным при некоторых условиях) (один из самых распросранённых случаев) (имеет средний уровень вычислительно сложности, потому что нужно переобучиться L раз (столько, сколько элементов в выборке))

   2. общий случай при k > 2 имеет количество комбинаций N = C_L^k - что слишком много и затрудняет применение метода полного скользящего контроля

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

1. Случайные разбиения - разбиения выбираются равновероятно и независимо, именно для такого случая работают формулы описанные выше в утверждении. На практике эти формулы часто переносятся и на другие способы разбиения.

2. Контроль на отложенных данных (hold-out CV) - оценка скользящего контроля строится по одному случайному разбиению (N = 1). Недостатки:

   1. Приходится слишком много объектов оставлять в контрольной подвыборке. Уменьшение длины обучающей подвыборки приводит к смещённой (пессимистически завышенной) оценке вероятности ошибки.

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

   3. Оценка имеет высокую дисперсию, которая может быть уменьшена путём усреднения по разбиениям.

Следует различать скользящий контроль по отложенным данным и контроль по тестовой выборке. Если во втором случае оценивается вероятность ошибки для классификатора, построенного по обучающей подвыборке, то в первом случае для классификатора, построенного по полной выборке (то есть доля ошибок вычисляется не для того классификатора, который выдается в качестве результата решения задачи). <!!! что за муть тут написана?>

1. Контроль по q блокам (q-fold CV) - выборка разбивается на q блоков примерно одинаковой длинны, после этого каждый блок по очереди становится контрольной выборкой. Это компромисное решение между left-one-out, hold-out и случайным разбиениями. Обычно выборку разбивают на 10-20 блоков.

2. Контроль по r*q блокам (r*q-fold CV) - контроль ко q блокам повторяется r раз, каждый раз выборка случайным образом разбивается на q непересекающихся блоков.

Данный вариант является одним из стандартных и используется в системах WEKA и “Полигон алгоритмов”

Скользящий контроль в задачах прогнозирования.

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

1. Контроль при нарастающей длине обучения

Выбираем некоторый “настоящий момент”, после чего, всё что было до него - это в обучающую выборку, а всё что после - в контрольную выборку. Также можно взять некоторую величину задержки прогнозирования, и в контрольную выборку попадут только те объекты, которые находятся после настоящего момента + величина задержки прогнозирования.

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

1. Контроль при фиксированной длине обучения - отличается от предыдущего лишь тем, что длинна обучения фиксируется, ограничиваясь лишь поседними m прецедентами.

Недостатки скользящего контроля:

1. Задачу обучения приходится решать N раз, что сопряжено со значительными вычислительными затратами.

2. Оценка скользящего контроля предполагает, что алгоритм обучения уже задан. Она ничего не говорит о том, какими свойствами должны обладать «хорошие» алгоритмы обучения, и как их строить. Такого рода подсказки дают, например, теоретические оценки обобщающей способности.

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

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

Применения скользящего контроля:

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