Как важно быть открытым

[xaxam]

ИИ и математика

Квазиоднокашник ny_quant  впечатлился успехами ИИ: (впервые?) Axiom AI решил все задачи Putnam competition. Задачи и решения доступны по ссылке, но честно признаюсь, — я пастернака не читал, но осуждаю™ и ничуть не впечатлён.

И вот почему. Чем долго объяснять, прибегну к излюбленному приёму — аналогии и аллегории.

1. Шахматы. Я не умею играть, но кое-что слышал от тех, кто видел тех, кто умеет. Играть "живую" партию против (сильного) противника гораздо труднее, чем решать шахматные этюды, сколь бы красивыми ни были решения (авторские или посторонние). Как и в преферансном этюде Ласкера, знание того, что решение существует, очень помогает.
2. Игра в "заначку". Вы прячете заначку в комнате, ваша лучшая половина пытается её найти. Сделать это обычно гораздо легчее и быстрее, чем найти, куда же гостившая у вас месяц тёща могла убрать нож для открывания устриц, руководствуясь исключительно соображениями того, где бы его было проще найти, когда понадобится.
3. Древние греки, не зная механических замков, для предотвращения несанкционированного доступа к своим домам вязали разные узлы, всё сложнее и сложнее. Даже если оставить за кадром решение Гордия, сравните две задачи: развязать узел, завязанный хитроумным Одиссеем, и распутать клубок бабушкиной шерсти, с которой порезвились двое маленьких котят.
4. "Олимпиадная математика": all of the above. К Математике как таковой она давным давно не имеет никакого отношения, превратившись в искусство разгадывания специально составленных ребусов.

Понятно, что способность ИИ отслеживать и препарировать все труды шахматных/математических композиторов (хороших — немногие десятки на весь мир) намного превосходит креативность этих заслуженных творцов. Уж если что и могло бы поразить воображение — так это попросить ИИ сочинить несколько осмысленных сложных задач, на которых бы сломались "кожаные умы". Давеча в каком-то из из офф-топов зашла дискуссия, насколько осмысленна могла быть подобная задача, но вердикта общественность так и не вынесла.

Для порядка выступлю адвокатом дьявола, заодно расскажу очень поучительную математическую историю. Бесконечность множества простых чисел — один из первых сногсшибательных результатов Математики. Отче Наш™ Евклид дал самое простое и естественное доказательство этому факту. Если б простых чисел было конечное число, можно было бы перемножить их все между собой, после чего прибавить единицу. Результат давал бы в остатке единицу при делении на любое из перечисленных простых чисел, после чего остаются два варианта: либо результат является новым, явно неучтённым простым числом, но даже если нет, — он должен делиться на какое-то неучтённое простое число. И в том и в другом случае мы получаем противоречие с предположением о конечности.

Следующий шаг (глубочайший в смысле привлечения самых плодотворных идей) принадлежит Эйлеру. Он написал гармонический ряд (сумма аликвотных дробей 1/n по всем натуральным числам n), известный в широких кругах своей медленной расходимостью (сумма первых N членов растёт примерно как ln N), переразложил его в подряды в соответствии с делимостью n на разные простые числа и пришёл к выводу, — если б простых чисел было конечное число, то гармонический ряд сошёлся бы volens-nolens. Идеи Эйлера были восприняты очень многими, вплоть до Римана, который сформулировал свою гипотезу про дзета-функцию. Не будучи ни в малейшей степени понимантом этой теории, я слышал стопиццот неформальных соображений, почему гипотеза Римана просто обязана быть верной, — и от числовиков, и от специалистов по динамическим системам, и от комплексных аналитиков, — да от кого только нет). Но только воз и ныне тут, — любое серьёзное доказательство гипотезы Римана будет проверено сотнями первоклассных математиков, которые пытались совершить восхождение к этой Джомолунгме и прекрасно знают, в каком месте их самые профессиональные предшественники срывались в пропасть, не дойдя до вершины.

Но вот буквально вчера по историческим меркам, в 1955-м, бесконечно уважаемый мной Гиллель (Гарри) Фюрстенберг придумал "топологическое" доказательство бесконечности множества простых чисел. Оно довольно элементарно, вот видос с его подробным рассказом. Основная идея — определить на множестве ℤ целых чисел извращённую топологию. Для тех, кто не в танке, напомню: задать на (произвольном) множестве топологию означает пометить какие-то подмножества этого множества как открытые™, с соблюдением минимальных условий:

1. Пустое множество и всё множество целиком — открыты;
2. Объединение любого "числа" (имеются в виду бесконечные объединения любой мощности) открытых множеств — открыто;
3. Пересечение конечного числа открытых множеств — открыто.

Дополнение к открытому множеству называется замкнутым™, с соответствующими условиями (конечное объединение и любое пересечение замкнутых множеств — замкнуто). Пробормотав эти заклинания, можно дальше рассуждать о непрерывности, компактности, связности, и прочей топологической абракадабре, не мучаясь никакой геометрической интерпретацией. Кру́жки, бублики, шарики, пуанкаре и перельманы отдыхают в дальнем углу ринга, где собрались в узкий кружо́к очень специальные топологические пространства с аристократической топологией. А самая простая топология, конечно, обитает на конечных множествах, где любое подмножество одновременно и открытое и замкнутое (такая вот дискретная демократия).

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

