Логика вероятности и вероятностная логика тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

О050ои«>■

На правах рукописи

Сперанский Станислав Олегович

ЛОГИКА ВЕРОЯТНОСТИ И ВЕРОЯТНОСТНАЯ ЛОГИКА

01.01.06 — математическая логика, алгебра и теория чисел

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

1 * МАР 2013

Новосибирск-2013

005050677

Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального

образования «Новосибирский национальный исследовательский

государственный университет».

Научные руководители:

доктор физико-математических наук Витяев Евгений Евгеньевич-, доктор физико-математических наук Одинцов Сергей Павлович.

Официальные оппоненты:

Селиванов Виктор Львович, доктор физико-математических наук, профессор, Федеральное государственное бюджетное учреждение науки Институт систем информатики им. А. П. Ершова Сибирского отделения Российской академии наук, главный научный сотрудник;

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

Ведущая организация: федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Омский государственный университет им. Ф.М. Достоевского».

Защита диссертации состоится 25 апреля 2013 г. в 15 час. 30 мин. на заседании диссертационного совета Д 003.015.02 при Федеральном государственном бюджетном учреждении науки Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук по адресу: 630090, Новосибирск, пр. Академика Коптюга, 4.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук.

Автореферат разослан «_/_/» ^ 201

Ученый секретарь диссертационного совета кандидат физико-математических наук

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Одним из актуальных направлений исследований в современной математической логике и теоретической информатике является вероятностная логика (см., например, [8, 9, 14, 15, 18, 22, 25]), чья цель — введение в рассмотрение и дальнейшее изучение разнообразных языков для рассуждений о вероятностях. Исторически, однако, становлению указанного направления предшествовал ряд дискуссий о возможностях создания индуктивной логики (или логики вероятности; см. [6, 11, 13, 19, 24]), задачи которой, а также суть взгляда на роль вероятности существенно отличались от приведённой выше формальнологической позиции. Настоящая работа посвящена изучению математической стороны обоих этих подходов, что естественным образом нашло отражение в стуктурном разбиении диссертации на две главы. Опишем теперь каждое из направлений несколько более подробно.

Вначале рассмотрим второе из упомянутых направлений — это соответствует историческому ходу событий. Индуктивная логика (в отличие от вероятностной) ставит во главу угла проблему индуктивного синтеза непротиворечивых теорий, пропозициональных или первопорядковых, на основе специальных вероятностных критериев [6, 12, 13]: решение данной проблемы должно было способствовать созданию «логики научного открытия», важность которой как для философии науки, так и для практики хорошо осознавалась многими исследователями [6, 11, 20].

Проблема индуктивного синтеза (логически) непротиворечивых теорий порой именуется проблемой статистической двусмысленности вероятностных предсказаний. С целью её решения К. Гемпелем было выдвинуто требование максимальной специфичности [12], применяемое к правилам в языке, когда над последним задано конкретное вероятностное распределение (см., например, [22]). Однако поскольку требование специфичности у К. Гемпеля носит довольно неформальный характер, интерес представляет рассмотрение его формальных версий, для которых непротиворечивость соответствующих теорий может быть установлена. Кроме того, для таких версий обосновано изучение вычислительных аспектов сопутствующих понятий и, в частности, вопроса о разрешимости свойства максимальной специфичности. Отметим, что варианты формализации (требования специфичности), предложенной в [27] и впоследствии развитой в [39, 40, 43], использовались в прикладных исследованиях по экономике, биоинформатике и медицине (см. обширную

библиографию в [1]), а также по когнитивным наукам (дополнительно см. [41, 42]). Такие варианты и изучаются в главе 1.

Напротив, в качестве главной задачи в вероятностной логике выступает изучение (фрагментов) самого языка теории вероятностей логическими средствами. Разумеется, появление этого направления тесно связано с аксиоматизацией исчисления вероятностей [16], позволившей погружать указанное исчисление в стандратные формальные системы для рассуждений о множествах (будь то 2РС или ЫСВ). Значит, к числу основных проблем вероятностной логики можно отнести выделение достаточно естественных фрагментов языка теории вероятностей и изучение их свойств (как теоретико-модельных, так и вычислительных).

Ядро вероятностных пространств составляют булевы алгебры, снабжённые аддитивными мерами, один из наиболее фундаментальных объектов математики. Тем не менее, хотя теоретико-модельным свойствам такого сорта метрических структур посвящено довольно большое количество литературы (см. [4, 7, 22, 28]), вычислительные особенности языков, чья семантика задаётся специальными классами этих структур, стали исследоваться относительно недавно (например, см. [3, 8, 14, 26]). Здесь, поскольку о вероятностных пространствах можно рассуждать в различных языках, особый интерес представляет изучение сравнительно слабых фрагментов теории вероятностей на предмет разрешимости, классификация возникающих алгоритмических проблем (точнее, их т-степеней) по вычислительной сложности и т. п.

