Машинное обучение столкнулось с нерешенной математической проблемой

Автор оригинала: Davide Castelvecchi
  • Перевод
Салют, хабровчане! В преддверии запуска новых потоков по продвинутому и базовому курсам «Математика для Data Science» хотим поделиться с вами достаточно интересным переводом. В этой статье не будет практики, но материал интересен для общего развития и обсуждения.





Группа исследователей столкнулась с открытой математической проблемой, связанной с рядом логических парадоксов, которые были открыты знаменитым австрийским математиком Куртом Гёделем еще в 1930-х годах.

Математики, работавшие над проблемами машинного обучения, доказали, что возможность «обучаемости», то есть то, может ли алгоритм извлечь паттерн из ограниченных данных, тесно связана с парадоксом, известным как гипотеза континуума. Гедель говорил о том, что с помощью стандартных возможностей математического языка гипотезу нельзя ни подтвердить, ни опровергнуть. Последние результаты исследований на эту тему были опубликованы в Nature Machine Intelligence от 7 января.

«Для нас это было неожиданностью», — сказал Амир Иегудаев из Technion – Израильского Института Технологий в Хаифе, который был соавтором исследования. Он говорил о том, что несмотря на ряд технических вопросов, которые также известны как «неразрешимые», он не ожидал, что это явление встретится в, казалось бы, простой задаче машинного обучения.

Джон Такер, специалист по computer science Университета Суонси, Великобритания, говорит, что эта работа представляет из себя «весомый результат на границе наших знаний», с основополагающими последствиями как для математики, так и для машинного обучения.

Не все наборы одинаковы


Исследователи часто определяют обучаемость с точки зрения того, может ли алгоритм обобщать свои знания. Алгоритм дает ответ «да» или «нет», например, на вопрос «Есть ли на изображении кошка?» для ограниченного числа объектов, а затем он должен сделать прогноз для новых, ранее неизвестных ему, объектов.

Иегудаев и его коллеги получили результаты, исследуя связь между обучаемостью и «сжатием», которое включает в себя поиск способа отображения характерных признаков большого набора данных на меньший набор. Авторы обнаружили, что способность информации эффективно сжиматься сводится к вопросу теории множеств – математических совокупностей объектов, таких как множества в диаграммах Венна. В частности, это относится к множествам различного размера, содержащим бесконечно большое количество объектов.

Георг Кантор, основатель теории множеств, в 1870-х годах доказал, что не все бесконечные множества равны между собой: так, например, множество целых чисел «меньше», чем множество всех действительных чисел, также известное как континуум. (Поскольку действительные числа включают в себя иррациональные, а также рациональные и целые числа.) Кантор также предположил, что не существует множеств промежуточного размера, то есть большего, чем множество целых чисел, но меньшего, чем континуум. Но он не смог доказать эту гипотезу континуума, как и многие математики и логики – его последователи.

Их усилия оказались напрасны. В 1940 году Гедель провел исследование (которое было завершено только в 1960-х годах американском математиком Полом Коэном), в котором с помощью аксиом доказал, что гипотеза континуума не может быть ни истинной, ни ложной.

Работа Геделя и Коэна над гипотезой континуума допускает, что могут существовать параллельные математические вселенные, отвечающие законам стандартной математики: одна — в которой гипотеза континуума становится общепринятой аксиомой, то есть объявляется истинной, а вторая – в которой она же объявлена ложной.

Лимб обучаемости


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

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

«Результат исследования также помогает сформировать более широкое понимание обучаемости», говорит Иегудаев. «Эта связь между сжатием и обобщением действительно фундаментальна в вопросе понимания процесса обучения.»

«Исследователи обнаружили ряд подобных «неразрешимых» проблем», говорит Питер О'Хирн, специалист по computer science из Университетского Колледжа в Лондоне. В частности, по результатам работ Геделя, Алан Тьюринг – один из основателей теории алгоритмов – обнаружил класс вопросов, на которые ни одна компьютерная программа не может гарантированно ответить за любое конечное число шагов.

«Однако неразрешимость, полученная в ходе последних исследований очень редка и гораздо более удивительна», добавляет О'Хирн: она указывает на то, что Гедель обнаружил внутреннюю неполноту любого рода математического языка. Полученные результаты, вероятно, окажутся важны для теории машинного обучения, однако вряд ли это окажет большое практическое влияние.