При таком определении непустое конечное подмножество ℤ не может быть открыто, поскольку мы разрешаем только прогрессии с ненулевым шагом, а в них всегда бесконечное число элементов.

Предположим, что множество простых чисел конечно, и рассмотрим всевозможные прогрессии, содержащие ноль и имеющие простой шаг. Такое объединение должно включать все целые точки, кроме двух, +1 и −1 (каждое число либо само просто, либо имеет простой делитель). С другой стороны, в силу предположения о конечности оно обязано быть замкнутым по топологическим соображениям (см. выше). Но тогда отсюда следовало бы, что множество из двух точек открыто, что невозможно. Ч.Т.Д.

Является ли это доказательство на самом деле "новым" доказательством того, что простых чисел бесконечно много? Нет. В основе доказательства лежит тот самый "трюк" Евклида, просто он запрятан очень глубоко, в утверждении об открытости пересечения двух прогрессий (то самое, доказательство которого столь любезно предоставлено зрителю). Фюрстенберг "просто" перевёл этот трюк на топологический язык, сочинив тем самым блистательный и совершенно неожиданный пример применения простейших свойств делимости к специальной топологии на ℤ.

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

Задача. Назовём непустое подмножество ℤ "хорошим", если оно есть объединение любого числа целочисленных арифметических прогрессий с ненулевым шагом. Докажите, что пересечение любого конечного числа "хороших" множеств либо пусто, либо "хорошее".

Я подсунул её Гроше: он настучал ответ немедленно. Как и следовало ожидать. Впрочем, Гроша и полное доказательство Фюрстенберга знает. Талант композитора состоял в том, чтобы найти неожиданно красивую формулировку. До того, чтобы решать открытые (и интересные, содержательные) математические проблемы, ИИ ещё крутить и крутить шестерёнками. Пока он неплохо работает секретаршей и библиотекаршей (если не начинаются вдруг месячные глюки).

Comments

[rusty_spur]

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

[xaxam]

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

[rusty_spur]

Да, но эта секретарша уж больно фантазийная. Особенно дипсик, прямо мастер придумывать научные статьи и даже журналы

[xaxam]

Проверять надо. Я в последнее время, скажем, пользуюсь ИИ примерно следующим образом. "Знаешь ли ты такую-то теорему? (следует примерное описание того, что мне надо)". Как правило, ответ "знаю". "Где она доказана? Напиши доказательство". А дальше - проверять. Лажается часто, но ошибки признаёт, не кобенясь (в отличие от кожаных авторов).

[rusty_spur]

А профит в чем? Пока не нахожу выгоды в пререпроверке ии или простом поиске.
PS Можно конечно лажу что ИИ нагенерил (правдоподобную) давать студентам на экзамене и говорить - опровергни

[fslon.livejournal.com]

Шахматные программы тоже не сразу заиграли. А теперь попробуй у них выиграй

[xaxam]

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

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

[ny_quant]

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

Популярные ИИ с олимпиадными задачами справляются очень плохо, причем чем элементарнее формулировка тем хуже. Я пробовал, кстати, давать задачи из предыдущих Putnams. Решали не все, но те что решали делали это довольно быстро - за минуты. Думаю, что все 12 никакой грок пока что не решит.

Не впечатлены так не впечатлены, дело такое. Но есть ощущение, что мы играем в известную игру под названием "тогда и поговорим". You are here now.

[fslon.livejournal.com]

Я тоже не про сравнение уровня игры. Я про то, что вначале программы были айяйяй, а через полвека стали ойейей. ИИ и 5 лет нету. Но если сравнить то, что есть сейчас, с тем, что было вначале, и проэкстраполировать на 50 лет вперед (что, конечно, мало осмысленно в плане получения точного результата), то можно порадоваться (или наоборот), что жить в ту прекрасную пору нам не дано :)

[ny_quant]

Именно!

[(Anonymous)]

А надо пробовать?

Или это такое же бессмысленное упражнение, как бег наперегонки с машиной?

Причем из за наличия машин бег бессмысленным не становится.

[xaxam]

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

[(Anonymous)]

Как обучение - само собой разумеется.

Шахматы тоже не люблю - самый продвинутый в мире тайм-киллер. А если как развлечение - то есть много умных игр попроще.

[dragonru]

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

[prof_yura]

Пару месяцев назад мне прислали на quick opinion статью, подписанную каким-то индусом, но явно написанную AI. Меня позабавила липовая ссылка на статью в Publ. Math. IHES (при этом, в качестве авторов были указаны реальные математики). Ну, и конечно, глубокая теорема, формулировка которой заканчивается следующим образом.

"Тогда существует константа C."

(Дальше примерно на полстраницы идет обсуждение того, как и почему эта теорема важна . . .)

