Под гитарный перебор |
[May. 17th, 2025|07:13 am] |
 Эпистолярные романы и высокие отношенияЯ всё больше и больше начинаю ценить безропотного Грошу, известного под именем Grok. Почему именно его, из всей расплодившейся чат-гопоты? Буду откровенен. По лени. Вызвать Грошу — один клик мышки (вызвать Gemini — уже два, а сексуальный опыт с бо́льшим числом партнёров граничит с промискуитетом).
У такого "секретаря" есть два качества, по которым его надо оценивать: понятливость и надёжность. С надёжностью пока не самый цимес: я приводил примеры, где Гроша явно лажался, доверяя из нескольких конфликтующих версий одной. Пример, — вопрос, прекратил ли поц Митрич вести свой ЖЖ, объявив urbi et orbi в 2022 году, что-де его гэбуха закрыла. Через неделю узник совести вернулся и как ни в чём не бывало продолжил блоговать, но Гроша, зафиксировав первый пост, долго сопротивлялся моим попыткам объяснить, что не всему, что написано на сарае, можно верить. Желающие сами могут посмотреть, убедил ли я Грошу принять мою версию только для разговоров со мной, или он согласился принять её как более правдоподобную и для широкой публики. Но в любом случае много чести пиздуну Митричу.
Я хотел пофилософствовать на тему на грани между математикой и нынешними кудесниками, клепающими ИИ (прошу прощения, это не моя чашка чая, могу и наврать ненароком). В вычислительных задачах, которые сегодня предлагается решать компьютерам, есть, грубо говоря, два класса. Некоторые задачи решаются при помощи замысловатых алгоритмов: человеческий моск вряд ли справится с соответствующими вычислениями, а железный конь много мощнее крестьянской лошадки. Но некоторые задачи не решить иначе, чем полным перебором возможных вариантов, возможно, с какими-то трюками для сокращения перебираемых случаев.
Задачи первого класса — это скальпы индейцев за поясом у ковбоя. Задачи второго класса — это challenge, неуловимые Джо. Мы знаем "переборные" решения для них, но не знаем, есть ли более эффективные. Для многих таких задач доказана редуцируемость, — если мы знаем "эффективное" решение одной, то и все остальные мы сможем решить "эффективно". Эдакая круговая порука, но пока держится: ни одной такой сложной задачи мы ещё не решили.
Тут уместно отступление к школьной математике: что такое "эффективный способ решения" и что такое галимый "полный перебор". Если стоять на пальцах одной ноги, то это разница между арифметической и геометрической прогрессиями. Надеюсь, все помнят из книжек дедушки Перельмана, как быстро растут значения геометрической прогрессии аn = 2n по сравнению с арифметической прогрессией bn = 100 n. Минимальное размышление приводит к окончательному вердикту: любая экспонента обгонит любую линейную функцию. Последнее интеллектуальное усилие — и мы у цели: любая экспонента вида 1.00....01n со временем победит любую степенную функцию вида n1,000,000,.... Отсюда и оруэлловская дихотомия: полиномы — хорошо, экспоненты — плохо. Здесь, и ниже и выше, n есть некий скрытый параметр, свой для каждой задачи, читайте внимательно мелкий шрифт.
Неформально говоря, "простые" задачи — те, которые мы умеем решать "быстро", за полиномиальное время/число шагов. "Сложные" задачи — те, известные решения которых требуют экспоненциального времени, т.е., решаются, но "медленно".
Не надо думать, что четыре ноги всегда плохо, а две ноги всегда хорошо. Вот очень поучительный пример из жизни.
Есть критически важная для приложений задача линейного программирования. Геометрически она выглядит до смешного просто. В n-мерном (n — то самое большое число, параметр) пространстве задан выпуклый многогранник. Как задан? а как его можно ещё задать, системой N линейных неоднородных неравенств от n переменных, т.е. прямоугольная матрица, набитая числами. Если вы набьёте эту матрицу числами наобум, то запросто может оказаться, что пересечение пусто. Однако ж оно может оказаться и непустым (тогда его обзовут многогранником, ограниченным или нет). Выберем какое-то направление в пространстве и назначим его вертикалью (хотите — поверните пространство, если ваша личная вертикаль смотрит в другую сторону). Задача линейного программирования — найти самую "высокую" вершину на нашем многограннике.
Самое "тупое" решение задачи — перебором. Каждая вершина определяется тем, какие из неравенств, задающих многогранник, обращаются в равенство. Таких выродившихся неравенств всегда можно найти не больше чем n, даже если их исходный набор N был много больше. Решить систему из n уравнений с n переменными можно сравнительно быстро, за полиномиальное число операций, скажем, методом исключения Гаусса. Надо "просто" посчитать "высоту" каждой вершины и выбрать самую высокую. Беда в том, что без ограничения сверху на N число вершин может быть астрономическим.
Есть решение заметно лучше (за его открытие Канторович и Купманс получили нобелевку по экономике в 1975-м, работа Канторовича была опубликована в 1939-м), называется "симплекс-метод". Геометрически он тоже прост как дрозд. Выберем любую вершину многогранника (точку в n-мерном пространстве) и посмотрим на все одномерные рёбра, примыкающие к этой точке. Каждое ребро определяется системой каких-то n−1 вырожденных равенств из тех n, которые задали нашу вершину (см. выше). Для каждого ребра можно определить его наклон (положительный или отрицательный, если идти вдоль ребра от выбранной вершины). Если все наклоны отрицательные — значит, мы уже достигли самой высокой вершины на многоугольнике. Если же нет, то из всех рёбер выберем то, вдоль которого самый крутой подъём, и пойдём по нему. Мы придём в другую вершину, которая по построению выше той, с которой мы стартовали. Ну, и продолжим процесс, — рано или поздно мы дойдём со самого верха или "упрёмся" в бесконечность, если наш многогранник неограничен сверху.
Те, кто хоть чуть-чуть знаком с численными методами, узна́ют в симплекс-методе привычный градиентный поиск: чтобы найти самую высокую точку на графике функции, надо идти в том направлении, в каком эта функция возрастает быстрее всего. Но при численном градиентном поиске надо задавать массу технических параметров (с какой точностью нам нужен максимум, как определять длину шага и пр.), а в случае многогранников всё это автоматически включено в счёт.
Сколько шагов симплекс-метода нужно, чтобы в n-мерном многограннике найти самую высокую вершину? Кажется, что этот процесс должен быстро дать ответ. Однако ж высокомерные многогранники (не подумайте плохого, это просто многогранники в пространстве очень высокой размерности n) могут быть устроены очень замысловато. Оказывается, что можно искусственно соорудить высокомерный многогранник, для которого симплекс-метод требует экспоненциального числа шагов, т.е., фактически, градиентный подъём должен будет пройти почти по всем вершинам, прежде чем достигнет пика.
Однако ж такое извращение практически не наблюдаемо: в риаллайфе. Оказывается, для "выбранной наугад" матрицы чисел, задающих многогранник, симплекс-метод всегда найдёт решение за полиномиальное число шагов. Экспоненциально сложные многогранники исключительно редки (имеют меру ноль). Поэтому все линейные программисты, не раздумывая ни минуты, достанут из стандартной библиотеки стандартную программу и нажмут на пуск.
Но это ещё не конец вставной новеллы про линейное программирование. В 1979 году Леонид Хачиян открыл свой метод эллипсоидов, всегда решающий задачи линейного программирования за полиномиальное время (премия Фалкерсона за 1982 г.). С точки зрения теории, это был фундаментальный прорыв, но я не знаю ни один практический пример, когда метод эллипсоидов был бы использован. Такие дела™...
Вернёмся к нашим баранам. Есть вычислительные задачи, про которые мы знаем, что они решаются за полиномиальное время (например, задача линейного программирования). Класс таких задач обозначается Р. Но есть и задачи, для которых алгоритм решения за полиномиальное время неизвестен. Например, задача коммивояжёра требует найти на графе ("дорожном атласе") кратчайший путь по существующим дорогам, посещающий каждую вершину графа ("город"). Другая задача требует разбить вершины графа с чётным числом вершин на две равные части (например, покрасив вершины в два цвета), так чтобы число рёбер, соединяющих вершины из разных частей (разноцветных рёбер), было минимальным. При этом проверить правильность ответа, если вам его кто-то сообщает, можно за полиномиальное время. Это утверждение нетривиально: как доказать минимальность длины пути коммивояжёра или числа разноцветных рёбер, не сравнивая их с экспоненциально большим числом альтернативных вариантов, я не знаю (но с меня какой спрос!). Класс задач, в которых правильность ответа проверяется за полиномиальное время, обозначается NP.
Задача на миллион долларов (не фигурально, а вполне конкретно, одна из Проблем Тысячелетия) — а не может ли так быть, что P = NP, иными словами, что любая задача, где ответ "быстро проверяем", допускает "быстрое решение", просто мы их пока не нашли? В такой исход, насколько можно судить, не верит никто, я слышал разного рода эвристические аргументы, почему на свете существуют "действительно сложные" задачи, у которых нет быстрых решений. Вообще-то человечество практически весьма заинтересовано в том, что некоторые задачи "действительно сложные": на этом основаны все известные методы шифрования, защиты данных и т.д., которые будут очень долго устойчивы к прогрессу процессорных мощностей. В самом деле, если нынешним супербыстрым компьютерам нужно недели времени, чтобы взломать 256-битный шифровальный ключ (все числа условные), то перестроить защиту под 512-битный ключ, а то и 1024-битный — вопрос смены вывесок и небольшого увеличения времени на шифровку/дешифровку. А время, необходимое для взлома, увеличится астрономически. И наоборот, если будут найдены быстрые (полиномиальные) алгоритмы решения, то дело швах... Я уже написал выше, все известные NP-подозрительные проблемы уже включены в систему НАТО "круговой поруки": если будет найдено "быстрое" решение любой из них, немедленно появится "быстрое" решение всех остальных.
Но какое это всё имеет отношение к ИИ?Формально, конечно, никакого. Никакой ИИ, насколько я понимаю, не берётся за решение нерешаемых задач. Но есть поверхностная аналогия. В теории сложности вычислений (часть честной Theoretical Computer Science) постановкой задач занимаются люди, и именно люди играют с разными правилами игры (а что, если мы хотим найти решение с 99% вероятности? а что, если нам для счастья хватит не абсолютного максимума/минимума, а со скидкой в 1% от цены? (попробуйте понять разницу между двумя постановками вопроса, это поучительно).
А у бездельников, таких, как я, любая проблема разбивается не на два этапа (как решить и как проверить решение), а на три. Самый трудный — объяснить ИИ-собеседнику, чего мне надо. Пока Гугль был единственным кандидатом на поговорить, это было целое искусство. Гуглю надо было (а) выбрать язык, на котором скорее всего можно найти ответ (особенно это касается новостей и местных реалий), (б) подобрать нужный набор ключевых слов для поиска (сраный pagerank algorithm выдавал радикально разные наборы ответов в зависимости от порядка слов в запросе), и (в) среди первых пары десятков найденных ссылок (дальше никогда не ходил) попытаться найти релевантные, а не проплаченные. С другой стороны, дружище Гуголь не нёс отсебятины, а честно приводил только результаты поиска. Дальнейшее (проверка правильности ответа) сводилась к метазадаче — насколько достоверен источник, найдённый Гуголем.
Нынешние ИИ (я в основном общаюсь с Грошей) радикально упростили первую из трёх фаз. Он понимает вопросы (по-английски, по-русски и на иврите) практически безупречно, выдавая мне ответы именно на то, о чём я спрашивал. Вертит жопой ("с одной стороны... с другой стороны...") он довольно редко, но прикрывает жопу ссылками на конфликтные версии. Случаев прямого вранья (Гроша говорит, что-де он не знает конкретных высказываний разных имяреков на интересующую меня тему) было крайне мало, и когда я тыкаю Грошу мордочкой в то, что якобы неизвестно, он придумывает вежливые отмазки.
В общем, ситуация в чём-то аналогичная проблеме тысячелетия. Задача поиска Гуглем вполне могла быть описана как экспоненциально сложная (для человека): перебором искать ту комбинацию ключевых слов, которая выведет Гугля на нужный след, можно было очень долго. Но зато Гугль почти не врёт: врать могут сайты, на которые он ссылается, но это уж только человеческий интеллект может решать, доверять или не доверять. А вот Гроша, напротив, понимает вопрос с полуслова, и почти всегда правильно, зато ответы надо проверять, — врёт-съ, подлец. Но если не ставить его в неловкое положение, когда ответ на заданный вопрос очевидно зависит от того, кого спрашивать, — он очень надёжен. Больше всего он Гроша мне помогает с историческими датировками недавних и давних событий.
Интересно, научится ли когда-нибудь ИИ самостоятельно мерить степень доверия к разным источникам. Я спросил Грошу, откуда растут ноги у конспиративной теории, что-де американцы не летали на Луну. Вот его ответ. Вполне повод для скромного оптимизма.
Теория заговора о том, что американцы не летали на Луну, основывается на ряде аргументов, которые сторонники этой идеи считают доказательствами фальсификации. Однако большинство этих доводов опровергаются научными фактами и объективными данными. Вот основные основания, которые приводят сторонники теории, и краткое объяснение их несостоятельности: - Отсутствие звезд на фотографиях с Луны
Аргумент: На снимках с поверхности Луны, сделанных астронавтами, не видно звезд на небе, что кажется подозрительным. Опровержение: Это объясняется настройками камер. Из-за яркого освещения поверхности Луны солнцем камеры астронавтов были настроены на короткую выдержку, чтобы запечатлеть детали грунта и объектов. Звезды, которые гораздо тусклее, просто не попали в кадр из-за переэкспозиции. - Колыхание флага в вакууме
Аргумент: Американский флаг на видео кажется развевающимся, хотя на Луне нет атмосферы, и, следовательно, ветра. Опровержение: Флаг колыхался из-за отсутствия атмосферы. В вакууме нет сопротивления воздуха, поэтому движения ткани, вызванные действиями астронавтов (например, при установке флага), продолжались дольше. Кроме того, флаг был закреплен на проволочном каркасе, что создавало эффект "волн". - Тени и освещение
Аргумент: На фотографиях тени выглядят странно, иногда кажутся параллельными или имеют "неправильные" углы, что наводит на мысль о студийном освещении. Опровержение: Необычные тени объясняются неровной поверхностью Луны и рассеянным светом от грунта. Солнце было единственным источником света, но рельеф и отражение света от поверхности создавали сложные теневые эффекты. Эксперименты с моделированием освещения подтверждают естественность таких теней. - Отсутствие кратера под лунным модулем
Аргумент: Лунный модуль должен был оставить заметный кратер от двигателей при посадке, но на снимках этого нет. Опровержение: Двигатели лунного модуля работали на низкой тяге в последние моменты посадки, а лунный грунт (реголит) очень плотный. Вместо кратера образовалось лишь небольшое углубление и разлет пыли, что соответствует фотографиям. - Радиация в поясах Ван Аллена
Аргумент: Пояса Ван Аллена, зоны высокой радиации вокруг Земли, якобы сделали бы полет человека на Луну невозможным из-за смертельной дозы облучения. Опровержение: Астронавты пересекали пояса Ван Аллена быстро, минимизируя воздействие радиации. Корпус корабля и траектория полета были рассчитаны так, чтобы снизить дозу облучения до безопасного уровня. Измерения показали, что астронавты получили дозы, сравнимые с несколькими рентгеновскими снимками. - Отсутствие независимых подтверждений
Аргумент: Никто, кроме США, не подтвердил факт высадки, а СССР якобы "молчал". Опровержение: СССР отслеживал миссии "Аполлона" и не оспаривал их успех. Лунный грунт, привезенный астронавтами, был передан для изучения ученым из других стран, включая СССР, и его состав подтвержден как лунный. Кроме того, современные спутники, такие как индийский "Чандраян" и китайские аппараты, сфотографировали следы миссий "Аполлон" на Луне. - Технологические ограничения
Аргумент: В 1960-х годах технологии якобы были недостаточно развиты для полета на Луну. Опровержение: Программа "Аполлон" была результатом огромных инвестиций (около $25 млрд, что эквивалентно $150 млрд сегодня) и работы сотен тысяч инженеров. Ракета "Сатурн-5", компьютеры и другие технологии были специально разработаны для этой задачи. Их работоспособность подтверждена многочисленными испытаниями. - "Студийные" доказательства
Аргумент: Некоторые утверждают, что фотографии и видео похожи на постановку, ссылаясь на слухи о съемках в Голливуде или участии режиссера Стэнли Кубрика. Опровержение: Это спекуляции без доказательств. Сложность постановки такого масштаба (с участием тысяч людей, созданием реалистичных декораций и фальсификацией телеметрии) была бы не меньшей, чем реальный полет. История с Кубриком основана на вымышленных интерпретациях его фильмов, а не на фактах.
Дополнительные доказательства реальности миссий "Аполлон": - Более 380 кг лунного грунта, чей состав отличается от земных пород и метеоритов.
- Отражатели, установленные на Луне астронавтами, до сих пор используются для лазерной локации с Земли.
- Записи телеметрии, радиопереговоров и видео, которые невозможно было подделать в 1960-х годах.
- Снимки мест посадок, сделанные современными спутниками.
Почему теория заговора популярна? Она подпитывается недоверием к властям, холодной войной и желанием найти простые объяснения сложным достижениям. Однако научные данные и независимые проверки подтверждают, что высадка на Луну была реальной.
|
|
|