В чем состоит особенность логического программирования

Роль логического программирования, и стоит ли планировать его изучение на 2021-й

Логи́ческое программи́рование — парадигма программирования, основанная на автоматическом доказательстве теорем, а также раздел дискретной математики, изучающий принципы логического вывода информации на основе заданных фактов и правил вывода. Логическое программирование основано на теории и аппарате математической логики с использованием математических принципов резолюций.

Итак, пришло время второй ссылки. Что это будет? Статья на Хабре? Может быть статья на ином ресурсе? Прочитав пару первых абзацев на разных сайтах, вы, скорее всего, мало что поймете, так как, во-первых, материал обычно ориентирован на знающего читателя, во-вторых, хорошей и понятной информации по теме не так много в русскоязычном интернете, в-третьих, там почему-то постоянно речь идёт о некоем «прологе» (речь о языке программирования Prolog, разумеется), но сам язык, кажется, использует мало кто (почётное 35 место в рейтинге TIOBE). Однако наш герой не теряет мотивации и, спустя некоторое время, натыкается на эту самую статью, желая, все-таки понять:

Что такое логическое программирование

Какова история его создания и фундаментальные основы (серьезно, какому новичку это может быть интересно?)

Зачем и где его применяют

Стоит ли лично вам его изучать

Что ж, постараюсь ответить просто и понятно, обходя страшные термины и не вспоминая исторических личностей.

Что такое логическое программирование

В школе на уроках информатики многие, если не все, слышали про Pascal (а кто-то даже писал на нем). Многие также могли слышать про Python, C/C++/C#, Java. Обычно программирование начинают изучать именно с языков из этого набора, поэтому все привыкли, что программа выглядит как-то так:

Этот яркий, но малоинформативный пример призван показать, что обычно команды выполняются одна за другой, причем мы ожидаем, что следующие инструкции (команды) могут использовать результат работы предыдущих. Также мы можем описывать собственные команды, код которых будет написан подобным образом. Остановимся на том, что как завещал Фон Нейман, так компьютер и работает. Машина глупа, она делает то, что скажет программист, по четкому алгоритму, последовательно выполняя инструкции. Не может же, в конце концов, компьютер, подобно мыслящему живому существу, делать выводы, строить ассоциативные ряды… Или может?

Давайте устроимся поудобнее рядом со своим компьютером и порассуждаем о жизни и смерти вместе с Аристотелем:

Следовательно, Сократ смертен.

Звучит логично. Но есть ли способ научить компьютер делать выводы как Аристотель? Конечно! И вот тут мы вспомним о Prolog-e, который так часто мелькает при поиске информации о логическом программировании. Как несложно догадаться, Prolog (Пролог) является самым популярным чисто логическим языком программирования. Давайте рассуждения об этом языке оставим на следующие разделы статьи, а пока что продемонстрируем «фишки» логических языков, используя Пролог.

Напишем небольшую программу, где перечислим, кто является людьми (ограничимся тремя) и добавим правило «всякий человек смертен»:

Что ж, давайте спросим у компьютера, смертен ли Сократ:

Компьютер выдал нам сухое «true», но мы, конечно, вне себя от счастья, так как вот-вот получим премию за успешное прохождение нашим умным устройством теста Тьюринга.

Предикат a от трех аргументов вернет истину, если удастся доказать истинность предикатов b, c и d. Читаются правила справа налево следующим образом: «Если b от X истинно И c от Y, Z истинно И d истинно, то a от X, Y, Z истинно».

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

Теперь начнём делать запросы к программе (всё те же предикаты):

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

Какие задачи и как можно решать с помощью логического программирования

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