С точки зрения теории вероятностей (и математической статистики), естественным и одновременно полезным выглядит обобщение известных бескванторных формализмов с разрешимой проблемой общезначимости (к примеру, таков язык из [8, раздел 5]) за счёт введения кванторов по случайным величинам. При обобщении формализма из [8] можно воспользоваться пропозициональной классической логикой для записи измеримых событий, а простейшие (бернуллиевские) случайные величины, выраженные в терминах пропозициональных формул, взять за область квантификации переменных. Получающийся язык (обозначим его прежде не изучался, однако, он весьма тесно связан со слабыми фрагментами теоретико-модельных логик Д. Хувера и Д. Кейслера [14, 15] и «чистой индуктивной логики» Д. Пэриса [19], в которых допускаются бесконечные конъюнкции и дизъюнкции особого типа. Вычислительной характеризации и его вариантов (возникающих при варьировании семантики) и посвящена глава 2.

Цель работы. Исследовать возможности построения непротиворечивых теорий первого порядка на основе версий формального требования максимальной специфичности и провести анализ алгоритмических аспектов использования данного требования. Изучить вычислительные свойства введённого автором вероятностного языка

Методы исследования. В диссертации используются методы классической теории вычислимости [21], а также теоретико-модельные подходы к разрешимости (примером служит метод относительной элементарной определимости [2]) и техника работы с определимостью в арифметике второго порядка, изложенная в [23].

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

Практическая ценность. Работа носит теоретический характер. Её результаты могут найти применение в дальнейших исследованиях по индуктивной и вероятностной логике. Кроме того, материалы диссертации могут использоваться при создании учебных курсов для студентов и аспирантов, специализирующихся в области математической логики и теоретической информатики.

Основные результаты. Получены следующие основные результаты:

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

2. Доказано, что даже если ограничиться рассмотрением пропозициональных правил, т. е. когда требование специфичности приводится в терминах пропозициональной логики, существуют рациональ-но-значные вычислимые вероятностные распределения (над пропозициональными формулами), для которых совокупность максимально специфичных правил невычислима. Согласно приведённому в работе определению, посылка любого специфичного правила лежит в специальном вычислимом множестве конъюнкций РасЬд.

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

3. Введён вероятностный язык Q5\C, естественным образом расширяющий бескванторный формализм Фэйгина-Хальперна-Мегидцо за счёт добавления кванторов по бернуллиевским случайным величинам, выраженным в терминах пропозициональных формул.

4. Найдена точная граница для разрешимости проблемы общезначимости в префиксных фрагментах языка QT-C: доказано, что проблема общезначимости для \/3-!2!Р,С-предложений разрешима, а для ЗУ-ОСРХ-предложений — неразрешима.

5. Доказано, что проблема общезначимости для ОУ-С-предложепий является П^-полной.

Первый из основных результатов опубликован в [35], второй — в [36], третий — в [37], четвёртый — в [37, 38], и пятый — в [38].

Апробация. Результаты работы докладывались на:

• семинарах «Алгебра и логика», «Автоматы и сложность вычислений», «Нестандартные логики», «Конструктивные модели» и «Теория вычислимости» Новосибирского национального исследовательского государственного университета;

• семинаре Лаборатории логических систем Института математики им. С. JI. Соболева СО РАН, -

и были представлены на международных конференциях «Мальцевские чтения» (Новосибирск, 2009, 2010, 2011) и «Logic Colloquium» (София, Болгария, 2009; Париж, Франция, 2010; Барселона, Испания, 2011), а также на международном конгрессе «Continuity, computability, constru-ctivity» (Триер, Германия, 2012) и совместном российско-американском семинаре «Вычислимость и модели» (Новосибирск, 2012).

Публикации. Основные результаты диссертации опубликованы в работах автора [29]—[38], при этом [35]—[38] являются статьями в журналах,

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

Структура и объём диссертации. Диссертация состоит из введения, двух глав, разбитых на разделы, и списка литературы. Она изложена на 109 страницах, а соответствующая библиография включает 55 наименований, в том числе 15 работ автора по теме диссертации.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

В разделе 1.1 вводится понятие (конечно-аддитивной) вероятности на Sen°a, множестве всех бескванторных предложений сигнатуры а (см. [22]): в качестве таких вероятностных мер берутся функции

¡л : Sen°a [0,1]

со свойствами

1- ЬроьФ /х(Ф) = 1;

2. Ьроь-'(ФАФ) =>• ^(ФУФ) = ¿¿(Ф)+/л(Ф).

Первое из свойств гарантирует, что тавтологии имеют единичную вероятность, а второе, как нетрудно убедиться, обеспечит наличие принципа включения-исключения относительно ¡1. Далее обсуждается семантическая интерпретация предложенного понятия (см. [8, 9]), а также его статистические истоки. Затем, фиксируя некоторую ц, мы формализуем требование максимальной специфичности над сг-правилами (последние могут включать переменные и определяются как в классическом логическом программировании [17], т.е. образуют специальный сорт универсальных сг-предложений); интуитивный смысл требования заключается в том, что посылка правила должна включать всю возможную информацию, способную увеличить его вероятностную оценку. Стоит отметить, что здесь, следуя [1, 27], вероятностная оценка правила задаётся как ин-финум условных вероятностей его основных частных случаев. Наконец,

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

В разделе 1.2 приведён пропозициональный аналог понятия вероятности на Sen°: в нем Sen° заменяется на -Forcl, совокупность всех формул в языке пропозициональной классической логики CL, а вместо Ьроь берётся bcL- Разумеется, тогда естественным образом переписывается и само формальное требование максимальной специфичности и, в целом, значительно упрощаются многие определения. Затем доказывается, что даже в такой ситуации найдутся рационально-значные вычислимые вероятностные меры (отображающие коды пропозициональных формул в коды рациональных чисел), для которых множество максимально специфичных пропозициональных правил невычислимо. С другой стороны, если Facíд — вычислимое множество «допустимых» посылок, т. е. специфичные правила ищутся в классе правил с посылками из Factл (см. подробности и обоснование в тексте), а вероятность ¿i : F or cl [0,1] принимает лишь конечное число значений на элементах FacíA, то, как несложно понять, отвечающая ц совокупность максимально специфичных правил будет вычислима. Для каждой ф из F or cl положим

ф„ := {ф е Foret I Ц (Ф -Н- ф) = 1} •

Рассмотрим несколько параметров, характеризующих «конечность» вероятностных распределений (точнее, их сужений на FactA):

• т(м) := \{ц(ф) I Ф € FacÍA и 0 < ц(ф) < 1}|;

• к, (/i) := \{фц I Ф 6 Fact л}|;

• ¿(¿i) := 1/inf {ц(ф) I ф е Fact а и р(ф)> 0}.

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

• существует алгоритм, который по каждой паре (n, q) G N х Q, где п — клиниевский номер рационально-значной вычислимой меры ц и к(ц) = q, выдаёт номер разрешающей процедуры для соответствующего множества максимально специфичных правил;

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

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

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

В разделе 2.1 описываются синтаксис и семантика для 0У£>. Пусть Prop = {pi,p2,---} — это совокупность пропозициональных символов, на основе которой строится Forcl, а ££ = {х\,х2,...} — не пересекающаяся с ней совокупность переменных. Обозначим за For ж множество всех пропозициональных формул, строящихся из элементов Prop U 3£ (вместо Prop). В качестве QJ\C-атомов выступают выражения вида

где {<¿>1,..., i/?n+m} С For ¿с, а / и д суть полиномы с рациональными коэффициентами. Тогда 0,7Z-формулы получаются из ОТ^-атомов путём замыкания относительно классических логических связок и навешивания кванторов V и 3 по переменным из 5£. Семантика бескванторных □^^-предложений стандартна и может быть найдена в [8] — поскольку такие предложения совпадают с «полиномиальными взвешенными формулами» из [8, раздел 5]. На самом деле, её нетрудно распространить и на все ОЗ^С-предложения (при этом класс «вероятностных моделей» остаётся прежним — далее эти модели будут именоваться О.УС-структурами), если Ух Ф и Эх Ф воспринимать как

Д *[х/ф] и V *[х/ф\,

1p£ForcL IpGiFor CL

соответственно (речь здесь идёт только о семантической интерпретации, т. к. в Q31C нет бесконечных конъюнкций и дизъюнкций, в отличие, например, от теоретико-модельных языков из [14, 15]). В итоге к бескванторному формализму из [8, раздел 5] мы добавили кванторы, пробегающие For cl- С другой стороны, как и в [8] и многих других работах, в

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

Затем находится точная граница для разрешимости проблемы общезначимости в префиксных фрагментах QT£: устанавливается разрешимость данной проблемы для \/3-0?£-предложений, и неразрешимость — для ЗУ-ОУ-С-предложений. Кроме того, доказывается, что в целом проблема общезначимости для Q7L будет П^-полна.

В разделе 2.2 приведён ряд обобщений результатов из предыдущего раздела на случаи, когда вероятности в семантике для QT£ подразумеваются F-значными, где F — фиксированное подполе в R. При релятивизации на F проблему общезначимости над F-значными Q'JlC-структу-рами называем проблемой F-общезначимости (и аналогично для проблемы выполнимости). Здесь устанавлены следующие общие факты:

• Проблемы F-общезначимости для УЗ-0!Р£-предложений и для бескванторных ОУ£-предложений ш-эквивалентны, а проблема F-общезначимости для ЗУ-ОР-С-предложений неразрешима.

• В целом, проблема F-общезначимости для 03>£-предложений является Щ-трудной (на самом деле, nj-трудность достигается уже на уровне 3V3V-предложений — с целью установления этого факта нами доказывается П}-полнота 3\/-теории арифметики Пресбурге-ра с единственным свободным одноместным предикатом, что обобщает результат Хальперна из [Ю]).

Более того, если ограничиться рассмотрением лишь арифметически определимых подполей, т. е. таких F ^ К, которые можно задать посредством арифметической формулы второго порядка, не содержащей кванторов по множествам (см. подробности в тексте), то F-общезначимость для QУ£ окажется не сложнее Пj, а значит, будет П}-полна.

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