Пишите в комментарии, что думаете по поводу данного материала, а мы приглашаем вас на бесплатный вебинар, в рамках которого поговорим о методах регрессионного анализа в Data Science.
OTUS. Онлайн-образование
Цифровые навыки от ведущих экспертов

Комментарии 11

    +53
    Континуум-гипотеза не является парадоксом и не является нерешенной математической проблемой. Она просто недоказуема в стандартной теории множеств основывающейся на аксиоматике Цермело-Френкеля. То что недоказуемо отрицание этой гипотезы было установлено Геделем, а недоказуемость утверждения этой гипотезы была доказана Коэном. Это значит всего лишь, что континуум-гипотезу, равно как и ее отрицание можно добавлять в аксиоматику теории множеств. И будут получаться различные внутренне непротиворечивые теории множеств.

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

    Ровно также дело обстоит с континуум-гипотезой.

    нерешенная ≠ неразрешимая

    P.S. За наводку на статью спасибо, посмотрю что они там придумали :)
      +10
      Вот, я бы тоже хотел когда-то так писать комментарии. В одной плоскости — как тот, кто понимает и объясняет для тех, кто понял статью, и в другой — как тот, кто понимает и объясняет для тех, кто хотел понять статью, но не понял (это сейчас я), но так, чтобы после объяснения у тех, кто не понял до прочтения объяснения, возникло желание ещё раз прочитать статью и попытаться её понять, взяв под руку википедию.

      Поэтому я люблю популяризаторов науки (кем для меня являетесь и вы, stabuev). Просто спасибо!
        +16

        Информативность и понятность этого комментария в бесконечность раз превосходит информативность и понятность статьи.


        Спасибо.

          0
          Тоже об этом подумал, но вопрос — если её добавить в аксиомы математика останется непротиворечивой?
            +3
            Именно так, ведь была доказана непротиворечивость этого факта, как и его отрицания аксиоматике.

            Но в основаниях теории множеств вообще все непросто, потому что непротиворечивость принятой аксиоматики (ZFC) сама по себе не доказана, поэтому когда что-то доказывают в этой области оговаривают, «если не противоречива аксиоматика, то...»
          +2

          По ходу тут какие-то проблемы с переводом, так как возможность обобщения модели, обученной на конечных наборах данных была показана Вапником и Червоненкисом ещё в 70-х. В итоге не понятно, о чем идёт речь в статье (скорее всего о чем-то другом), или что-то не так с формулировка и проблемы. Надо будет почитать оригинальную работу.

            +1
            Посмотрел с утра работу, с первого наскока разобраться не получилось, довольно сложный язык + не всегда строгие формулировки, надо смотреть предысторию по ссылкам, но то, что я понял — это они берут конечные наборы из множества мощности континуума — отрезка [0, 1] и что-то крутят с ними. Попробую еще поковырять.
          –1
          Поскольку действительные числа включают в себя иррациональные, а также рациональные и целые числа
          Миллениалы изобрели доказательство теоремы Кантора
            +2
            исследуя связь между обучаемостью и «сжатием», которое включает в себя поиск способа отображения характерных признаков большого набора данных на меньший набор...

            Когда завели речь о сжатии, то вспомнилась проблема невычислимости Колмогоровской сложности и связанный с ней принцип Минимальный длины сообщения (… который, «в статистическом и индуктивном выводе и машинном обучении был разработан Уоллесом (англ. C. S. Wallace) и Болтоном (англ. D. M. Boulton) в 1968 году.»)

            «Эта связь между сжатием и обобщением действительно фундаментальна в вопросе понимания процесса обучения.» — говорит Иегудаев

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

            Эта проблема, действительно, очень неплохо коррелирует с обучением: даже когда, казалось бы, нам известно «всё» про изучаемый предмет — не лишним будет всегда оставлять допущение, что «что-то про явление мы всё ещё не знаем». И это какое-то фундаментальное свойство природы, если нам заведомо неизвесна полная аксиоматика теории, которая это явление описывает.
              +1
              множество целых чисел «меньше», чем множество всех действительных чисел, также известное как континуум. (Поскольку действительные числа включают в себя иррациональные, а также рациональные и целые числа.)

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

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

              Самое читаемое