Пусть производная получилась довольно громоздкой, но мы и не ставили цель её упростить. Главное, из примера видно, что правила вывода производной на Prolog-е описываются очень близким образом к их математическому представлению. Чтобы сделать подобное на привычных языках программирования, пришлось бы вводить понятие дерева выражений, описывать каждое правило в виде функции и т. д. Тут же мы обошлись 8-ю строками. Но здесь важно остановиться и задуматься: компьютер не начал работать как-то иначе, он все ещё обрабатывает последовательности команд. Стало быть, те самые деревья, которые где-то все-таки должны быть зашиты, чтобы программа работала, действительно присутствуют, но в неявном виде. Деревья эти именуют «деревьями вывода», именно они позволяют подбирать нужные значения переменных, перебирая все возможные варианты их значений (существует механизм отсечения, который является надстройкой над логической основой языка, но не будем об этом).

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

Ага…то есть Петя, Петя и ложь… Что-то не так, подумает программист и попробует разобраться. На самом деле, перебирая все варианты значений X, Пролог пройдёт по такому дереву:

Представим, что перед нами в ячейках расположены три чёрных и три белых шара (как на картинке выше), которые требуется поменять местами. За один ход шар может или передвинуться в соседнюю пустую клетку, или в пустую клетку за соседним шаром («перепрыгнуть» его). Решать будем поиском в ширину в пространстве состояний (состоянием будем считать расположение шаров в ячейках). Суть этого метода заключается в том, что мы ищем все пути длины 1, затем все их продления, затем продления продлений и т. д., пока не найдем целевую вершину (состояние). Почему поиск в ширину? Он первым делом выведет самый оптимальный путь, то есть самый короткий. Как может выглядеть код решения:

Со стороны улучшения алгоритма можно предложить использовать поиск в глубину. Но как же, он ведь не даст оптимального результата? Сделаем просто: ограничим глубину поиска. Так мы точно не забьём стек и, возможно, получим ответ. Поступим так: проверим, есть ли пути длины 1, затем длины 2, затем длины 4 и т. д. Получим так называемый поиск с итерационным заглублением:

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

С другой стороны, задачу можно было бы решить, не меняя код поиска, а лишь изменив правила перемещения шаров. Обратим внимание, что нам заранее известны входные и выходные данные. Приглядевшись становится понятно, что нет никакого смысла в движении фишек «назад». Действительно, если чёрным нужно встать в правые позиции, то какой смысл делать ходы влево? Перепишем предикаты движения:

Хм, код стал даже проще. Запустив мы убедимся, что поиск (оба варианта), во-первых, работает, во-вторых, работает быстро, в-третьих, работает быстро и выводит результат. Это успех. Мало того, что мы решили задачку, только что был создан самый настоящий искусственный интеллект. Программа получает входные данные и желаемый результат, а затем сама ищет, как его достигнуть. Да, это однозначно успех.

Зачем и где применяют логическое программирование

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

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

Стоит ли планировать его изучение на 2021-й

Тут оставлю своё субъективное мнение, разделённое на две части:

И здесь остаётся лишь пожелать продуктивного 2021-го года!

Хочется выразить особую благодарность Дмитрию Сошникову за знакомство с этой удивительной парадигмой.

Источник

Логическое программирование и кому оно нужно

Что это

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

Самым известным представителем и пожалуй самым популярным из используемых, является язык Prolog.

Prolog

auto( ‘Model’, ‘Year’, ‘Engine’, Power( ‘h.p.’, ‘kW’ ) ).

Согласитесь, такую структуру легко понять и идентифицировать параметры, а ведь это едва ли не самое сложное, что можно увидеть в Prolog.

Изначально именно поэтому ему была уготована больше просветительская участь, чем реально полезная. Но со временем Prolog оказался полезен на передовой — в создании искусственного интеллекта и при работе с базами данных. В свежем рейтинге TIOBE Prolog занял весьма достойное 38 место.

Рассмотрим основные плюсы и минусы этого языка.

Операции, совершаемые в логическом программировании всегда понятны;

Результат практически всегда не зависит от выбранного пути реализации;

Может быть использован в качестве невычислительного языка используя только выражения и факты.

Если брать за пример логического языка программирования Prolog, то на лицо невозможность создания комплексных задач. То есть в реальности логический язык может идти дополнением к процедурному, но самостоятельно используется крайне редко;