Автор выражает глубокую благодарность своим научным руководителям Евгению Евгеньевичу Витяеву и Сергею Павловичу Одинцову за проявленное внимание к работе, ценные замечания и неизменно плодотворные обсуждения материала.

Список литературы

[1] Витяев Е. Е. Извлечение знаний из данных. Компьютерное познание. Моделирование когнитивных процессов. Новосибирск: НГУ, 2006. 293 с.

[2] Ершов Ю. JI. Проблемы разрешимости и конструктивные модели. М.: Наука, 1980. 416 с.

[3] Abadi М., Halpern J. Y. Decidability and expressiveness for first-order logics of probability // Inf. Comput. 1994. V. 112, No. 1. P. 1-36.

[4] Barwise J., Feferman S. (eds.) Model-theoretic Logics. Berlin: Springer, 1985. 893 p.

[5] Carnap R. A basic system of inductive logic, part 1 // Studies in Inductive Logic and Probability, Vol. 1 / Eds. R. Carnap and R. C. Jeffrey. Univ. of California Press, 1971. P. 33-165.

[6] Carnap R. The Continuum of Inductive Methods. Chicago: Univ. of Chicago Press, 1952. 92 p.

[7] Chang С. C., Keisler H.J. Continuous Model Theory. Princeton: Princeton Univ. Press, 1966. 165 p.

