В последнее время я часто писал о вычислительной сложности, алгоритмах и моделях (например 1, 2, 3). Вычислительные модели лежат в основе вычислительной науки и не только её, и всё же немногие обладают чётким представлением о том, что такое вычислительная модель на самом деле. Это программное обеспечение? Или алгоритм? Как это связано с математическими моделями? Какие языки или обозначения подходят для описания вычислительной модели? Сделает ли ИИ вычислительные модели устаревшими? В процессе обсуждения с некоторыми товарищами сформулировалось достаточно подробное и, надеюсь, понятное описание, которое я и хотел бы представить в этой статье.
Любое научное вычисление предполагает применение одной или нескольких вычислительных моделей. Некоторые из этих моделей кажутся настолько очевидными, что иной раз трудно признать их в таком качестве. С другой стороны, некоторые модели настолько сложны, что кажутся самой сутью компьютерных наук и квинтэссенцией программного обеспечения. Существуют также разделы вычислительной науки, в частности, биоинформатика, которые делают упор на методы решения проблем, а не на модели, представляющие лежащие в их основе явления, и, как следствие, почти не затрагивают сами модели. Но модели в любом случае существуют в виде предположений об изучаемых системах, которые неявно заложены в алгоритмах решения задач.
Если свести процесс научного исследования к его основам, то он предполагает создание и итеративное совершенствование моделей, описывающих эмпирические наблюдения. Таким образом, модели и наблюдения являются основными понятиями науки. Две давние специализации многих дисциплин — это теоретик, придумывающий и совершенствующий модели, и практик, проектирующий конкретные установки для проведения наблюдений.
В науке наблюдения представляются в виде наборов данных. А модели часто представляются кодом. В некотором роде код и данные ассоциативно можно представить в качестве аналогии теории и практики. Правда, если достаточно педантично подойти к этой аналогии, то она не выдерживает критики.
Код — это технический артефакт, включающий в себя множество различных понятий, никак не связанных с моделированием природных явлений. Например, чтобы написать код, я должен выбрать язык программирования, но этот выбор совершенно не связан с явлением, которое я хочу описать с помощью моей модели. Вычислительная модель может быть реализована на любом языке программирования и должна давать одинаковые результаты независимо от этого выбора.
Но тогда что такое вычислительная модель? В идеале это частичная спецификация алгоритма или программы. Спецификации, алгоритмы и данные аналогичны уравнениям, функциям и числам в математике. В науке, основанной на математике, наблюдения — это числа, отношения между наблюдениями и параметрами — это функции, а модели — это уравнения. В вычислительной науке наблюдения — это данные, отношения между наблюдениями и параметрами — это алгоритмы и код, а вычислительные модели — это спецификации.
Математические модели в науке
Количественные математические модели играют очень важную роль в самых разнообразных научных дисциплинах, таких как физика, биология, экономика и др. Модели описывают отношения между наблюдаемыми величинами и параметрами системы, такими как время. Простейшая форма, которую может принять такое отношение, — это функция, выражающая одну величину через другие величины и параметры. Этот подход можно легко обобщить на несколько функций или одну многозначную функцию для случая нескольких зависимых величин. Модели, выраженные в виде функций, часто имеют настраиваемые параметры, значения которых определяются из наблюдений.
Двумя исторически важными примерами моделей, основанных на функциях, являются модели Птолемея и Кеплера для орбит небесных тел. Модель Птолемея описывает орбиту Солнца, видимую с Земли, как круг с наложенными друг на друга эпициклами, идея, близкая по духу к анализу Фурье. Радиусы и относительные фазы циклов являются параметрами, соответствующими наблюдениям.
Модель Кеплера утверждает, что планеты движутся по эллиптическим орбитам вокруг Солнца, которое занимает один из двух фокусов. У каждого эллипса есть два регулируемых параметра формы, которые должны быть определены из наблюдений за положением планеты. Модель Кеплера также делает количественное утверждение о скорости, с которой движутся планеты, ускоряясь по мере приближения к Солнцу и замедляясь по мере удаления от него, соблюдая то, что называется сохранением углового момента.
Исторические дискуссии описывают модель Кеплера как превосходящую модель Птолемея, потому что она определила Солнце, а не Землю, в качестве точки отсчёта для небесных орбит. Другие отличия редко обсуждаются, но самым явным фактом является то, что модель Птолемея слишком общая. Любую замкнутую кривую можно описать как суперпозицию круговых движений в духе анализа Фурье, но для хорошего приближения требуется много эпициклов и, следовательно, много параметров.
Кеплер вводит форму орбит в функциональную структуру своей модели, уменьшая количество параметров до двух. В общем, при наличии двух моделей с настраиваемыми параметрами, которые одинаково хорошо предсказывают наблюдения, модель с меньшим количеством параметров является более мощной, поскольку она фиксирует больше закономерностей данных. Это урок, который современная наука о данных только открывает заново.
Более продвинутая математическая модель состоит из уравнений, решениями которых являются функции, связывающие наблюдаемые величины и параметры системы. Поскольку функцию можно рассматривать как частный случай уравнения, в котором нет ничего неизвестного, модели, основанные на уравнениях, представляют собой надмножество моделей, основанных на функциях. В общем, уравнения — это ограничения на функции.
Уравнения являются более мощными научными моделями, чем функции, потому что они могут быть составлены произвольно. Функции, конечно, тоже могут быть составлены, но не произвольно. Вы можете объединить две функции, но значение одной функции должно быть действительным аргументом второй функции. Уравнения же можно просто свалить в кучу. В худшем случае эта куча не имеет решений или их слишком много, чтобы представлять практический интерес.
Каждое уравнение может фокусироваться на одном конкретном аспекте общей модели. Таким образом, использование уравнений делает математические модели модульными. Большая часть информации, которую дают такие модели, исходит из изучения составляющих её уравнений.
Хорошей иллюстрацией является модель небесной механики Ньютона, которая улучшила эллипсы Кеплера. Система состоит из комбинации двух уравнений. Одним из них является общий принцип (классической) механики: сила, действующая на объект, равна произведению его массы на его ускорение. Другое уравнение — это закон тяготения, который гласит, что две массы притягиваются друг к другу с силой, пропорциональной каждой массе и обратно пропорциональной квадрату расстояния между ними. Именно это разделение на общий принцип, применимый ко многим другим ситуациям, плюс описание конкретных взаимодействий превратило классическую механику в одну из самых успешных и практически важных научных теорий всех времен.
Эллипсы Кеплера — это частное решение уравнений Ньютона. Но уравнения Ньютона выходят далеко за рамки этих эллипсов, даже если мы рассматриваем только небесную механику. Уравнения показывают, что эллипсы являются точным решением только для одной планеты, вращающейся вокруг одной звезды. В нашей многопланетной Солнечной системе эллиптические орбиты являются лишь приближением, полезным, если гравитационное притяжение между планетами достаточно мало, чтобы им можно было пренебречь.
Более того, уравнения Ньютона подсказывают, как улучшить решения, принимая во внимание эти взаимодействия, и показывают, что существуют и неэллиптические решения: параболические орбиты небесных тел, прибывающих из бесконечного пространства и никогда не возвращающихся к месту своего происхождения. Наконец, уравнения Ньютона позволяют вывести законы сохранения, т. е. для энергии и углового момента, которые значительно облегчают рассуждения о возможных решениях даже без их детального расчета.
Этот пример небесной механики иллюстрирует, как модели функций и модели уравнений обычно играют разные роли в науке. Функции, обычно с подобранными параметрами, используются для обобщения наблюдений в компактной форме и отделения закономерностей от неизбежных шумов или ошибок в любом измерении. Такая описательная модель может использоваться для вычисления теоретических значений прошлых и будущих наблюдений. Но его нельзя обобщить на похожие, хотя и не идентичные ситуации. Модели уравнений обычно описывают наблюдения как результат предположительно более фундаментальных механизмов, таких как кинетика и гравитация, которые применимы в гораздо более широком диапазоне ситуаций.
Алгоритмы и спецификации
В области вычислений эквивалентом математической функции является алгоритм. Он принимает элементы данных в качестве входных параметров и создаёт один или несколько элементов в качестве выходных. Таким образом, входные данные соответствуют аргументам функции, а выходные данные — значению функции. Это наводящее на размышления соответствие является причиной того, что многие языки программирования используют термин «функция» для элементов кода, реализующих алгоритм. Однако он точен только в том случае, если больше ничего не делает, кроме как возвращает свои выходные данные. При этом условии функции и алгоритмы можно считать почти синонимами в контексте научных моделей, оставляя в стороне в основном теоретические тонкости, связанные с проблемой вычислимости действительных чисел. Сняв условие об отсутствии эффекта, кроме возврата выходных данных, мы, таким образом, обнаруживаем, что алгоритмы являются обобщением функций.
Общепринятое мнение состоит в том, что вычислительные модели являются алгоритмами. Многие, если не большинство вычислительных моделей, используемых сегодня, действительно являются алгоритмами, потому что они получены из математических моделей как алгоритмы решения. Но сразу возникает другой вопрос: есть ли что-то эквивалентное уравнениям в области вычислений?
Если немного поразмыслить, то определённо можно дать положительный ответ, и это что-то — спецификация. Она описывает, что должен делать алгоритм или программа. Подобно набору уравнений, спецификация состоит из ограничений поведения алгоритма или программы.
Фактически, уравнения — одна из возможных форм ограничения алгоритма, и поэтому спецификация — это обобщение набора уравнений в том смысле, что оно допускает большее количество типов ограничений. Спецификации бывают формальные и неформальные.
Они являются крайностями одной шкалы, а не чётко отдельными категориями. Формальная спецификация выражается формальным языком, синтаксис и семантика которого точно определены, что делает его пригодным для машинной обработки. Неформальная спецификация — это текст, написанный для человека, правда, чтобы стать спецификацией, имеющей какую-либо практическую ценность, описание должно быть максимально точным. Между двумя крайностями есть полуформальные спецификации — категория, включающая в себя большую часть традиционной математики. Полуформальные спецификации поддаются формальным рассуждениям (например, умножение обеих частей уравнения на одно и то же число даёт одинаково верное уравнение), но набор применимых правил зависит от контекста и сам по себе не формализован, как это должно было бы быть для того, чтобы стать частью компьютерной программы. Это одна из причин, по которой формализация научных моделей часто приводит к лучшему пониманию и созданию полезных вычислительных инструментов.
Алгоритмы обычно формулируются как неформальные текстовые или как полуформальные спецификации, часто называемые псевдокодом. При выражении на языке программирования алгоритм становится исполняемым, и тогда мы называем его программой. Однако, как я писал выше, спецификации — это более общее понятие, чем алгоритмы. Таким образом, можно иметь неисполняемые формальные спецификации, являющиеся лишь ограничениями результатов работы программы. Для этого требуются специальные формальные языки, называемые языками спецификаций, которые могут выражать как алгоритмы, так и ограничения на них. В разработке программного обеспечения формальные спецификации в основном используются для проверки того, что программа ведёт себя так, как ожидается, с помощью формальных доказательств, тестов или других методов.
Роль спецификации состоит в том, чтобы обеспечить формулировку ожидаемого поведения программной системы, которая проще и понятнее пользователю, чем реализация на каком-либо языке программирования. В качестве примера рассмотрим задачу сортировки списка. Спецификация этой задачи такова: создать новый список, элементы которого совпадают с элементами входного списка и отсортированы. В спецификации не говорится, как должен быть построен этот новый список, и действительно существует множество возможных решений, включая хорошо известные алгоритмы сортировки, такие как qsort или пузырьковая сортировка. Дополнительные ограничения (например, затрагивающие использование ресурсов вычислительной машины) можно добавить в спецификацию, чтобы сузить набор приемлемых решений. Хотя в настоящее время спецификации в основном используются для проверки программ, существуют также формализмы для получения исполняемого кода из формальной спецификации.
По духу они подобны методам, разработанным математиками для поиска решений уравнений. Одним из примеров является формализм Бёрда-Миртенса (BMF, он же Squiggol). Формальные спецификации являются хорошей основой для определения вычислительных моделей по нескольким причинам:
могут быть обработаны компьютерами,
содержат математические уравнения, выраженные на подходящем формальном языке,
содержат явно сформулированные алгоритмы как частный случай, а значит, и вычислимые математические функции,
сохраняют модульность систем уравнений.
Наиболее важным препятствием для использования формальных спецификаций в вычислительной технике является отсутствие языков спецификации, подходящих для этого варианта использования. В отличие от огромного количества языков программирования, используемых сегодня, существует очень мало языков спецификаций, имеющих узкую прикладную направленность в разработке программного обеспечения. Сегодня вычислительные модели в науке обычно имеют два несвязанных представления: неформальную и, как правило, неполную спецификацию в виде текста, и исполняемую реализацию в виде вычислительного инструмента, в которой утрачивается модульность спецификации.
Производные и нативные вычислительные модели
Большинство используемых сегодня вычислительных моделей основано на математических моделях. В простейшем случае, который представляет собой математическую модель, уже сформулированную как вычислимая функция, это включает только аппроксимацию действительных чисел в математической модели числами с плавающей запятой.
Типичным примером является линейная регрессия, другой — вычисление интеграла по формуле Симпсона. Замена действительных чисел числами с плавающей запятой может показаться тривиальной, и некоторые языки программирования поддерживают это впечатление тривиальности, называя числа с плавающей запятой «реальными». Однако эта замена является нетривиальной аппроксимацией, требующей учёта влияния конечной точности и неассоциативных вычислений.
Другой распространенный тип производной вычислительной модели вычисляет численное решение для набора уравнений. Целые подобласти вычислительной науки и техники, например, вычислительная гидродинамика, основаны на вычислительных моделях, полученных из дифференциальных уравнений с помощью схемы дискретизации.
Получение алгоритмов численного решения математических уравнений является предметом численного анализа, области исследований, которая появилась на много столетий раньше, чем компьютеры. Действительно, численные решения математических уравнений вычислялись вручную почти с момента зарождения науки, потому что зачастую это был единственный доступный метод получения чисел, которые можно было сравнить с наблюдениями. Компьютеры же привели к развитию альтернатив численному анализу для получения вычислительных моделей из математических уравнений.
Наиболее известным методом такого рода является метод Монте-Карло для вычисления интегралов путём их интерпретации как плотностей вероятностей. Другим примером являются решёточные газовые автоматы (lattice gas automata) и метод решёточных уравнений Больцмана, которые представляют собой методы решения уравнений гидродинамики путём моделирования динамической системы в удобной для компьютеров форме (движение частиц по решётке с применением простых правил). Средними значениями можно показать, что в достаточно больших областях пространства и времени моделируемая жидкость ведёт себя так же, как реальная. Эти модели были инспирированы клеточными автоматами, которые, возможно, были первыми цифровыми нативными моделями, т. е. вычислительными моделями, разработанными без каких-либо ссылок на традиционные математические модели, на основе идей, разработанных в 1940-х годах. Подробнее можно почитать у Стивена Вольфрама в «Науке нового типа» (A New Kind of Science), там он описывает вычислительные модели, основанные на клеточных автоматах, для различных природных явлений.
Другой класс цифровых нативных моделей предлагает агентное моделирование. Подобно клеточным автоматам, они являются объяснительными моделями, используемыми в симуляциях, из которых в конце вычисляются наблюдаемые величины. Агентная модель описывает поведение системы, сосредоточиваясь на её составляющих, называемых агентами, и их взаимодействиях с другими агентами, выраженных в виде набора правил. Очень интересный метод моделирования, имеющий множество коммерческих и технологических приложений.
Описательные цифровые модели в последнее время привлекают большое внимание. Их формулирование и использование в принципе и есть data science. Одним из популярных семейств моделей в этой категории являются сетевые модели. Они описывают некоторые сущности как узлы графа, а отношения между сущностями — как рёбра графа. Сущности могут быть физическими (молекулы, люди, города и т. д.) или символическими (например, научные статьи в графе цитирования), а отношения могут быть качественными или количественными, описываемыми взвешенными ребрами. Сетевые модели изучаются методами теории графов и дают в основном статистические выводы о важности и роли различных объектов или групп объектов в сети.
Ещё одно важное семейство моделей в data science — ML модели. В этом семействе наиболее известным типом модели является нейронная сеть. Её не следует путать с сетевой моделью, описанной выше. В сетевой модели сама сеть представлена как структура данных, тогда как в нейронной сети представляет отношения между небольшими математическими функциями, часто называемыми искусственными нейронами.
В принципе, нейронная сеть — это просто математическая функция с очень большим количеством настраиваемых параметров. Однако способ использования нейронных сетей сильно отличается от традиционных моделей математических функций. В последнем случае функциональная форма кодирует научные гипотезы модели, а параметры служат только для тонкой настройки общей модели на конкретную систему. Напротив, нейронная сеть по своей конструкции может представлять практически любую функцию, что доказывает теорема Цыбенко (универсальная теорема аппроксимации). Таким образом, сама по себе нейронная сеть вообще не содержит научной гипотезы. Обучение сети на наборе данных наблюдений больше похоже на сжатие данных с потерями, чем на традиционную подгонку функций, а вычисление прогнозов из обученной сети аналогично интерполяции и экстраполяции приближения к исходному набору данных.
Однако методы машинного обучения быстро развиваются, и интеграция априорной информации, такой как физические законы, является одной из основных стратегий улучшения нейронных сетей. Один из способов сделать это — через архитектуру сети, т. е. паттерны связей между нейронами. Свёрточные сети были первой такой специализированной архитектурой, предназначенной для обработки изображений. Они обеспечивают трансляционную инвариантность, тем самым гарантируя по конструкции, а не в результате процесса обучения, что, например, кот распознаётся одинаково независимо от того, находится он в правом верхнем углу изображения или в центре. Рекуррентные сети также навязывают определённую архитектуру для моделирования последовательных данных.
Более поздний метод, дифференцируемое программирование, допускает произвольные комбинации числовых функций, выраженных кодом, и числовых функций, выраженных нейронными сетями. Большие языковые модели, недавно нашедшие своё применение в программном обеспечении для широкой публики, накладывают некоторые базовые структуры человеческих языков на нейронную сеть, позволяя ей изучать последовательности фраз, содержащие ссылки друг на друга.
Другой подход к внедрению предварительных знаний в нейронные сети — это модификация функции потерь, используемой при обучении. Функция потерь — это величина, которую процесс обучения стремится минимизировать. Основным компонентом построения функции потерь является отклонение прогнозов сети от обучающих данных.
Нейронные PINN-сети (Physics-informed neural networks) добавляют ещё один термин, который измеряет, насколько предсказание отклоняется от заданных физических законов, обычно представляющих собой дифференциальные уравнения. Это отличается от подхода сетевой архитектуры тем, что априорные знания используются в качестве мягкого, а не жёсткого ограничения. Все эти методы уже исследуются учёными во многих дисциплинах с целью выявления их сильных и слабых сторон. Параллельно с этим эпистемологический статус моделей машинного обучения в науке является предметом споров и, вероятно, ещё долгое время будет занимать умы. Простые нейронные сети не содержат научных гипотез, а это означает, что они не являются научными моделями. Но более продвинутые сетевые структуры поднимают вопрос о том, имеет ли смысл традиционное разделение моделей и наблюдений.
Подходящие параметры как гибридные объекты, зависящие как от моделей, так и от наблюдений, веками играли важную роль в науке. Более того, конструкция любой экспериментальной установки зависит от входных данных моделей. Таким образом, данные всегда каким-то образом зависели от моделей. С машинным обучением мы получаем модели, которые ещё сильнее зависят от данных. Мы можем делать прогнозы, используя эти модели, но вопрос извлечения из них достоверной научной информации, остаётся открытым.
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
— 15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.