RNAInSpace/Реконструкция прошлого
- Более точное название: Реконструкция неизвестных состояний.
Всем известна так называемая «задача прогнозирования». Но не менее актуальной является задача реконструкции прошлого. Но в рамках науки «Искусственный интеллект» данная задача рассматривается крайне редко. Об этой задачи нам скорее известно из антропологии или истории, чем из точных, технических наук.
При попытке реконструкции прошлого мы столкнемся с быстро увеличивающимся числом вариантов (траекторий), отвечающих нынешнему состоянию системы. Только один из них соответствует реальному течению событий. Если выбрать не его, а какой-то другой, то получится уже искаженная "версия" истории. На основании чего выбирается правильная траектория ("версия")? Информация, на которую мы можем опереться, - совокупность имеющихся конкретных фактов. Траектории, несовместимые с ними, отбрасываются. В результате при наличии достаточного количества надежных фактов останется одна траектория, определяющая единственную версию истории. Однако даже для недалекого прошлого траекторий может оказаться значительно больше, чем достоверных сведений, - тогда однозначная трактовка исторического процесса уже не может быть произведена. [1]
Планирование как реконструкция прошлого
[править]Когда мы говорим о прогнозировании, то как правило имеем введу прогнозирование некой статистической (непрерывной) величины. Например, курса акций, доходов или расходов предприятия, кредитоспособность заёмщиков, длительность заболеваний, спрос на товары и т.п.
Когда же мы говорим о реконструкции прошлого, нас интересует наоборот дискретные величины - факты и происходившие события. Поэтому как на первый взгляд ни странно, задача прогнозирования не является обратной задачей для реконструкции событий в прошлом.
Когда же мы говорим о прогнозировании событий в будущем - речь идет о планировании. А вот понятия планирования в прошлом не бывает - это называется реконструкцией прошлого.
Поэтому планирование и реконструкция прошлого - это две близкие задачи отличающиеся только направленностью во времени. Кроме того, как будет показано ниже, время в ряде задач вообще может не иметь значения. И тогда в общем случае стоит вести разговор о восстановлении (реконструкции) состояний неизвестных элементов. Эти элементы - могут быть как активными субъектами (агентами), так и пассивными (объектами управления).
РНК-тюнинг в сравнении с методом „Альфа-бета отсечения“
[править]
Как происходит поиск желаемого состояния в „Альфа-бета отсечении“ ? Здесь анализируется состояния, которые будут в будущем, скажем через K тактов времени (ходов). А затем производят реконструкцию прошлого, то есть от желаемого состояния возвращаются в настоящее. Таким образом, направление времени теряет абсолютность, весь вопрос в том какую выбрать точку отсчета. Эту точку отсчета назовем глубиной (уровнем) просмотра - L.
Но в „Альфа-бета отсечении“ анализируются практически все возможные состояния уровня L, за исключением тех ветвей, которые уже очевидно анализировать не нужно. При этом уровень L-1 содержит в поддереве все варианты действий одного из элементов. Например, в игре в шахматы имеются 16 фигур, каждую из которых будем для общности называть элементом E.
Теперь попробуем выработать другой принцип анализа. Определим лишь то, что целью у нас будет поставить мат. Как известно, его можно поставить различными способами, но при этом король противника и одна из фигур нападающего игрока должны находится в определенных позициях (состояниях). Понятно, что кроме позиций короля и фигуры ставившей мат, важно расположение других фигур.
Но оценивать успешность партии мы можем только исходя из близости текущего состояния к одному из возможных целевых расположений, которые приводят к мату. Имея такую оценку, мы затем сможем реконструировать прошлое, получая подцели - положения, к которым в сложившихся условиях наиболее эффективно будет стремится тем или иным фигурам.
И вот именно из такой логики и работает метод РНК-тюнинг. Определяется цель - два элемента E1 и E2 (в данном случае - нуклеотида) должны быть в определенном взаимном состоянии (образовать водородную связь). При этом успешность приближения к этому, оценивается близостью расстояния и малым углом между этими элементами. Таким образом, каждое состояние можно отнести к одной из N групп, нахождение в которых указывает близость (или отдаленность) к целевому состоянию.
За ход могут меняться расположение любых элементов, но даже если элементы E1 и E2 не двигались, движение других элементов способствует или отдаляет от их целевого положения. Так например, примем N = 6. Тогда при активном перемещении элементов E1 и E2 в самом лучшем случае,например, можно получить только варианты из группы №3 (а нужен вариант из группы №1). Поэтому очевидно, что нужно так же передвигать другие элементы. Но какие ?
Чтобы ответить на этот вопрос, нужно сделать ряд проверок. Чтобы отсечь те варианты которые мало пригодны, стоит начать с активных действий элементов E1 и E2, например, как говорилось выше мы получили скажем 100 вариантов из группы №3. Все прочие варианты можно отсечь, и исходя из этих 100 вариантов, наугад попробовать переместить другую фигуру. Если перемещения получает варианты из группы №2 или выше, то действия таких элементов и нужно выбрать. В худшем случае они не должны уменьшать варианты из группы №3. Таким образом, шаг за шагом будут выполняться те действия которые приводят к цели, или увеличивают число вариантов (путей) ведущих к цели.
Демонстрация отличий на игре крестики-нолики
[править]
Чтобы продемонстрировать отличия данных подходов, сыграем в игру крестики-нолики. Для простоты начнем из состояния изображенного на рисунке. Существует 8 вариантов позиций крестиков дающих выигрыш (занять одну из вертикалей (3), одну из горизонталей (3), одну из диагоналей (2) ). Введем 3 группы. В группу 3 попадают все варианты, где один крестик и 2 пустых позиции на пути к выигрышу. В группу 2 попадают все варианты, где 2 крестика рядом и 1 пустая позиция нужная для выигрыша. И в 1-ую группу попадают 3 крестика расположенные давая выигрыш, учитывая число образуемых вариантов.
Из имеющегося положения надо проанализировать 5 положений и решить куда поставить крестик. Ставя крестик в позицию 1 (позиции отсчитываем слева-направо, сверху-вниз) вы попадаем в состояние из группы 2: 2 крестика и пустая клетка. Аналогично в позициях 3, 7 и 9. А в позиции 6 попадаем в группу 3: 1 крестики и две пустые клетки. Таким образом, в группе 2 имеем 4 варианта.
Теперь проанализируем эти 4 варианта на следующем шаге. Из позиций 1 и 3 получаем по 2 варианта выигрыша, а из 7 и 9 по одному. Поэтому в группу один попадают позиции 1 и 3.
Заметим, что в таком подходе мы избавились от достаточно большого перебора. И главное, данный алгоритм легко распараллелить, в отличии от альфа-бета.
Ссылки
[править]- Компьютерное моделирование в истории
- Алгоритмы шахматных программ
- Развитие искусственного интеллекта в шахматных программах