[8] Fagin R., Halpern J. Y., Megiddo N. A logic for reasoning about probabilities // Inf. Comput. 1990. V. 87, No. 1-2. P. 78-128.

[9] Halpern J. Y. An analysis of first-order logics of probability // Artif. Intell. 1990. V. 46. P. 311-350.

[10] Halpern J. Y. Presburger arithmetic with unary predicates is П} complete //J. Symb. Log. 1991. V. 56, No. 2. P. 637-642.

[11] Hempel C. G. Deductive-nomological versus inductive-statistical explanation // Minnesota Studies in the Philosophy of Science, Vol. 3 / Eds. H. Feigl and G. Maxwell. Univ. of Minnesota Press, 1962. P. 98-169.

Hempel C. G. Maximal specificity and lawlikeness in probabilistic explanation // Philosophy of Science. 1968. V. 35, No. 2. P. 116-133.

Hintikka J., Hilpinen R. Knowledge, acceptance, and inductive logic // Aspects of Inductive Logic / Eds. J. Hintikka and P. Suppes. Amsterdam: North-Holland, 1966. P. 1-20.

Hoover D.N. Probability logic // Ann. Math. Logic. 1978. V. 14. P. 287-313.

Keisler H.J. Probability quantifiers // Model-theoretic Logics / Eds. J. Barwise and S. Feferman. Berlin: Springer, 1985. P. 509-556.

Kolmogorov A. N. Grundbegriffe der Wahrscheinlichkeitsrechnung, Berlin: Julius Springer, 1933. 62 p.

Lloyd J. W. Foundations of Logic Programming. Berlin: Springer, 1987. 212 p.

Ng R., Subrahmanian V. S- Probabilistic logic programming // Inf. Comput. 1993. V. 101, No. 2. P. 150-201.

Paris J. Pure inductive logic // The Continuum Companion to Philosophical Logic / Eds. L. Horsten and R. Pettigrew. London: Continuum International Publishing Group, 2011. P. 428-449.

Popper K.R. The Logic of Scientific Discovery. London: Hutchinson & Co, 1959. 479 p.

Rogers H. Theory of Recursive Functions and Effective Computability. New York: McGraw-Hill, 1967. 482 p.

Scott D., Krauss P. Assigning probabilities to logical formulas // Aspects of Inductive Logic / Eds. J. Hintikka and P. Suppes. Amsterdam: North-Holland, 1966. P. 219-264.

Simpson S.G. Subsystems of Second Order Arithmetic. Cambridge: Cambridge Univ. Press, 2009. 444 p.

Suppes P. A Probabilistic Theory of Causality. Amsterdam: North-Holland, 1970. 130 p.

Terwijn S. A. Probabilistic logic and induction //J. Log. Comput. 2005. V. 15, No. 4. P. 507-515.

[26] Terwijn S. A. Decidability and undecidability in probability logic // Proceedings of Logical Foundations of Computer Science 2009, LNCS 5407 / Eds. S. Artemov and A. Nerode. Springer, 2009. P. 441-450.