Из-за недостатка в инвестициях и простом внимании, логические языки слабо развиваются;

Кому изучать

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

Почитать

Изучение языка, а тем более целого класса языков немыслимо без чтения хороших книг. Вот некоторые из них:

Пару месяцев назад мы с вами бегло обсудили функциональное программирование, а теперь пришло время затронуть ещё один тип — логическое программирование. В некоторой литературе эти два типа часто объединяют, противопоставляя императивному, однако основные принципы всё же различны.

Что это

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

Самым известным представителем и пожалуй самым популярным из используемых, является язык Prolog.

Prolog

auto( ‘Model’, ‘Year’, ‘Engine’, Power( ‘h.p.’, ‘kW’ ) ).

Согласитесь, такую структуру легко понять и идентифицировать параметры, а ведь это едва ли не самое сложное, что можно увидеть в Prolog.

Изначально именно поэтому ему была уготована больше просветительская участь, чем реально полезная. Но со временем Prolog оказался полезен на передовой — в создании искусственного интеллекта и при работе с базами данных. В свежем рейтинге TIOBE Prolog занял весьма достойное 38 место.

Рассмотрим основные плюсы и минусы этого языка.

Операции, совершаемые в логическом программировании всегда понятны;

Результат практически всегда не зависит от выбранного пути реализации;

Может быть использован в качестве невычислительного языка используя только выражения и факты.

Если брать за пример логического языка программирования Prolog, то на лицо невозможность создания комплексных задач. То есть в реальности логический язык может идти дополнением к процедурному, но самостоятельно используется крайне редко;

Из-за недостатка в инвестициях и простом внимании, логические языки слабо развиваются;

Кому изучать

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

Почитать

Изучение языка, а тем более целого класса языков немыслимо без чтения хороших книг. Вот некоторые из них:

Источник

Что такое логическое программирование и зачем оно нам нужно

У того, кто в детстве не писал на Прологе — нет сердца, а у того, кто пишет на нём сегодня — нет мозгов. (оригинал)

Если вас всегда терзали мучительные сомнения — что за фигня это Логическое Программирование (ЛП) и вообще зачем оно нужно? То это статья для вас.

Можно по-разному разделить языки программирования на группы (часто их называют парадигмами программирования), например, вот так:

Вот эту оплошность я и собираюсь сегодня исправить.

Важнейший тезис этой статьи:

И вообще последний вам скорее всего не нужен. А вот первое вполне может быть.

Структура статьи:

В данной статье (возможно) впервые на русском языке собраны основные аспекты современного логического программирования вместе с объяснением зачем они нужны. Логическое программирование (ЛП) напрямую связано с темой моего PhD (о нем будет отдельный подробный пост). В процессе работы я заметил, что материала на русском языке практически не существует и решил заполнить этот пробел (в русской википедии даже нет статьи про ASP, которую бы стоило написать).

Отдельные части статьи могут быть не связаны с друг другом напрямую, такие какие Sketching и Problog — в некотором смысле это персональный обзор наиболее интересных тем и разработок в области логического программирования. Здесь безусловно не получится покрыть все темы связанные с ЛП — но можно считать, что это первый шаг, чтобы заинтересованный читатель погрузился в тему или представил, что ЛП за зверь такой.

Что такое Пролог и почему он вам скорее всего не нужен

Prolog (Programming in Logic, в оригинале: programmation en logique) был разработан в Марселе в начале 70-х Аленом Колмероэ. В основу языка легла процедурная интерпретация логических выражений Хорна (т.е., как именно можно машинно выполнить) утверждений вида:

И, упрощенно говоря (вот тут мы опускаем все технические детали), может быть переписано в виде логического следования:

«a» — верно, если я могу: доказать «b», доказать «c» и доказать «d».

Тогда каждая программа — это набор теорем для вывода утверждений, а каждое выражение «доказывается» (внимательный читатель конечно же заметит здесь изоморфизм Карри — Ховарда).