[ny_quant]

Я уверен, что при желании можно будет еще долго находить поводы похихикать над ИИ и ея незадачливыми пользователями. А тем временем Теренс Тао с соавторами уже применили ИИ для решения ранее нерешенных (или улучшения имеющихся) решений задач Эрдоша. Конечно, можно сказать, что Эрдош это пустяки, вот когда оно докажет гипотезу Римана, тогда и поговорим. Но, имхо, это не самый правильный взгляд.

[prof_yura]

при желании можно будет еще долго находить поводы похихикать над ИИ и ея незадачливыми пользователями.

Речь идет не о хихиканье, а о реальной проблеме, с которой столкнулись (из-за AI) редакторы всех нормальных научных журналов (рецензентов не напасешься), возможные решения которой не сильно вдохновляют. Да и незадачливость жуликоватых пользователей AI я не стал бы переоценивать, - где-нибудь прорвутся/напечатаются.

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

[rusty_spur]

Мне бы хотелось использовать а не хихикать, но что то пока не выходит

[ny_quant]

Дайте срок, как говорил знакомый прокурор.

[rusty_spur]

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

[rusty_spur]

Он даже реальность ссылок поленился проверить?
PS Не скажу что до ИИ такой проблемы не было

реальность ссылок поленился проверить

[prof_yura]

Думаю, что этот джентльмен (если он реально существует) разослал кучу различных статей (спасибо AI) в самые разные журналы; так что же, прикажете многие сотни ссылок проверять? :-)

Кстати, это один из характерных черт творчества AI, - выдаются на гора правдоподобно смотрящиеся фальшивые ссылки.

[van_wylen]

не знаю про математику....но прикладные задачи по механике он не решает от слова совсем

[memdaletpey]

И программный код генерирует быстро но низкого качества.
Этот код хорош для решения небольших сиюминутных задач, то есть в пределах одной-двух функций за раз.
Он не reusable, часто используются какие-то малоизвестные маргинальные особенности какой-то специфической версии языка, совершенно unmaintainable и т.д.
То есть ниша применения кода сгенерированого таким образом безусловно существует.
Облегчает ли ИИ работу программиста - да, безусловно.
Вытеснит ли ИИ код, как он существует сегодня, программирование как массовую профессию - нет.

[tuli_pimendatud_linnas]

А в чём дело с олимпиадной математикой? Был ли критический момент исчерпания парадигмы, и был ли он неизбежен?

[xaxam]

Олимпиадная математика родилась из "кружковской", делавшей акцент на "нетривиальные" рассуждения в отличие от "школьных" доказательств. Как всегда, спортивный элемент всегда присутствовал, но когда олимпийское движение стало массовым, возникла потребность в сочинении новых задач в промышленных количествах. Количество действительно талантливых композиторов, сочинявших красивые задачи (и простые и сложные) очень невелико.

А если вам нужно каждую неделю писать новую кантату, а вы не обладаете талантом Баха, то у вас будут получаться гаммы Ганона во всё более извращённых тональностях.

[(Anonymous)]

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

А нетривиальность - она и в грамотно выстроенной школьной программе вполне себе встречается.

[xaxam]

Вы в каком полку служили в какой кружок ходили?

[(Anonymous)]

Ни в какой не ходил, мне вполне хватало очень хорошей школы и самостоятельных занятий.

[xaxam]

А я с 7-го класса ходил на кружок при МГУ, потом два старших класса проучился в матшколе в классе, набранном по итогам олимпиад и знакомства с кружковцами, а потом ещё почти десять лет преподавал в своей же школе, параллельно ведя кружки и раз в 2-3 года набирая новые классы.

Хвалиться анонимно своими достижениями некрасиво и неубедительно, но количество моих школьных учеников, ставших сегодня профессорами математики в Ivy League универстетах или примерно эквивалентными европейскими профессорами в Европе - около десятка (это не считая тех, кого я учил уже в докторантуре). Есть один (как минимум) российский академик.

Позвольте мне иметь своё личное мнение про то, чем хороши и чем плохи математические кружки, матшколы и олимпиады.

[(Anonymous)]

Так разве я покушаюсь на ваше личное мнение?

Просто у меня есть свое - те ребята, которые ходили на ваш кружок и учились с вами в одном классе, изначально были хороши. И если бы не ходили на кружок - вряд ли стали бы сильно хуже.

[dragonru]

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

А вот то, что живой противник часто будет делать не сильнейшие ходы, а те, которые наиболее эффективно мешают вашим планам - это уже другой вопрос. И кстати, шахматные программы этому тоже научились. Понаблюдайте, как играет LeelaRookOdds - давая фору в ладью, просто делать правильные ходы недостаточно, надо уметь делать "неправильные" ходы :)

[xaxam]

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

[homoscript]

"А самая простая топология, конечно, обитает на конечных множествах, где любое подмножество одновременно и открытое и замкнутое."
Пустяк, но "кроме тривиальной топологии с открытыми пустым 0 и самим множеством Х".