Научный архив: статьи

В одной из недавних статей я представил логику для кросс-мировой предикации (CWPL, crossworld predication logic). Кросс-мировая предикация — это атрибуция отношений объектам, каждый из которых ассоциирован с некоторым возможным миром. (Интуитивно, объект, ассоциированный с возможным миром — это объект, каков он в этом мире). CWPL — это модальная логика первого порядка с равенством и λ-оператором. Ее преимущество перед другими известными мне логиками для кросс-мировой предикации (в частности, перед логиками, разработанными Баттерфилдом и Стерлингом, Вемайером и Коцуреком) состоит в том, что она базируется на стандартном языке модальной логики первого порядка. В семантическом плане CWPL основана на кросс-мировой интерпретации предикатов, при которой n-местный предикат получает экстенсионал для каждой упорядоченной n-ки возможных миров, а не для каждого отдельного возможного мира. Использование кросс-мировой интерпретации предикатов при оценке формулы в семантике CWPL оказывается возможным благодаря тому, что истинностное значение формул релятивизировано к частичным функциям от предметных переменных к возможным мирам. В упомянутой выше статье описаны синтаксис и семантика CWPL; в настоящей статье разработана табличная теория доказательств для CWPL и показана ее слабая корректность и полнота.

Рассматриваемый класс схем размещения частиц по ячейкам характеризуется введением верхнего ограничения уровней заполнения ячеек с его обязательным достижением хотя бы в одной ячейке каждого исхода каждой схемы. Схемы различаются между собой парными качествами составляющих их элементов (ячеек и частиц) по их различимостям. Из направлений исследования схем выделяются представляющие наибольший интерес по нестандартным приемам доасимптотического анализа и получению новых результатов – это нумерованные бесповторные перечисления исходов схем и нахождение их чисел.

В схемах S размещения r частиц по n различимым ячейкам изучаются их размещения в выделенных m ячейках – схем S∗, для которых проводится анализ новым перечислительным методом (ПМ) по расширенным направлениям перечислительной комбинаторики: нахождения числа исходов и на основе построения модели их бесповторного нумерованного перечисления – решения для них задачи нумерации в прямой и обратной постановках по установлению взаимнооднозначного соответствия между их видами и номерами и введения управляемого вероятностного распределения на множестве исходов схемы.

Пусть r, r1 - целые неотрицательные числа, r < r1, η1,… ηN - обобщенная схема размещения (r1 - r)n + rN частиц по N ячейкам, определенная независимыми случайными величинами ξ1,… ξN, которые имеют распределение степенного ряда, определенное рядом ∑∞ k=0 bk βk k!, случайный процесс X{r1} n, N (t) = ∑[tN ] i=1 I{ηi=r1}, 0 t 1, Fn - эмпирический процесс с параметром n. Показано, что если n, r, r1 - фиксированные числа и выполнено условие Ar(r1): bk = 0, k < r, br > 0, bk = 0, r < k < r1, br1 > 0, то при N → ∞ cлучайные процессы X{r1} n, N cходятся по распределению в пространстве Скорохода к cлучайному процессу nFn.

Рассматриваются конфигурационные графы с N вершинами. Степени вершинявляются независимыми одинаково распределенными случайными величинами, распределение которых удовлетворяет следующему условию: при k→∞ pk=P{η=k}∼h(k)/kg,2 < g < 3, где h(k)- медленно меняющаяся на бесконечности функция. Изучаются случайные графы при условии, что сумма степеней всех вершин равна n. Найдены предельные распределения числа вершин заданной степени в таком условном графе при N, n →∞ так, что h(N)n2 N(4-3g)/(g-1) ≥ C > 0.

Рассматриваются конфигурационные графы с N вершинами. Степени вершин графа являются независимыми одинаково распределенными случайными величинами, распределение которых удовлетворяет условию: при k→∞ pk=P{ξ=k}∼h(k)/kτ+1,τ>0, где случайная величина ξ равна степени любой вершины графа, а h(x)обозначает медленно меняющуюся на бесконечности функцию. Исследуется глобальный кластерный коэффициент условного конфигурационного графа приразличных значениях параметра τ > 0. Получены предельные теоремы для этой характеристики при стремлении числа вершин к бесконечности.