Задача становится чуть веселее, если добавить сюда отрицание. В Прологе оно называется negation as failure и отличается от классического отрицания в логике. В теории это звучит так: если я не смог доказать утверждение «a», то значит оно неверно. В логике такое предположение называется closed world assumption и иногда оно очень даже осмысленно.

Negation as Failure и Closed World Assumption

Представьте себе расписание автобуса 11-го маршрута города Самары, фрагмент:

Вопрос: есть ли автобус в 16:00? Его нет, потому что мы не можем доказать, что он есть согласно расписанию — т.е. расписание обладает полной картиной мира хождения 11-го маршрута в городе Самаре. Отсюда собственно и название closed world assumption — предположение о том, что весь условный мир описан данной программой — всё вне — ложно. Как правило также применяется в базах данных — кстати про них писал тут.

Пролог, как Тьюринг полный язык программирования

Вместе с еще парой интересных операторов (как например cut) из Пролога получается — Тьюринг полный язык — вкратце — если программа на прологе P вычисляет функцию f(x), то найдется программа M на любом другом Тьюринг полном языке, которая тоже вычисляет f(x). Таким образом, если вы можете решить программу на Прологе — значит и на любом другом языке (Python, Java, C, Haskell, etc) можно написать решение. Никаких чакр тут не открывается.

В целом решение задачи на Прологе раскладывается согласно Бобу Ковальски в схему

Хороший пример задачи, которая хорошо формулируется и решается на прологе, — это набор правил, согласно которому выполняется или нет определенное условие. Однако вам самим придется задать алгоритм поиска решения — что является пространством допустимых значений, в каком порядке они обходятся и тд. По сути вы моделируете задачу в виде правил вывода и с помощью правил вывода задаете процедуру поиска решения (порядок правил, cut, переход от значений в списке из тела правило в голову, и тд) и допустимое пространство решений.

Приведем в качестве примера быструю сортировку на прологе — комментарии мои, код из The Art Of Prolog (если у вас возникнет спонтанное желание читать рэп изучать Пролог, то рекомендую именно эту книгу)

Мы видим, что предикат quicksort определен для двух случаев — пустой и непустой список. Нам интересен непустой случай: в нем список [X|Xs], где X — голова списка, т.е., первый элемент (car — для тех, кому кажется, что в этой программе мало скобочек) и Xs — хвост (tail, он же cdr) разбивается на два списка Bigs и Littles — те, кто больше, и те, кто меньше, Х. Затем оба этих списка рекурсивно сортируются и объединяются в финальный выходной список Ys. Как мы видим в целом мы задаем правилами вывода работу всего алгоритма.

Чем хорош пролог? У него хорошо с формальной семантикой — т.е. можно формально показывать свойства (например доказать, что программа выше и правда сортирует числа), хорошо расширяется на вероятностный случай (см. раздел ProbLog) и вообще хорошо расширяется, удобный язык для моделирования логических задач, хорошо подходит для математических работ, для мета-языковых операций и тд.

Вкратце, если вы не пишите научную работу, где вам нужно формально показать свойства поведения программы — скорее всего вам не очень нужен Пролог. Но может быть вам пригодится логическое программирование?

Зачем оно надо, или краткое введение в Answer Set Programming (ASP)

Краткое объяснение, что такое ASP:

если SAT — это assembler, то современный ASP — это C++.

Вот тут стоит начать с такой штуки, как декларативное программирование и принцип устойчивости к изменениям (elaboration tolerance principle) от Джона Маккарти (который придумал LISP, повлиял на Алгол и вообще предложил термин «Искусственный Интеллект»).

Что такое декларативный подход? Если вкратце, то мы описываем задачу и её свойства, а не как её решать. В этом случае задача чаще всего представляется в виде:

Где мы регулярно встречаемся с таким подходом? Например, в базах данных SQL — это декларативный язык запросов, а поиском ответа на этот запрос занимается СУБД. Для эффективной работы СУБД придуманы тысячи эффективных алгоритмов, данные хранятся в оптимизированном виде, всюду индексы, методы оптимизации запросов и тд.