[27] Vityaev E. E. The logic of prediction // Proceedings of Mathematical Logic in Asia 2005 / Eds. S. S. Goncharov, R. Downey and H. Ono. World Scientific, 2006. P. 263-276.

[28] Yaacov I. В., Berenstein A., Henson C. W., Usvyatsov A. Model theory for metric structures // Model Theory with Applications to Algebra and Analysis, Vol. 2 / Eds. Z. Chatzidakis et al. Cambridge Univ. Press, 2008. P. 315-427.

Работы автора по теме диссертации

Тезисы конференций

[29] Сперанский С. О. К вопросу непротиворечивости семантического вероятностного предсказания // Мальцевские чтения 2009, тезисы докладов, Новосибирск, Россия, Август 24-28. С. 230.

[30] Speranski S. О. On the question of consistence of the semantic /./-prediction // Bull. Symb. Log. 2010. V. 16, No. 1. P. 131-132.

[31] Сперанский С. О. О неразрешимости свойства максимальной специфичности // Мальцевские чтения 2010, тезисы докладов, Новосибирск, Россия, Май 2-6. С. 36.

[32] Speranski S. О. On undecidability of the property of maximal specificity // Bull. Symb. Log. 2011. V. 17, No. 2. P. 328-329.

[33] Speranski S. O. Complexity for probability logic with quantifiers over propositions // Maltsev Meeting 2011, Collection of Abstracts, Novosibirsk, Russia, October 11-14. P. 111.

[34] Speranski S. O. Quantification over propositional formulas in probability logic: computability issues // Bull. Symb. Log. 2012. V. 18, No. 3. P. 464-465.

Статьи в журналах и трудах конференций

[35] Сперанский С. О. О логической непротиворечивости вероятностных предсказаний // Вестник НГУ. Серия: матем., механика, информ. 2011. Т. 11, Вып. 1. С. 99-115.

[36] Сперанский С. О. О вычислительных аспектах максимальной специфичности в вероятностном объяснении // Вестник НГУ. Серия: матем., механика, информ. 2011. Т. 11, Вып. 4. С. 78-93.

[37] Сперанский С. О. Квантификация по пропозициональным формулам в вероятностной логике: вопросы разрешимости // Алгебра и логика. 2011. Т. 50, Вып. 4. С. 533-546.

[38] Speranski S. О. Complexity for probability logic with quantifiers over propositions //J. Log. Comput. 2012. doi: 10.1093/logcom/exs041

[39] Сперанский С. О., Витяев Е. Е. Синтез логики, вероятности и обучения: формализация предсказания // Сиб. электрон, матем. изв. 2009. Т. 9. С. 340-365.

[40] Vityaev Е. Е., Speranski S. О. New definition of prediction without logical inference // Proceedings of the IASTED International Conference on Computational Intelligence 2009, Honolulu, USA, August 17-19 / Ed. B.Ya. Kovalerchuk. ACTA Press, 2009. P. 48-54.

[41] Vityaev E.E., Perlovsky L.I., Kovalerchuk B.Ya., Speranski S. O. Probabilistic dynamic logic of phenomena and cognition // Proceedings of the World Congress on Computational Intelligence 2010, Barcelona, Spain, July 18-23. 2010. P. 3361-3366.

[42] Витяев E. E., Перловский JI. И., Ковалерчук Б. Я., Сперанский С. О. Вероятностная динамическая логика мышления // Нейроинформа-тика. 2011. Т. 5, №1. С. 1-20.

[43] Vityaev Е. Е., Speranski S. О. On the problem of prediction // Knowledge Processing and Data Analysis: KONT/KPP 2007, LNAI 6581 / Eds. K.E. Wolff et al. Springer, 2011. P. 280-296.

Сперанский Станислав Олегович

ЛОГИКА ВЕРОЯТНОСТИ И ВЕРОЯТНОСТНАЯ ЛОГИКА

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 08.02.13 Формат 60x84 1/16

Печать офсетная Уч.-изд. л. 1,0

Заказ № 28 Тираж 100 экз.

Редакционно-издательский центр НГУ 630090, Новосибирск, ул. Пирогова, 2

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Новосибирский национальный исследовательский государственный университет»

Сперанский Станислав Олегович

ЛОГИКА ВЕРОЯТНОСТИ И ВЕРОЯТНОСТНАЯ ЛОГИКА

01.01.06 — математическая логика, алгебра и теория чисел

диссертация на соискание ученой степени

ю

кандидата физико-математических наук

Ю со

Ю £

СО я

Ю

О О Научные руководители: С\| о

СМ д.ф.-м.н. Е. Е. Витяев,

О д.ф.-м.н. С. П. Одинцов

Новосибирск-2013

Оглавление

Введение 4

1 Логика вероятности 15

1.1 Проблема статистической двусмысленности..................15

1.1.1 Вероятность над основными предложениями .... 15

1.1.2 Требование максимальной специфичности............20

