Pour la science № 511 - как оценить сложность модели?
Одна из тем, больше всего мне понравившихся в Machine Learning - это проблема overfit.
Грубо говоря, кода мы учим систему классифицировать что-то, это сводится к интерполяции каких-то известных точек некой аналитической формулой, которая потом поможет нам предсказывать неизвестные точки. Предположим, что у нас на двухмерном графике (размер / плотность) есть точки, соответствующие разным опухолям, и про какие-то опухоли мы знаем, что они - раковые, а другие - безопасные. В таком случае мы можем попытаться «обучить систему», проведя кривую, разделяющую зону раковых опухолей от обычных. И потом этот «искусственный интеллект» сможет различать раковые опухоли от нераковых, исходя из местоположения новых опухолей в нашей плоскости (по параметрам размер и плотность и по расположению точки относительно кривой).
Проблема overfit состоит в том, что через любые точки можно провести некую кривую, например, полином огромной степени (грубо говоря, через любые n+1 точку можно провести полином n-й степени) - очевидно, что результат будет прекрасным на наших точках, но совершенно не будет годиться для будущих предсказаний, потому что на самом деле полином будет вести себя достаточно хаотично, лишь «случайно» попадая по всем точкам наших данных.
Стандартным решением этой проблемы является уменьшение количества параметров системы (снижение степени полинома), введение штрафов за слишком большие коэффициенты (снижение хаоса, когда на обучающих точках огромные числа с разным знаком компенсируют друг друга) и т.п. Это действительно, работает, но авторы статьи в журнале обращают внимание на опасность простого подсчёта количества параметров системы для оценки её сложности. Это на самом деле существует - я на работе часто вижу аргументы в духе «эта модель с 3 параметрами, а значит...». Собственно, малое количество параметров нормального распределения объясняет, почему его суют не только туда, где его использование оправдано, но и вообще везде, где нет никакой информации о реальном распределении - это «самое экономное» распределение, к тому же издалека похоже на правду в подавляющем большинстве случаев.
Прелюдия закончилась, собственно статья о том, как математики придумали параметрическую функцию со всего одним параметром, способную объяснить любое количество точек. Они немедленно подняли старую шутку фон Неймана и нашли значение параметра, при котором график функции выглядит как слон. Потом нашли значение параметра для птички, ещё одно для черепахи - у них была не только функция, но и алгоритм нахождения параметра, дающего график, проходящий через любое количество заранее известных точек.
Фокус на самом деле достаточно простой, в статье его иллюстрируют другим примером. Предположим, мы хотим построить функцию, которая на целых числах 1, 2, 3, ... даёт бинарные значения a1, a2, a3, ... Функция с параметром p выглядит как D(n, p) = D(D(n - 1, p)), D(1, p) = 2p mod 1 (дробная часть после умножения на 2). На самом деле функция даже E(D(n, p)), где E возвращает первую цифру после запятой от полученного числа. Таким образом, D(1, p) - вторая цифра после запятой в бинарной записи p, D(2, p) - третья цифра и т.д. То есть, p = a1a2a3a4... - просто запись подряд всех нужных нам ответов. Секрет кроется в том, что мы допускаем параметр с бесконечной точностью. Тема, на которую автор писал уже колонку несколько месяцев назад, и я её пересказывал.
То есть, простой подсчёт количества параметров действительно бессмысленный, так как мы можем упаковать в один параметр любое конечное количество параметров с конечной точностью. Непонятно, на что можно было бы его заменить. По аналогии с Machine Learning, где часто вводят дополнительный коэффициент штрафа за большие значения параметров - здесь, наверное, нужно вводить штраф за чувствительность результата к малым изменениям параметра. Что-то вроде подсчёта не просто количества параметров, а количества значащих цифр всех параметров - количество цифр, которые мы обязаны сохранить для сохранения результата, а после которых мы вольны ставить всё, что угодно.
Удивительно при этом, что автор совсем не затрагивает тему чувствительности системы к её параметрам - у нас это самый что ни на есть стандартный тест (более того, это ещё и стандартный тест при любом контроле нас со стороны законодателя).
А ещё идея использования бесконечного количества информации в действительных числах напоминает наш с catpad разговор о том, как вытаскивать информацию из числа пи. В статье упоминают и эту тему, это называется гипотезой универсальности числа пи (гипотеза о том, что в числе пи есть любая конечная последовательность цифр), отмечая при этом преимущество описанной в статье функции (осторожно: я описал только простую иллюстрацию, в статье речь идёт о другой функции): в отличие от пи, универсальность этой функции доказана, к тому же известен работающий алгоритм построения параметра для любой последовательности. В то время как для пи, даже если мы когда-нибудь докажем его универсальность, алгоритма никакого нет, только перебор.
Грубо говоря, кода мы учим систему классифицировать что-то, это сводится к интерполяции каких-то известных точек некой аналитической формулой, которая потом поможет нам предсказывать неизвестные точки. Предположим, что у нас на двухмерном графике (размер / плотность) есть точки, соответствующие разным опухолям, и про какие-то опухоли мы знаем, что они - раковые, а другие - безопасные. В таком случае мы можем попытаться «обучить систему», проведя кривую, разделяющую зону раковых опухолей от обычных. И потом этот «искусственный интеллект» сможет различать раковые опухоли от нераковых, исходя из местоположения новых опухолей в нашей плоскости (по параметрам размер и плотность и по расположению точки относительно кривой).
Проблема overfit состоит в том, что через любые точки можно провести некую кривую, например, полином огромной степени (грубо говоря, через любые n+1 точку можно провести полином n-й степени) - очевидно, что результат будет прекрасным на наших точках, но совершенно не будет годиться для будущих предсказаний, потому что на самом деле полином будет вести себя достаточно хаотично, лишь «случайно» попадая по всем точкам наших данных.
Стандартным решением этой проблемы является уменьшение количества параметров системы (снижение степени полинома), введение штрафов за слишком большие коэффициенты (снижение хаоса, когда на обучающих точках огромные числа с разным знаком компенсируют друг друга) и т.п. Это действительно, работает, но авторы статьи в журнале обращают внимание на опасность простого подсчёта количества параметров системы для оценки её сложности. Это на самом деле существует - я на работе часто вижу аргументы в духе «эта модель с 3 параметрами, а значит...». Собственно, малое количество параметров нормального распределения объясняет, почему его суют не только туда, где его использование оправдано, но и вообще везде, где нет никакой информации о реальном распределении - это «самое экономное» распределение, к тому же издалека похоже на правду в подавляющем большинстве случаев.
Прелюдия закончилась, собственно статья о том, как математики придумали параметрическую функцию со всего одним параметром, способную объяснить любое количество точек. Они немедленно подняли старую шутку фон Неймана и нашли значение параметра, при котором график функции выглядит как слон. Потом нашли значение параметра для птички, ещё одно для черепахи - у них была не только функция, но и алгоритм нахождения параметра, дающего график, проходящий через любое количество заранее известных точек.
Фокус на самом деле достаточно простой, в статье его иллюстрируют другим примером. Предположим, мы хотим построить функцию, которая на целых числах 1, 2, 3, ... даёт бинарные значения a1, a2, a3, ... Функция с параметром p выглядит как D(n, p) = D(D(n - 1, p)), D(1, p) = 2p mod 1 (дробная часть после умножения на 2). На самом деле функция даже E(D(n, p)), где E возвращает первую цифру после запятой от полученного числа. Таким образом, D(1, p) - вторая цифра после запятой в бинарной записи p, D(2, p) - третья цифра и т.д. То есть, p = a1a2a3a4... - просто запись подряд всех нужных нам ответов. Секрет кроется в том, что мы допускаем параметр с бесконечной точностью. Тема, на которую автор писал уже колонку несколько месяцев назад, и я её пересказывал.
То есть, простой подсчёт количества параметров действительно бессмысленный, так как мы можем упаковать в один параметр любое конечное количество параметров с конечной точностью. Непонятно, на что можно было бы его заменить. По аналогии с Machine Learning, где часто вводят дополнительный коэффициент штрафа за большие значения параметров - здесь, наверное, нужно вводить штраф за чувствительность результата к малым изменениям параметра. Что-то вроде подсчёта не просто количества параметров, а количества значащих цифр всех параметров - количество цифр, которые мы обязаны сохранить для сохранения результата, а после которых мы вольны ставить всё, что угодно.
Удивительно при этом, что автор совсем не затрагивает тему чувствительности системы к её параметрам - у нас это самый что ни на есть стандартный тест (более того, это ещё и стандартный тест при любом контроле нас со стороны законодателя).
А ещё идея использования бесконечного количества информации в действительных числах напоминает наш с catpad разговор о том, как вытаскивать информацию из числа пи. В статье упоминают и эту тему, это называется гипотезой универсальности числа пи (гипотеза о том, что в числе пи есть любая конечная последовательность цифр), отмечая при этом преимущество описанной в статье функции (осторожно: я описал только простую иллюстрацию, в статье речь идёт о другой функции): в отличие от пи, универсальность этой функции доказана, к тому же известен работающий алгоритм построения параметра для любой последовательности. В то время как для пи, даже если мы когда-нибудь докажем его универсальность, алгоритма никакого нет, только перебор.