Постановка задачи в терминах Q-learning

Архив Проекта

Пожалуйста, не редактируйте эту страницу!

В качестве агента будет выступать собственно цепь РНК. Средой для агента будет энергетическая поверхность окружающая цепь РНК и формирующая ее 3-х мерную поверхность.

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

Действие определяется двумя числами: (1) выбранной позицией - нуклеотид который поворачивается и (2) идентификатором поворота - определяет 9 углов поворота с последующим пересчетом позиций атомов нуклеотида. Тогда множество доступных агенту действий - это открытое множество не запрещенных для выбранной позиции поворотов. Учитывая, что действие не задается простым перечислением, оно должно быть реализовано, в отличие от классического версии, динамическим массивом. Элементами массива, будет объект действие (а не просто число), характеризующийся рядом параметров - в данном случае двумя позиция и идентификатор поворота.

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

Состояния на базе статического определения. В данном случае состояние определяется энергией цепи. А энергия цепи определяется положением всех нуклеотидов. Например, в примере выше, определяется следующими числами:

0 - 332 // читается как положение начального (нулевого) нуклеотида в цепи в положении 332
1 - 993 
2 - 1858
3 - 2271

и такое положение однозначно определяется значением энергии равной -1.39 .

Множество возможных положений не превышает 3000. Но множество состояний, в таком случае, зависит от длины цепи. Число состояний можно оценить как $n^{k}$, где n - длина цепи, а k - число возможных положений. То есть в нашем примере $4^{3000}$ - огромное число состояний для нашей маленькой цепи. Нам же нужно исследовать как минимум цепи с длиной около 100 нуклеотидов, т.е. с числом состояний $100^{3000}$. Конечно многие из них вырожденные, но какие именно это еще нужно выяснить.

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

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

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

Во-первых, так же как и в случайном поиске (модуль FoldingSearchRnd) агент будет вести список найденных состояний с минимальной энергией (LowScore). А вознаграждение от среды, которое определяется абсолютным значением оценки энергии цепи, он будет преобразовывать к относительному виду. Для этого он будет считать вознаграждением за действие разность между текущей и предыдущей оценкой энергии. То есть для него вознаграждением будет, то на сколько его действия позволили улучшить последнее состояние с минимальной энергией.

Например, рассмотрим фрагмент поиска из примера выше:

Position: 2 FragID: 1280 Change: х.ххх LowScore: 8.539
Position: 4 FragID: 2093 Change: 0.076 LowScore: 8.463
Position: 2 FragID: 1187 Change: 1.328 LowScore: 7.135
Position: 4 FragID: 2550 Change: 0.290 LowScore: 6.845

Первый поворот 2 нуклеотида (Position) в положение 1280 (FragID) дает оценку энергии 8.539 (LowScore). Далее агент выполняет некоторые действия, которые не приводят к никакому вознаграждению, так как не уменьшают энергию относительно 8.539. Но вот какое то из действий, а именно поворот 4 нуклеотида в положение 2093, дает вознаграждение от среды 8.463. Агент же преобразовывает это значение как разность 8.539 - 8.463 = 0.076. Таким образом, истинным вознаграждением (скажем так, которое агент ощущает) является столбец Change.

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

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

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

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

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

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

См. также

• Q-learning‎ - классика