1.1.3 Теоремы непротиворечивости..........................24

1.2 Вычислительные аспекты максимальной специфичности . 36

1.2.1 Пропозициональные специфичные правила..........36

1.2.2 Вопросы разрешимости в общем случае..............40

1.2.3 Вопросы разрешимости в финитном случае..........47

1.2.4 О сложности введённых классов мер..................59

2 Вероятностная логика 63

2.1 Квантификация по пропозициональным формулам..........63

2.1.1 Основные определения..................................63

2.1.2 Вопросы разрешимости в префиксных фрагментах . 68

2.1.3 Алгоритмическая сложность проблемы общезначимости ........................................77

2.2 Обобщение: вероятностные языки над подполями в К . . . 87 2.2.1 Релятивизация ранее полученных результатов ... 87

2.2.2 О схлопывании иерархий проблем общезначимости 91

2.2.3 Рационально-значные вероятности

и диофантовы уравнения............... 97

Литература 103

Введение

Одним из актуальных направлений исследований в современной математической логике и теоретической информатике является вероятностная логика (см., например, [13, 15, 21, 22, 25, 33, 37]), чья цель — введение в рассмотрение и дальнейшее изучение разнообразных языков для рассуждений о вероятностях. Исторически, однако, становлению указанного направления предшествовал ряд дискуссий о пвозможпностях создания индуктивной логики (или логики вероятности; см. [10, 18, 20, 27, 35]), задачи которой, а также суть взгляда на роль вероятности существенно отличались от приведённой выше формально-логической позиции. Настоящая работа посвящена изучению математической стороны обоих этих подходов, что естественным образом нашло отражение в стуктурном разбиении диссертации на две главы. Обсудим теперь каждое из направлений несколько более подробно.

Начнём со второго из упомянутых направлений — это соответствует историческому ходу событий. Индуктивная логика (в отличие от вероятностной) ставит во главу угла проблему индуктивного синтеза непротиворечивых теорий, пропозициональных или первопорядковых, на основе специальных вероятностных критериев [10, 19, 20]: решение данной проблемы должно было способствовать созданию «логики научного открытия», важность которой как для философии науки, так и для практики

хорошо осознавалась многими исследователями [10, 18, 29].

/

Проблема индуктивного синтеза (логически) непротиворечивых теорий порой именуется проблемой статистической двусмысленности вероятностных предсказаний. С целью её решения К. Гемпелем было выдвинуто требование максимальной специфичности [19], применяемое к правилам в языке, когда над последним задано конкретное вероятностное распределение (см., например, [33]). Однако поскольку требование специфичности у К. Гемпеля носит довольно неформальный характер, интерес представляет рассмотрение его формальных версий, для которых непротиворечивость соответствующих теорий может быть установлена. Кроме того, для таких версий обосновано изучение вычислительных аспектов сопутствующих понятий и, в частности, вопроса о разрешимости свойства максимальной специфичности. Отметим, что варианты формализации (требования специфичности), предложенной в [39] и впоследствии развитой в [51, 52, 55], использовались в прикладных исследованиях по экономике, биоинформатике и медицине (см. обширную библиографию в [3]), а также по когнитивным наукам (дополнительно см. [53, 54]). Такие варианты и будут изучаться в Главе 1.

Напротив, в качестве главной задачи в вероятностной логике выступает изучение (фрагментов) самого языка теории вероятностей логическими средствами. Разумеется, появление этого направления тесно связано с аксиоматизацией исчисления вероятностей [23], позволившей погружать указанное исчисление в стандратные формальные системы для рассуждения о множествах (будь то ZFC или ЫСВ). Значит, к числу основных проблем вероятностной логики можно отнести выделение достаточно естественных фрагментов языка теории вероятностей и изучение их свойств (как теоретико-модельных, так и вычислительных).

Ядро вероятностных пространств составляют булевы алгебры, снабжённые аддитивными мерами, один из наиболее фундаментальных объ-

ектов математики. Тем не менее, хотя теоретико-модельным свойствам такого сорта метрических структур посвящено довольно большое количество литературы (см. [8, 11, 33, 40]), вычислительные особенности языков, чья семантика задаётся специальными классами этих структур, стали исследоваться относительно недавно (например, см. [7, 13, 21, 38]). Здесь, поскольку о вероятностных пространствах можно рассуждать в различных языках, особый интерес представляет изучение сравнительно слабых фрагментов теории вероятностей на предмет разрешимости, классификация возникающих алгоритмических проблем (точнее, их т-степеней) по вычислительной сложности и т. п.