Значит, наш новый запрос Q_updated представляется в виде базового запроса + дополнительное условие. Говоря чуть более обще, мы видим, что

Вариация Задачи = Базовая Модель + Доп Условие

А значит, что когда мы немного меняем условие задачи на какое-то дополнительное условие X, нам необходимо изменить модель (которая моделирует изначальную задачу на каком-то формальном языке — например SQL), добавив дополнительное условие C_X.

Причем тут ASP и Логическое программирование?

В чем принципиальная разница между Прологом и ASP? По сути ASP — это декларативный язык ограничений, т.е., мы задаем пространство перебора в виде специальных ограничений называемых choice rules, например:

Такие правила определяют пространство перебора — буквально читается следующим образом: для каждого X в предикате (читай здесь — во множестве) node, i.e., для каждой вершины X — должен быть верен один — единичка слева от «<" и только один — единичка справа от ">» атом color(X,C), такой что C пришел к нам из множества colors (унарный предикат colors/1).

Одной из главных особенностей ASP является то, что в ограничениях определяется, что НЕ является решением, например — рассмотрим следующее правило:

Ограничения (в научной англоязычной литературе употребляется термин: integrity constraints) — по сути, правила из самого начала статьи — только у них “пустая голова”

empty head: и на самом деле, это сокращение от правил вида:

т.е. если выполняются a_1, … a_n, то выводится “ложь” и моделью это не является.
(еще точнее: false — это синтаксическая конструкция для b :- a_1, …. a_n, not b. — b выводится в предположении, что b неверно — что является противоречием).

На этом закончим теоретический экскурс и посмотрим на правило внимательнее — оно утверждает следующее: если между X и Y есть дуга, цвет Х — это Cx, а цвет Y — это Сy и Cx == Cy, то это НЕ решение.

Кстати говоря, люди знакомые с ASP, скорее всего записали бы это правило так:

Переменные с одинаковым именем внутри одного и того же правила — считаются равными (и скорее всего это поможет на этапе grounding — но это отдельная история).

Перейдем к описанию всей задачи в целом (и еще парочке).

Разбираем пару популярных комбинаторных задач: NP-полных и не очень

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

Мы поговорим о следующих задачах:

И решим каждую из них с помощью ASP, а заодно и разберем основные приемы моделирования.

Раскраска графа

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

Выход:

(картинки взяты отсюда)

Основные конструкции ASP кода мы уже разобрали — пройдемся по остальным элементам: node/1 (node(a). node(b). ) — объявляет множество вершин графа, порядок не важен, edge/2 — объявляет дуги. Такие атомы в ASP (и логическом программировании) называются — фактами, фактически это сокращение от “a :- true.”, а выводится просто из утверждения, которое всегда верны, т.е., атомы задают данные программы.

Черно-белые королевы

Про расстановку королев (включаю эту вариацию) писал раньше подробнее вот здесь.

(здесь максимальное число ферзей, причем на месте крестика можно поставить белого, а на месте точке черного — но не обоих сразу; взято из статьи)

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

Далее нам нужно объявить пространство поиска:

Далее мы описываем что не является решением: если мы разного цвета на одной строке, колонке или диагонали:

По сути мы видим, что наш код хорошо раскладывается на две части: пространство поиска (guess) + валидация ответа (check) — в ASP это и называется guess-and-check парадигмой, а весь код хорошо ложится на уравнение Problem = Data + Model — в отличие от SAT, если я поменяю данные — добавлю новых королев, то сами ограничения (правила модели) не изменятся. Вообще мы могли бы переписать эти правила, чтобы они даже цвета принимали в качестве параметра.

Кратко о комбинаторной оптимизации