Дерево решений — это один из алгоритмов машинного обучения, у которого есть ряд преимуществ (хорошая интерпретация, возможность работы с разными типами данных, автоматическое формирование правил и пр.). В некоторых задачах, где набор данных ограничен, а признаки связаны между собой (например, в задаче атрибуции текстов), можно при построении условий в узлах модели использовать не одиночные признаки, а их линейные комбинации. С учетом этого в статье изложено развитие метода «дерево решений», которое заключается в том, что к старым k признакам добавляются новые признаки как линейные комбинации двух исходных: xij = αxi ± (1 − α)xj, где i, j = 1,…, k и параметр α ∈ [0, 1]. Для проведения численных экспериментов на примере задачи атрибуции текстов выполнена реализация построения линейных комбинаций признаков в информационной системе СМАЛТ («Статистические методы анализа литературного текста»). Результаты классификации дореволюционных текстов из журналов «Время», «Эпоха» и еженедельника «Гражданин» с использованием разных видов n-грамм показали, что данное улучшение повышает точность метода, при этом несущественно снижает интерпретацию полученного результата.

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

Рассматриваются леса Гальтона - Ватсона, порожденные однородным критическим ветвящимся процессом с N начальными частицами, в котором числопрямых потомков каждой частицы является случайной величиной ξ с распределением pk=h(k+1)/(k+1)τ, k=0,1,2,…, τ ∈(2,3), где h(x)- медленно меняющаяся на бесконечности функция. Предполагается, что число некорневых вершин случайного леса равно n. Пусть μr- число деревьев с rвершинами. Доказаны теоремы о скорости сходимости распределенийμrк нормальному закону при N, n, r →∞ и n/N ≤ C < ∞.

Рассматриваются леса Гальтона - Ватсона с N корневыми деревьями и n некорневыми вершинами. Предполагается, что такие леса образуются критическим ветвящимся процессом, в котором число прямых потомков каждой частицы имеет распределение pk=h(k+1)/(k+1)τ, k=0,1,2,…, τ ∈(2,3), где h(x)- медленно меняющаяся на бесконечности функция. Найдены предельные распределения числа деревьев заданного объема, если N, n →∞, n/N →∞.

Представлена и исследована теоретико-игровая математическая модель управления заданиями в вычислительной системе с линейными экстерналиями. Каждый игрок стремится максимизировать свою производительность в присутствии положительных экстерналий. Предложенная модель описывает управление заданиями в системе добровольных вычислений типа Desktop Grid, а экстерналии выражают обмен информацией в процессе решения научной задачи. Системы Desktop Grid задействуют вычислительные мощности неспециализированных компьютеров, объединенных сетью передачи данных и выполняющих вычисления в то время, когда они не заняты другой работой. В таких системах вычислительноемкая научная задача зачастую делится на несколько взаимосвязанных подзадач, выполняемых параллельно. Промежуточные результаты решения одной подзадачи способны помогать в решении остальных подзадач, оптимизируя или сокращая вычисления. В данной работе доказано, что игра является потенциальной в случаях однородных процессоров или заданий и одинаковых экстерналий, инвариантных или симметричных экстерналий. При этом в случаях с однородными процессорами или заданиями и одинаковыми экстерналиями или инвариантными экстерналиями равновесие по Нэшу единственно и глобально оптимально, в то время как случай с симметричными экстерналиями допускает множество равновесий по Нэшу в чистых стратегиях. Приводятся результаты вычислительных экспериментов по моделированию управления заданиями предложенным методом в сравнении с рядом популярных алгоритмов. Представленные результаты расширяют область применения классических моделей, доказывая существование равновесия и сходимость к нему как в задачах минимизации задержки, так и в задачах максимизации производительности. Найденный вид функции потенциала позволяет использовать методы глобальной оптимизации для поиска равновесий.

В работе дано определение топологической размерности dim ξ максимальных сцепленных систем (м. с. с.) замкнутых подмножеств метризуемого компакта X. По определению dim ξ, есть точная нижняя грань нижних размерностей квантования м. с. с. ξ по всем метрикам, совместимым с топологией X. Предложенное определение dim ξ мотивировано теоремой Понтрягина –Шнирельмана, характеризующей топологическую размерность метризуемого компакта как инфимум нижних емкостных размерностей этого компакта по всем совместимым метрикам. Для любого метризуемого компакта X и любой м. с. с. ξ выполняется неравенство dim ξ  dimX. При этом для конечномерного метризуемого компакта X справедлива следующая теорема о промежуточных значениях размерности dim ξ: для любого целого числа k, удовлетворяющего неравенствам 0  k  dimX, существует м. с. с. ξk такая, что dim ξk = k. Доказано, что для всех рассмотренных ранее м. с. с. с известными значениями размерностей квантования размерность dim ξ является целым числом. В частности, построенные по технологии Е. В. Кашубы м. с. с. ξ(A, B) всегда нульмерны в топологическом смысле.