С точки зрения теории вероятностей (и математической статистики), естественным и одновременно полезным выглядит обобщение известных бескванторных формализмов с разрешимой проблемой общезначимости (к примеру, таков язык из [13, Раздел 5]) за счёт введения кванторов по случайным величинам. При обобщении формализма из [13] можно воспользоваться пропозициональной классической логикой для записи измеримых событий, а простейшие (бернуллиевские) случайные величины, выраженные в терминах пропозициональных формул, взять за область квантификации переменных. Получающийся язык (обозначим его прежде не изучался, однако, он весьма тесно связан со слабыми фрагментами теоретико-модельных логик Д. Хувера и Д. Кейслера [21, 22] и «чистой индуктивной логики» Д. Пэриса [27], в которых допускаются бесконечные конъюнкции и дизъюнкции особого типа. Вычислительной характеризации и его вариантов (возникающих при варьировании

семантики) и посвящена Глава 2.

В диссертации используются методы классической теории вычислимости [32], а также теоретико-модельные подходы к разрешимости (при-

мером служит метод относительной элементарной определимости [4]) и техника работы с определимостью в арифметике второго порядка, изложенная в [34]. Получены следующие основные результаты:

• Доказано, что универсально аксиоматизируемые теории (в логике первого порядка), построенные с помощью формального требования максимальной специфичности, чья формулировка приведена в работе и опирается на идеи К. Гемпеля и Е. Е. Витяева, логически непротиворечивы. Предложен ряд модификаций упомянутого требования специфичности, причём для каждого случая установлена непротиворечивость соответствующих теорий. [47]

• Доказано, что даже если ограничиться рассмотрением пропозициональных правил, т. е. когда требование специфичности приводится в терминах пропозициональной логики, существуют рациональ-но-значные вычислимые вероятностные распределения (над пропозициональными формулами), для которых совокупность максимально специфичных правил невычислима. Согласно приведённому в работе определению, посылка любого специфичного правила лежит в специальном вычислимом множестве конъюнкций Fací д. Для вероятностных мер, принимающих лишь конечное число значений на элементах FactA, рассмотрено несколько вспомогательных рационально-значных параметров и установлено, знание каких из указанных параметров позволяет по клиниевскому номеру вычислимой меры с конечным числом значений на FactA эффективно строить разрешающую процедуру для соответствующей совокупности максимально специфичных правил. [48]

• Введён вероятностный язык Q7L, естественным образом расширяющий бескванторный формализм Фэйгина-Хальперна-Мегиддо за

счёт добавления кванторов по бернуллиевским случайным величинам, выраженным в терминах пропозициональных формул. [49]

• Найдена точная граница для разрешимости проблемы общезначимости в префиксных фрагментах языка Q3\£ : доказано, что проблема общезначимости для \/Э-ОТ£.-предложений разрешима, а для ЗУ-ОУ£-предложений — неразрешима. [49, 50]

• Доказано, что проблема общезначимости для ОУ£-предложений является П}-полной (более того, П}-полнота достигается уже на уровне ЗУЗ\/-предложений). [50]

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

Вышеупомянутые результаты неоднократно докладывались на:

• семинарах «Алгебра и логика», «Автоматы и сложность вычислений», «Нестандартные логики», «Конструктивные модели» и «Теория вычислимости» Новосибирского национального исследовательского государственного университета;

• семинаре Лаборатории логических систем Института математики им. С. Л. Соболева СО РАН, -

и были представлены на международных конференциях «Мальцевские чтения» (Новосибирск, 2009, 2010, 2011) и «Logic Colloquium» (София,

Болгария, 2009; Париж, Франция, 2010; Барселона, Испания, 2011), международном конгрессе «Continuity, computability, constructivity» (Триер, Германия, 2012), а также совместном российско-американском семинаре «Вычислимость и модели» (Новосибирск, 2012). Основные результаты диссертации опубликованы в работах автора [41]—[50].

Дадим краткий обзор содержания Глав 1-2.

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

В Разделе 1.1 вводится понятие (конечно-аддитивной) вероятности на Sen°, множестве всех бескванторных предложений сигнатуры о (см. [33]): в качестве таких вероятностных мер берутся функции

\i : Sen* -¥ [0,1]

со свойствами

1. hpOL Ф м(ф) = 1;

2- Ьроь^(ФАФ) => /¿(Ф УФ) = ¿х(Ф) +

Первое из свойств гарантирует, что тавтологии имеют единичную вероятность, а второе, как нетрудно убедиться, обеспечит наличие принципа включения-исключения относительно /1. Далее обсуждается семантическая интерпретация предложенного понятия (см. [13, 15]), а также его статистические истоки. Затем, фиксируя некоторую /2, мы формализуем требование максимальной специфичности над ст-правилами (последние могут включать переменные и определяются как в классическом логическом программировании [24], т.е. образуют специальный сорт универсальных сг-предложений); интуитивный смысл требования заключается

в том, что посылка правила должна включать всю возможную информацию, способную увеличить его вероятностную оценку. Стоит отметить, что здесь, следуя [3, 39], вероятностная оценка правила задаётся как ин-финум условных вероятностей его основных частных случаев. Наконец, устанавливается непротиворечивость универсально аксиоматизируемых теорий, построенных с помощью формального требования специфичности (точнее, любая такая теория аксиоматизируется множеством максимально специфичных правил в объединении со статистически значимым набором данных — см. определение в тексте). Предложен ряд модификаций упомянутого требования специфичности, причём для каждого случая доказана непротиворечивость соответствующих теорий.