Суть проста: есть комбинаторная задача, как например поиск цикла Гамильтона (NP-полная задача), но сверху есть доп условие: что-то нужно минимизировать — например вес пути (количество цветов для раскраски графа, максимизировать число королев или цветов королев и тд.) Как правило это дает скачок сложности задачи и делает поиск довольно сложным. У ASP есть стандартный механизм для решения задач комбинаторной оптимизации.

Разберем задачу поиска цикла Гамильтона с оптимизацией веса пути (код из книги Answer Set Solving in Practice. Martin Gebser et al.; комментарии — мои)

По сути мы видим, что задача комбинаторной оптимизации в ASP хорошо раскладывается в декларативное уравнение:

Problem Model = Guess + Check + Minimize

Также в задаче присутствует часть вывода новых фактов (auxiliary inference), которые потом используются в ограничениях. Это также довольно стандартно для программ, написанных на ASP.

Вероятностный Prolog — ProbLog

Prolog хорош тем, что он хорошо расширяется — как язык, в том числе и на вероятностный случай — ProbLog (в шутку я читаю его всегда, как Проблох — референс к его фламандскому происхождению и тому, как его читают авторы) — Probabilistic Prolog.

Теоретические основы вероятностного логического программирования изложены в статье

A Statistical Learning Method for Logic Programs with Distribution Semantics by Taisuke Sato

(Он, кстати, еще в трезвом уме и здравой памяти — выступал на ILP 2015 в Киото — где задавал участникам много интересных и коварных вопросов)

Основные материалы по теме можно найти здесь (там же есть онлайн-редактор и tutorial, статьи и тд)

По сути представьте себе, что теперь правила пролога выводят не факт, а вероятность того, что данный факт верен, например, представим, что у нас есть набор нечестных монет, нечестных потому что вероятность выпадения орла не 0.5, а ну например 0.6 — вопрос какова вероятность выпадения орла, если мы подкинем четыре таких монетки?

В первом правиле мы описываем какие у нас есть случайные величины — это переменные, описывающие выпадение орла (сами факты о монетках — детерминированные), потом мы описываем стохастическую величину — someHeads — выпадение хотя бы одного орла, через имеющиеся у нас вероятностные величины — монетки. И последнее — это запрос: какова вероятность выпадения орла.

По сути ProbLog — это очень удобная система моделирования задач, которые представляются в виде группы правил (например бизнес логики) с вероятностным исходом.

Логическое программирование на классической логике FO(.) и IDP

FO(.) и IDP — это во многом очень схожая система с Answer Set Programming: FO(.) — First Order и (.) — референс к расширениям языка на случай индуктивных определений, агрегации и тд. А IDP — это именно система, которая поддерживает язык FO(.). Здесь и далее мы их не различаем (и вообще это отличие похоже существенно только для авторов — но там как главный идейный создатель FO(.) и IDP Марк Денекер все пять лет моего PhD указывал мне эту разницу, я решил хоть где-то провести различие между ними).

По сути вся разница в том, что вместо правил вывода в духе Пролога мы используем классическую логику. IDP также поддерживает простую систему типов.

(я бы упростил код и захардкодил liesInBlock — код из примеров редактора

Проще говоря, для каждой строки и каждого числа есть такая колонка с, что функция на ней отображает (r, c) в n. Именно это ограничение и записано в полном коде выше.

Sketched Answer Set Programming

Лишь вкратце упомяну эту идею — так как это пример одной из разработок в данной области (тем более, что моя разработка, чтобы и не упомянуть действительно). Научная область, объединяющая логическое программирование (logic programming) и машинное обучение (machine learning), ап называется Inductive Logic Programming. В ней происходит много чего интересного и это отдельная история, здесь же приведем лишь один пример связанный с ASP.

Основано на статье Sketched Answer Set Programming by Sergey Paramonov, Christian Bessiere, Anton Dries, Luc De Raedt

Представим, что вы начали изучать ASP и в качестве задания нужно решить черно белых королев — простым гуглением найдем решение на Constraint Programming языке Essense.

Если вы перепишите это ограничения один-в-один на ASP, то получится следующее:

Что безусловно неверно и будет возвращать Unsatisfiable какую бы строчку мы не убрали. Идея sketching состоит в том, чтобы пометить часть программы как «мы вот тут не уверены, что должно быть» и дать примеры, как должна себя вести программа — «вот это решение, а вот это нет»

Условно, мы не уверены в операторах арифметики и неравенствах, мы пометили их вопросом, и дали примеры, что является решением, а что нет. По ним мы можем восстановить исходную программу (как в начале статьи).

Помимо sketching люди учатся восстанавливать целые программы с нуля по примерам — но это отдельная история.

Экспериментальный анализ

В качестве прототипа решения

ASP — хорош в качестве прототипа решения сложных комбинаторных задач, особенно, если это вариация сложной задачи — например NP-полная версия N-queens — как уже описывал ранее вот здесь.

Что куда эффективнее, например, перебора с возвратом.

В качестве общего решения vs специализированный алгоритм

В свой статье Relational Data Factorization (Paramonov, Sergey; van Leeuwen, Matthijs; De Raedt, Luc: Relational data factorization, Machine Learning, volume 106) мы провели очень подробный анализ общего решения одной проблемы, для частного случая которой есть специализированные алгоритмы и в целом картина вот такая:

Специализированные алгоритмы существенно быстрее — как мы видим слева по синей и красной кривой (такой специализированный алгоритм + формулировка задачи и тд

= год труда ученых) при одинаковом качестве — синяя и красная линия справа — однако, в некоторых задачах можно использовать приближенные методы на базе ASP и пожертвовать качеством для получения выигрыша в скорости — зеленая линия.

Гибридные решения

В определенных ситуациях задача может распасться на две части: базовая формулировка задачи + дополнительные ограничения, в такой ситуации можно использовать связку:

Гибридное Решение = Специализированный Алгоритм + ASP

На ряде задач, например в случае с structured frequent pattern mining гибридные решения имеют существенное преимущество в масштабируемости (см. Paramonov, Sergey; Stepanova, Daria; Miettinen, Pauli: Hybrid ASP-based Approach to Pattern Mining, Theory and Practice of Logic Programming, 2018):

Сравнение на синтетическом датасете последовательностей (от авторов другого метода; разница работы на настоящих крупных датасетах несколько порядков — у нас десятки секунды-минуты, у них не получается вычислить все последовательности за ночь вычислений)

Так же для графовых датасетов разница еще существенней, тут сравнивается старый декларативный метод и новый гибридный (логарифмическая шкала)

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

Тестирование и корректность программ

Обычно, научные задачи, особенно комбинаторные, сложно отлаживать и еще сложнее показать их корректность. Отсюда возникают подобные проблемы в духе вот таких:

И в целом, если вы думали, что научный код обычно необычайного качества, покрыт тестами и легко поддерживается, то вот кусочек кода из LCM-k:

Одной из важных особенностей программ с формальной семантикой является доказуемость их корректности, точнее говоря, вы смещаете фокус вопроса корректности на «ASP solver», т.е. систему которая может работать с языком Answer Set Programming. Вы можете показать, что программа и правила математически корректно моделируют вашу задачу — и вопросы по верному выполнению переходят в сообщество разработчиков. У систем, как правило, открытый код — так же они хорошо покрыты тестами и ими пользуются немалая группа юзеров. В среднем, мы достаточно уверены, что с ASP системами все хорошо в плане правильного выполнения кода.

Обычно, когда на свет выходит новый алгоритм (и статья вместе с ним), мы как бы просто верим в часть помеченную «?» на схеме:

В случае с ASP — algorithm и implementation являются одним и тем же (ну если вы не обернете ASP в процедурные вызовы в алгоритме), а значит можно показать формальную корректность самого кода.

Например, это можно использовать в качестве:

Заключение

Сегодня мы многое поняли (с) — и прикоснулись к вершине айсберга логического программирования. Тезисно (tl;dr) статья умещается в несколько пунктов:

Источник