В Разделе 1.2 приведён пропозициональный аналог понятия вероятности на Sen°: в нем Sen° заменяется на For cl, совокупность всех формул в языке пропозициональной классической логики CL, а вместо Ьроь берётся I-cl - Разумеется, тогда естественным образом переписывается и само формальное требование максимальной специфичности и, в целом, значительно упрощаются многие определения. Затем доказывается, что даже в такой ситуации найдутся рационально-значные вычислимые вероятностные меры (отображающие коды пропозициональных формул в коды рациональных чисел), для которых множество максимально специфичных пропозициональных правил невычислимо. С другой стороны, если FactA — вычислимое множество «допустимых» посылок, т. е. специфичные правила ищутся в классе правил с посылками из FactA (см. подробности и обоснование в тексте), а вероятность ¡i : For cl —> [0,1] принимает лишь конечное число значений на элементах FactAl то, как несложно понять, отвечающая fi совокупность максимально специфич-

ных правил будет вычислима. Для каждой ф из Fotq\_ положим

ф^ := {ф G Fora \ц(ф^<ф) = 1}.

Рассмотрим несколько параметров, характеризующих «конечность» вероятностных распределений (точнее, их сужений на FactA):

• т(ц) := \{^(ф) | ф <Е FaciA и 0 < /л (т/>) < 1}|;

• := К^м I Ф € Fac£A}|;

• i (ß) := 1/ inf {// (ф) | ф G FaciA и \i (ф) > 0}.

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

• существует алгоритм, который по каждой паре (n, q) 6 N х Q, где п — клиниевский номер рационально-значной вычислимой меры ¡1 и ас (/i) = q, выдаёт номер разрешающей процедуры для соответствующего множества максимально специфичных правил;

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

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

Глава 2 посвящена изучению вычислительных особенностей предложенного автором вероятностного языка QCP£ и его вариантов.

В Разделе 2.1 описываются синтаксис и семантика для Пусть

Prop = ...} — это совокупность пропозициональных символов,

на основе которой строится Fora, а & — {х\,х2,...} — не пересекающаяся с ней совокупность переменных. Обозначим за Forмножество всех пропозициональных формул, строящихся из элементов Prop U Ж (вместо Prop). В качестве QTL-атомов выступают выражения вида

где {</?!,... ,(/?n+m} С For%-, а / и д суть полиномы с рациональными коэффициентами. Тогда Q^L-формулы получаются из QT^-атомов путём замыкания относительно классических логических связок и навешивания кванторов V и 3 по переменным из 3£. Семантика бескванторных QT^-предложений стандартна и может быть найдена в [13], поскольку такие предложения совпадают с «полиномиальными взвешенными фор-

V

мулами» из [13, Раздел 5]. На самом деле, её нетрудно распространить на все ОУ£-предложения (при этом класс «вероятностных моделей» остаётся прежним — далее эти модели будут именоваться О,1?L-структурами), если УжФ и ЗггФ воспринимать как

д ф[х/ф] и v

ip^Forci фЕРог cl

соответственно (речь здесь идёт только о семантической интерпретации, т. к. в Q7L нет бесконечных конъюнкций и дизъюнкций, в отличие, например, от теоретико-модельных языков из [21, 22]). В итоге к бескванторному формализму из [13, Раздел 5] мы добавили кванторы, пробегающие F or а. С другой стороны, как и в [13] и многих других работах, в семантике QT,£ элементам ф £ Fotql сопоставляются измеримые события вероятностного пространства (подробности см. в тексте), а потому нами фактически вводится обогащение вышеуказанного бескванторного

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

Затем находится точная граница для разрешимости проблемы общезначимости в префиксных фрагментах устанавливается разрешимость данной проблемы для УЗ-ОУ^-предложений, и неразрешимость — для 3\/-<2У,£-предложений. Кроме того, доказывается, что в целом проблема общезначимости для будет П];-полна.

В Разделе 2.2 приведён ряд обобщений результатов из предыдущего раздела на случаи, когда вероятности в семантике для подразумеваются F-знaчными, где F — фиксированное подполе в М. При релятивизации на № проблему общезначимости над 1Р-значными ОУ£-структу-рами назовём проблемой ¥-общезначимости (и аналогично для проблемы выполнимости). Здесь устанавлены следующие общие факты:

• Проблемы Р-общезначимости для \/3-0СР£-предложений и для бескванторных ОТ^-предложений ш-эквивалентны, а проблема Р-об-щезначимости для ЗУ-ССР£-предложений неразрешима.

• В целом, проблема Р-общезначимости для ОСР£-предложений являе