Нове геометричне подання простору «станів-дій» Q-learning алгоритму в проблемі передбачення третинної структури білка

Розроблено новітнє подання простору станів та дій для алгоритму машинного навчання з підкріпленням Q-learning. Застосування Q-learning алгоритму з пропонованим поданням простору станів та дій досліджується на задачі передбачення третинної структури білків. Особливість пропонованого подання полягає в...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2020
1. Verfasser:	Чорножук, С.А.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2020
Schriftenreihe:	Кібернетика та комп’ютерні технології
Schlagworte:	Математичне моделювання та чисельні методи
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/173152
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Нове геометричне подання простору «станів-дій» Q-learning алгоритму в проблемі передбачення третинної структури білка / С.А. Чорножук // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2020. — № 3. — С. 59-73. — Бібліогр.: 16 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-173152
record_format	dspace
spelling	irk-123456789-1731522020-11-24T01:26:45Z Нове геометричне подання простору «станів-дій» Q-learning алгоритму в проблемі передбачення третинної структури білка Чорножук, С.А. Математичне моделювання та чисельні методи Розроблено новітнє подання простору станів та дій для алгоритму машинного навчання з підкріпленням Q-learning. Застосування Q-learning алгоритму з пропонованим поданням простору станів та дій досліджується на задачі передбачення третинної структури білків. Особливість пропонованого подання полягає в урахуванні геометричних властивостей результуючого ланцюга в кубічній ґратці. Ефективність такого підходу підтверджується експериментально на широко-розповсюдженому в світі наборі тестових даних. Цель роботы. Анализ существующих подходов к представлению пространств состояний и действий для алгоритма Q-learning для задачи предсказания трехмерной структуры белков, выявление их преимуществ и недостатков, предложение нового геометрического представления пространства «состояние-действие». Дальше необходимо сравнить существующие и предлагаемые подходы, сделать выводы и описать возможные будущие шаги дальнейших исследований. The purpose of the article is to analyze existing approaches of different states and actions spaces representations for Q-learning algorithm for protein structure folding problem, reveal their advantages and disadvantages and propose the new geometric “state-space” representation. Afterwards the goal is to compare existing and the proposed approaches, make conclusions with also describing possible future steps of further research. 2020 Article Нове геометричне подання простору «станів-дій» Q-learning алгоритму в проблемі передбачення третинної структури білка / С.А. Чорножук // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2020. — № 3. — С. 59-73. — Бібліогр.: 16 назв. — укр. 2707-4501 DOI:10.34229/2707-451X.20.3.6 http://dspace.nbuv.gov.ua/handle/123456789/173152 519.8 uk Кібернетика та комп’ютерні технології Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Математичне моделювання та чисельні методи Математичне моделювання та чисельні методи
spellingShingle	Математичне моделювання та чисельні методи Математичне моделювання та чисельні методи Чорножук, С.А. Нове геометричне подання простору «станів-дій» Q-learning алгоритму в проблемі передбачення третинної структури білка Кібернетика та комп’ютерні технології
description	Розроблено новітнє подання простору станів та дій для алгоритму машинного навчання з підкріпленням Q-learning. Застосування Q-learning алгоритму з пропонованим поданням простору станів та дій досліджується на задачі передбачення третинної структури білків. Особливість пропонованого подання полягає в урахуванні геометричних властивостей результуючого ланцюга в кубічній ґратці. Ефективність такого підходу підтверджується експериментально на широко-розповсюдженому в світі наборі тестових даних.
format	Article
author	Чорножук, С.А.
author_facet	Чорножук, С.А.
author_sort	Чорножук, С.А.
title	Нове геометричне подання простору «станів-дій» Q-learning алгоритму в проблемі передбачення третинної структури білка
title_short	Нове геометричне подання простору «станів-дій» Q-learning алгоритму в проблемі передбачення третинної структури білка
title_full	Нове геометричне подання простору «станів-дій» Q-learning алгоритму в проблемі передбачення третинної структури білка
title_fullStr	Нове геометричне подання простору «станів-дій» Q-learning алгоритму в проблемі передбачення третинної структури білка
title_full_unstemmed	Нове геометричне подання простору «станів-дій» Q-learning алгоритму в проблемі передбачення третинної структури білка
title_sort	нове геометричне подання простору «станів-дій» q-learning алгоритму в проблемі передбачення третинної структури білка
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2020
topic_facet	Математичне моделювання та чисельні методи
url	http://dspace.nbuv.gov.ua/handle/123456789/173152
citation_txt	Нове геометричне подання простору «станів-дій» Q-learning алгоритму в проблемі передбачення третинної структури білка / С.А. Чорножук // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2020. — № 3. — С. 59-73. — Бібліогр.: 16 назв. — укр.
series	Кібернетика та комп’ютерні технології
work_keys_str_mv	AT čornožuksa novegeometričnepodannâprostorustanívdíjqlearningalgoritmuvproblemíperedbačennâtretinnoístrukturibílka
first_indexed	2025-07-15T09:41:18Z
last_indexed	2025-07-15T09:41:18Z
_version_	1837705439364513792
fulltext	МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ЧИСЕЛЬНІ МЕТОДИ ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.3 59 КІБЕРНЕТИКА та КОМП'ЮТЕРНІ ТЕХНОЛОГІЇ Розроблено новітнє подання простору станів та дій для алгоритму машинного навчання з підкріпленням Q-learning. Застосування Q-learning алгоритму з пропонованим подан- ням простору станів та дій досліджується на задачі передбачення третинної структу- ри білків. Особливість пропонованого подан- ня полягає в урахуванні геометричних влас- тивостей результуючого ланцюга в кубічній ґратці. Ефективність такого підходу підт- верджується експериментально на широко- розповсюдженому в світі наборі тестових даних. Ключові слова: просторова структура білка, комбінаторна оптимізація, відносне коду- вання, машинне навчання, Q-learning, рівнян- ня Белмана, простір станів, простір дій, ба- зис у трьохвимірному просторі.  С.А. Чорножук, 2020 УДК 519.8 DOI:10.34229/2707-451X.20.3.6 С.А. ЧОРНОЖУК НОВЕ ГЕОМЕТРИЧНЕ ПОДАННЯ ПРОСТОРУ «СТАНІВ-ДІЙ» Q-LEARNING АЛГОРИТМУ В ПРОБЛЕМІ ПЕРЕДБАЧЕННЯ ТРЕТИННОЇ СТРУКТУРИ БІЛКА Вступ. Машинне навчання з підкріпленням – це акту- альний апарат для розв’язування багатьох задач, в яких точний пошук оптимальних розв’язків є NP-складною задачею і тому неможливий на практи- ці. Машинне навчання з підкріпленням – це галузь машинного навчання, що досліджує дії, які мають ви- конувати програмні агенти в певному середовищі для максимізації деякого уявлення про сукупну винагоро- ду при неможливому вичерпному пошуці в просторі, утвореному декартовим добутком множини станів на множину дій. Визначення вторинної або третинної структури білків на основі використання HP-моделі Діла [1] – важлива та актуальна проблема обчислюва- льної біології. Точний пошук оптимального розташу- вання послідовності амінокислот (мономерів) у такій моделі є NP-складною задачею, а отже обчислюваль- но неможливий вже на відносно невеликих розмірнос- тях. Саме тому для передбачення вторинної або тре- тинної структури білків на базі моделі Діла викорис- товуються численні метаевристичні методи [2–8], а також й підходи машинного навчання з підкріплен- ням, а саме Q-learning підхід [9–12]. Варто зазначити, що левова частина методів ма- шинного навчання з підкріпленням Q-learning викори- стовуються саме для передбачення вторинної струк- тури білку, адже для такої задачі простір станів та дій суттєво менший [9, 10, 12]. У цій статті ми транслю- вали ідеї, що вищезазначені у роботах, для постановки та розв’язування задачі передбачення саме третинної структури білка з використанням Q-learning методу, а також формалізовано нове подання простору «стани – дії» для тієї ж задачі. Математична постановка задачі. У роботі вико- ристовується HP-модель Діла, яку представимо згідно [13]. У такій моделі кожна амінокислота (мономер) , 1,i i n  , яка входить до первинної структури білка, належить одному з двох типів: https://doi.org/10.34229/2707-451X.20.3.6 https://uk.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%BD%D0%B5_%D0%BD%D0%B0%D0%B2%D1%87%D0%B0%D0%BD%D0%BD%D1%8F https://uk.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BD%D0%B8%D0%B9_%D0%B0%D0%B3%D0%B5%D0%BD%D1%82 С.А. ЧОРНОЖУК 60 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 3 H – гідрофобний тип, P – полярний, а сама третинна структура подається як послідовність аміно- кислот, що розміщена у деякій (просторовій) ґратці у вигляді неперервного ланцюга [14]. У цій роботі використовується кубічна ґратка. Важливо зазначити, що у такого ланцюга не має бути са- моперетинів. Тоді цільова функція (енергія утвореної третинної структури) обчислюється за формулою 1 2 2 ( ) ( ( ), ( )) ( ) ( ),i j i j i j n F x I U U h h            (1) де x X – неперервний ланцюг без самоперетинів довжиною ,n X – простір усіх можливих непе- рервних ланцюгів довжиною n без самоперетинів, розміщених у кубічній ґратці, ( )iU  – вузол у кубічній ґратці, який містить i-й мономер ланцюга (заданий декартовими координатами), а 1 2 1 2 1, якщо вузли та сусідні ґратці,в кубічній ( , ) 0, в іншому разі, U U I U U     1, якщо = H, ( ) 0, якщо = P. h      Задача полягає у тому щоб знайти такий допустимий ланцюг ,optx X що arg min ( )opt x X x F x   . (2) Конкретний ланцюг із X зручно подавати не у вигляді абсолютних координат вузлів, у яких він розташований, а за допомогою внутрішнього відносного кодування [15], при якому вважається, що ланцюг починається в точці (0, 0, 0), а надалі кожен новий сегмент ланцюга задається відносним поворотом, щодо свого попереднього положення (вправо на 90° – right, вліво на 90° – left, догори на 90° – up, донизу на 90° – down, рух прямо без поворотів – front). Наприклад, ланцюг ABCDEF (рис. 1) при заданій початковій орієнтації, буде мати кодування (front, up, right, down, down). РИС. 1. Ланцюг ABCDEF має відносне кодування (front, up, right, down, down) У роботі використовується відносне кодування, а початкова орієнтація задається за рахунок двох початкових неоднакових з точки зору абсолютного кодування поворотів. Перший з них обов’язково буде позначено front, а другий – up у рамках відносного кодування. Така початкова орієнтація робить відносне кодування інваріантним щодо будь-якого повороту, кратного 90° на- вколо будь-якої з координатних осей (рис. 2). Використання такого підходу зменшує простір X, а значить робить пошук optx у X більш ефективним. Нагадаємо, що кодування 1 2( ( ), ( ),..., ( ))nEnc U U U   ланцюга x, який подається послідовності мономерів 1 2, ,..., n   , є інва- ріантним щодо довільного відображення 3 3: ,f  якщо ґратка та відношення сусідства в ній інваріантні відносно f, та 1 2 1 2( ( ), ( ),..., ( )) ( ( ( )), ( ( )),..., ( ( )))n nEnc U U U Enc f U f U f U       [14]. НОВЕ ГЕОМЕТРИЧНЕ ПОДАННЯ ПРОСТОРУ «СТАНІВ-ДІЙ» Q-LEARNING АЛГОРИТМУ ... ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.3 61 РИС. 2. Три ланцюги, утворені шляхом повороту лівого зверху на 90° навколо кожної з осей Наприклад, використовуючи наведену орієнтацію, кожне з відносних кодувань буде трійка (front, up, right). Загальний опис алгоритму Q-learning, який використовується для розв’язування задачі. Як показано у [9], Q-learning – це розширення традиційного підходу динамічного програмування, що розв’язує задачу, яку можна описати недетермінованим марковським процесом прийняття рі- шень [15]. При цьому функція розподілу ймовірностей визначає множину майбутніх потенційних станів системи, за умови виконання агентом певної фіксованої дії при певному поточному стані си- стеми. В подальшому поняття «стан системи» буде конкретизуватися для досліджуваної проблеми. На відміну від інших підходів машинного навчання з підкріпленням, які здебільшого базуються на відповідності пари «стан-стан» певному скаляру, при підході Q-learning знаходиться відповідність пари «стан-дія» певному скалярному значенню (Q-value). Оптимальне значення Q-value – це сума підкріплень, яка може бути отримана, виконавши відповідну дію та послуговую- чись оптимальній стратегії подальших дій (на кожному етапі обирати таку дію, якій відповідає найбільше значення Q-value). У процесі навчання Q-learning алгоритм знаходить оптимальні Q-value ітеративно, використо- вуючи рівняння Белмана. Оновлення значень відбувається наступним чином: ' ( , ) : ( , ) ( ( , ) max( ( ', '))), a Q s a Q s a r s a Q s a     (3) де ( , )nQ s a – Q-value на поточній ітерації алгоритму, ( , )r s a – винагорода, яку отримує агент, виконавши дію a перебуваючи в стані s, s’ – стан, в який потрапить агент, перебуваючи у стані a та виконавши дію s. Для зручності введемо поняття функції переходу зі стану в стан : S A S   , яка визначає в який наступний стан перейде система, тобто s’ = ( , ).s a У такому випадку рівність (3) буде іншого вигляду ' ( , ) ( , ) ( ( , ) max( ( ( , ), '))) a Q s a Q s a r s a Q s a a      , (4) де  – фактор навчання агента, який показує, як швидко агент реагує на нову інформацію,  – фактор дисконтування агента, що показує, наскільки потужно агент реагує на винагороду піс- ля майбутніх своїх дій. С.А. ЧОРНОЖУК 62 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 3 Необхідно ввести декілька нових параметрів алгоритму. Нехай задано I – загальна кількість ітерацій алгоритму, p – ймовірнісний поріг, який відповідає за стратегію вибору поточної дії,  – темп зменшення p. Параметр  відповідає за те, щоб на більш пізніх ітераціях агент обирав опти- мальні дії з більшою ймовірністю, а Softmax – відома в машинному навчанні функція активації [15]. Важливо зазначити, що тут і надалі при адаптації відомих підходів для передбачення третинної структури білків простір дій складатиметься з можливих поворотів при відносному кодуванні лан- цюга. Агентом, у свою чергу, є ітеративний процес утворення відносного кодування ланцюга. Коли говоримо, що агент виконує певну дію з простору дій, то маємо на увазі, щодо відносного коду- вання додається наступний поворот, що однозначно відповідає цій дії. Бінарний оператор  і позначає додавання чергового повороту до поточного відносного кодування. У випадку задачі (2) схема пропонованого Q-learning алгоритма показана на рис. 3. procedure Qlearning(); x_optimal :=  ; x_сurrent :=  ; energy_optimal := 0; for i from 0 to I – 1 do for j from 0 to n – 2 do s_current := визначити стан системи, що відповідає x_current; possible_actions :=  ; qualities :=  ; for each a із множини можливих поворотів do: ( _ , ) ( _ , ) ( ( _ , ) max( ( _ , '))) ' Q s current a Q s current a r s current a Q s next a a      if x_current  a не містить самоперетинів then Додати a в кінець possible_actions; Додати ( _ , )Q s current a в кінець qualities; endif endfor if possible_actions не пустий then value := random[0; 1]; if value > p then Агент виконує дію a з possible_actions, якому відповідає найбільше зна- чення з qualities (тобто x_current := x_current  a); else probs := Softmax(qualities); Агент виконує дію a з possible_actions з ймовірностями, описаними у probs (x_current := x_current  a); endif endif endfor energy := F(x_current); if energy < energy_optimal then x_optimal := x_current; energy_optimal := energy; endif p:= p  ; endfor return {x_optimal, energy_optimal}; РИС. 3. Загальна схема роботи Q-learning алгоритму НОВЕ ГЕОМЕТРИЧНЕ ПОДАННЯ ПРОСТОРУ «СТАНІВ-ДІЙ» Q-LEARNING АЛГОРИТМУ ... ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.3 63 Аналіз пропонованих репрезентацій простору стан-дія в літературі. Як випливає із загаль- ної схеми роботи Q-learning алгоритму, важливим є визначення стану системи, який відповідає то- му чи іншому відносному кодуванню, а також обчислення винагороди, яку отримує агент викона- вши ту чи іншу дію, перебуваючи в певному стані. Наприклад, у [10] простір «стан-дія» визнача- ється наступним чином: 1) множина допустимих дій A фактично множиною поворотів при абсолютному кодуванні ланцюга. Тобто A = 1 2 3 4{ , , , }a a a a , де 1a = left, 2a = right, 3a = up, 4a = down; 2) множина станів S складається з 4 1 3 n  станів, де в i-й стан можна потрапити, виконавши рівно 4[log (3 2)]i  дій (поворотів). До того ж, неможливо потрапити у будь-який стан, виконавши більше однієї унікальної множини дій (поворотів). Функція переходу : S A S   визначається наступним чином: 1 4 3( , ) , {1,2,...,(4 1) / 3}, {1,2,3,4}n i j i js a s i j       . Для наочності, простір станів та дій у [10] показано на рис. 4. РИС. 4. Схема простору станів та дій [10] Таке подання легко адаптується для передбачення третинної структури білка. Використовую- чи відносне кодування замість абсолютного, єдиною відмінністю буде інша множина допустимих дій A та загальна кількість станів системи. Тоді A = 1 2 3 4 5{ , , , , }a a a a a , де 1a = left, 2a = right, 3a = up, 4a = down, 5a = front, а загальна кількість станів множини S тепер дорівнює 5 1 4 n  . Винагорода r(s, a), яку отримує агент під час вибору тої чи іншої дії (повороту в кубічній ґратці), обчислюватиметься аналогічно до того, як вона обчислюється в квадратичній [10], а саме: 1 2 1 1 2 1 2 0.01, якщо ланцюг ... містить самоперетини. ( , ) ( \| , , ,..., ) ( ... ), якщо 1 1. 0.1, інакше. k k k a a a a r s a r a s a a a F a a a a k n                  (5) С.А. ЧОРНОЖУК 64 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 3 Тут 1 1 2( \| , , ,..., )kr a s a a a означає те саме, що і r(s, a), де s – cтан системи, отриманий шляхом виконання дій 1 2, ,..., ka a a на початку перебуваючи в стані 1,s а 1 2 ... ka a a   визначає ланцюг, який при цьому отримано (фактично 1 2 ... ka a a   визначає відносне кодування ланцюга, але надалі називатимемо 1 2 ... ka a a   ланцюгом). Автори у [10] зазначають, що умова 1 1k N   означає, що система перейшла в термінальний стан. Надалі будемо використовувати цей термін. Таке подання простору станів має очевидний недолік – кількість станів є значною (для n = 48 їх кількість  328,88 10 ), а отже під час виконання алгоритму багато станів так і залишаться невідвіданими, що може суттєво погіршити знайдене рекордне значення цільової функції. Надалі називатимемо цю проблему надмірною інформативністю простору станів системи. Для вирішення цієї проблеми пропонуються й інші способи подання простору станів. Так, в [12] A = 1 2 3 4{ , , , },a a a a де 1a = left, 2a = right, 3a = up, 4a = down, але станом є пара, що утворюється останнім поворотом та його порядковим номером для поточної послідовності амінокислот з функ- цією переходу між станами (4 ( 1) mod 4) , якщо ( 1)mod 4 0. ( , ) , інакше. i i j i j i j s i s a s            Приклад подання простору станів показано на рис. 5, 6 [12]. Як і в [10], у цитованій роботі [12] розв’язується задача передбачення вторинної структури білка. РИС. 5. Схема простору станів та дій [12] НОВЕ ГЕОМЕТРИЧНЕ ПОДАННЯ ПРОСТОРУ «СТАНІВ-ДІЙ» Q-LEARNING АЛГОРИТМУ ... ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.3 65 РИС. 6. Схема простору станів та дій [12] на прикладі послідовності амінокислот HPHPPH Необхідно зазначити, що абсолютне кодування ланцюга не є вдалим для подання множини станів. Оскільки абсолютне кодування не є інваріантним щодо поворотів ґратки навколо координа- тних осей у тривимірному просторі та проти годинникової стрілки у двовимірному, то, наприклад, стану HPHPPHD може відповідати певний ланцюг, який при повороті ґратки на 90 , 180 , 270 проти годинникової стрілки буде вже відповідати станам HPHPPHR, HPHPPHU, HPHPPHL. Це означає, що всі термінальні стани системи будуть відповідати одній тій самій множині ланцюгів з точністю до поворотів ґратки. Отже, сумарна кількість винагороди, яку отримає агент при всіх мо- жливих переходах до термінальних станів, буде однаковою для кожного з цих термінальних станів. Фактично це означає, що агент не буде мати достатньо інформації, щоб якісно відрізнити один стан від іншого. Надалі будемо називати цю проблему недостатньою інформативністю простору станів системи. Недостатня інформативність простору станів системи робить Q-learning алгоритм малоефекти- вним. Заміна абсолютного кодування відносним частково вирішує цю проблему. Тобто, роз- ширивши множину дій A до 1 2 3 4 5{ , , , , }a a a a a , де 1a = left, 2a = right, 3a = up, 4a = down, 5a = front та замінивши абсолютне кодування відносним, стає можливим використання подання [12] для передбачення третинної структури білків. Використання простору станів та дій, поданих у [9], разом із заміною абсолютного кодування ланцюга на відносне є компромісним підходом, що частково вирішує як проблему недостатньої, так і надлишкової інформативності простору станів системи. Тут станом є трійка, утворена коор- динатами вузла мономера в ґратці, типом {H, P} та порядковим номером мономера у первинній структурі білка (послідовності амінокислот). Множина дій ідентична з [12] для задачі передбачен- ня третинної структури білка. Функція винагороди ( , )r s a обчислюється наступним чином: 1 2 1 1 2 1 2 1 2 0.1, якщо ланцюг ... містить самоперетини, ( , ) ( \| , , ,..., ) min( ( ... ) ( ... ),0.1), інакше. k k k k a a a a r s a r a s a a a F a a a F a a a a                 С.А. ЧОРНОЖУК 66 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 3 У роботі [8] використовується підхід Deep Q-learning, в якому значення Q(s, a) обчислюється не точно, а наближено з використанням LSTM нейронної мережі. Різниця між класичним Q-learning підходом та Deep Q-learning підходом показана на рис. 7 [9]. Важливо зазначити, що у своїй роботі ми не використовували Deep Q-learning підхід, але вико- ристали опис простору станів та дій з [9] в Q-learning алгоритмі, показаному на рис. 3. Пропонований підхід до подання простору станів та дій. Очевидно, що, після виконання по- воротів, якими визначено ланцюг при відносному кодуванні, результуюча орієнтація буде відрізня- тися від початкової (рис. 8). Якщо в кінцевій орієнтації позначити напрямок front, наприклад, як орту (1, 0, 0), left, як орту (0, 1, 0), та up, як (0, 0, 1), то утвориться певний базис, в якому можна бу- де задати координати усіх мономерів у вузлах ґратки. Тоді станом системи , ,l is   , {1,2,..., 1},n n l   назвемо сукупність інформації: 1. Координати не більше, ніж  найближчих вузлів у ґратці окрім попереднього, що містять мономери будь-якого з двох типів {H, P} у базисі, утвореному кінцевою орієнтацією, після вико- нання l перших поворотів. 2. Координати не більше, ніж  найближчих вузлів у ґратці окрім попереднього, що містять H-мономери будь-якого з двох типів {H, P} у базисі, утвореному кінцевою орієнтацією споглядан- ня, після виконання l перших повротів. 3. Тип (l + 1)-го мономера у первинній структурі білка. РИС. 7. Відмінність підходів: а – Q-learning; б – Deep Q-learning а б НОВЕ ГЕОМЕТРИЧНЕ ПОДАННЯ ПРОСТОРУ «СТАНІВ-ДІЙ» Q-LEARNING АЛГОРИТМУ ... ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.3 67 Множиною дій так само, як і раніше, є A = 1 2 3 4 5{ , , , , }a a a a a , де 1a = left, 2a = right, 3a = up, 4a = down, 5a = front. Тут повороти виконуються з урахуванням кінцевої орієнтації. Важливо зазначити, що кількість перших поворотів не є частиною подання стану системи, а отже , , , ,( , )l l i js a s      , де  може бути будь-яким елементом множини { , 1,..., 1 }l l n l     , а не тільки 1. Також необхідно вказати, що попередній вузол не розглядається, оскільки він є сусіднім у первинній структурі білка, тобто точно не впливає на можливе значення цільової функції F. Для наочності деякі приклади пропонованих станів системи з  = 2 та  = 1 показані на рис. 9 (на рис. а після виконання поворотів front, up, left, left, right з первинною структурою HPHPHH отри- маємо cтан «2 – 1 – 1 0 – 2 0 0 1 – 2 – 1 0 H», на рис. б після виконання поворотів front, up, left, left, right, right, front, up з первинною структурою HPHPHHHHP отримаємо стан «2 – 1 0 1 – 1 – 1 1 1 – 1 0 1 P»). РИС. 8. Початкова та кінцева орієнтації ланцюга з відносним кодуванням forward, up, left, left, right РИС. 9. Приклади пропонованих станів системи при  = 2 та  = 1 Таке подання станів, як і подання [9], також є компромісним підходом, що частково вирішує як проблему недостатньої, так і надлишкової інформативності простору станів, адже містить у собі інформацію лише про значущу частину ланцюга. Пропонована функція винагороди обчислюється наступним чином: С.А. ЧОРНОЖУК 68 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 3 1 2 1 2 1 2 1 2 1 2 2( ( ... ) ( ... )) 0.25( ( ... ) ( ... )) 1 1 2 10, якщо ланцюг ... містить самоперетини, ( , ) ( \| , , ,..., ) , k k k k k F a a a F a a a a G a a a G a a a a k a a a a r s a r a s a a a e                         інакше.      Тут 1 1 1 1 2 1 1 ( ) ( ) ( ) ( , ,..., ) ( ) k k i i i k k i i U U h G a a a h               . Необхідно нагадати, що відносне кодування 1 2, ,..., ka a a однозначно задає положення моно- мерів у ґратці 1 2 1( ), ( ),..., ( )kU U U    . Слід також зазначити, що функція : S A S   може бути недетермінованою. На рис. 10, а, б показано приклад недетермінованості функції : S A S   при пропонованому поданні простору станів та дій. Наприклад, з параметрами  = 1 та  = 1 обидва відносних кодування front, front, up, down, front, down, front, front, front, down, front, down, up, front та front, front, up, down, front, down, front, front, front, down, down, up, front, front переведуть систему в поточний стан «1 – 1 0 0 1 0 0 – 2 H». В обох випадках агент виконує поворот вгору. В першому випадку така дія переведе систему в стан «1 – 1 0 1 1 0 0 2 P» (рис. 10, а), в другому – у стан «1 – 1 0 1 1 0 0 3 P». (рис. 10, б). РИС. 10. Приклад недетермінованості функції : S A S   при пропонованому поданні простору станів та дій Обчислювальний експеримент. Q-learning алгоритм тестувався на 10 реальних значеннях білків довжиною 48, які широко використовуються при аналізі алгоритмів розв’язування задачі, і вперше були запропоновані у [16] (табл. 1). Обчислювальний експеримент проводився на персо- нальному комп'ютері Apple MacBook Pro Touch Bar 13 2019 з процесором 1.4 GHz Quad-Core Intel Core i5 та оперативною пам’яттю 8 GB 2133 MHz LPDDR3. Параметри алгоритму Q-learning та параметри опису станів системи обрані на основі попередніх досліджень так:  = 0.01,  = 0.95, p = 1.0,  = 0.999994, I = 100000,  = 8,  = 8. НОВЕ ГЕОМЕТРИЧНЕ ПОДАННЯ ПРОСТОРУ «СТАНІВ-ДІЙ» Q-LEARNING АЛГОРИТМУ ... ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.3 69 ТАБЛИЦЯ 1. Номер та код послідовності № послідовності PH код послідовності 1 HPHHPPHHHHPHHHPPHHPPHPHHHPHPHHPPHHPPPHPPPPPPPPHH 2 HHHHPHHPHHHHHPPHPPHHPPHPPPPPPHPPHPPPHPPHHPPHHHPH 3 PHPHHPHHHHHHPPHPHPPHPHHPHPHPPPHPPHHPPHHPPHPHPPHP 4 PHPHHPPHPHHHPPHHPHHPPPHHHHHPPHPHHPHPHPPPPHPPHPHP 5 PPHPPPHPHHHHPPHHHHPHHPHHHPPHPHPHPPHPPPPPPHHPHHPH 6 HHHPPPHHPHPHHPHHPHHPHPPPPPPPHPHPPHPPPHPPHHHHHHPH 7 PHPPPPHPHHHPHPHHHHPHHPHHPPPHPHPPPHHHPPHHPPHHPPPH 8 PHHPHHHPHHHHPPHHHPPPPPPHPHHPPHHPHPPPHHPHPHPHHPPP 9 PHPHPPPPHPHPHPPHPHHHHHHPPHHHPHPPHPHHPPHPHHHPPPPH 10 PHHPPPPPPHHPPPHHHPHPPHPHHPPHPPHPPHHPPHHHHHHHPPHH Для кожної з 10 послідовностей зроблено 5 прогонів Q-learning алгоритму з різним поданням простору станів та дій для передбачення третинної структури білка, а саме пропоновано- го та наведеного у [9, 10, 12]. У рамках цих 5 прогонів для кожної з послідовностей підраховува- лось найменше ( minF ) та середнє ( avgF ) значення цільової функції (енергії). Основні результати наведено в табл. 2, де minF – рекорд із знайдених у кожному прогоні міні- мальних значень енергії, avgF – середнє для обраної кількості прогонів, optF – відоме оптимальне значення цільової функції для кожної з послідовностей. ТАБЛИЦЯ 2. Результати обчислювального експерименту Q-learning алгоритму з різними S, A, R(s, a) № optF Пропоновані S, A, r(s, a) S, A, r(s, a) із [9] S, A, r(s, a) із [10] S, A, r(s, a) із [12] minF avgF minF avgF minF avgF minF avgF 1 – 32 – 29 – 26.8 – 20 – 19 – 12 – 11.2 – 12 – 10.6 2 – 34 – 29 – 27.2 – 20 – 19 – 11 – 10.6 – 14 – 11.8 3 – 34 – 28 – 23.8 – 19 – 18 – 12 – 11.2 – 14 – 11.4 4 – 33 – 21 – 20 – 20 – 19 – 13 – 10.8 – 11 – 10.4 5 – 32 – 24 – 21.2 – 20 – 18.8 – 14 – 11.6 – 12 – 11 6 – 32 – 21 – 19.6 – 21 – 18.8 – 12 – 10.2 – 12 – 10.4 7 – 32 – 20 – 19.6 – 18 – 17.4 – 12 – 10.6 – 12 – 10.4 8 – 31 – 27 – 25.4 – 19 – 18.2 – 11 – 10.2 – 12 – 11 9 – 34 – 26 – 25.4 – 21 – 19 – 13 – 11.2 – 13 – 11.4 10 – 33 – 28 – 25.2 – 18 – 17.2 – 12 – 10.2 – 12 – 10.2 С.А. ЧОРНОЖУК 70 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 3 Також для кожної ітерації серед всіх прогонів для всіх послідовностей підраховувалась серед- ня кількість відвіданих пар (s, a), тобто тих, для яких Q(s, a) вже містило значення, що відрізняють- ся від значень за замовчуванням. Результати показано на рис. 11, 12. На цих рисунках вісь абсцис – номер ітерації, вісь ординат – кількість відвіданих пар. РИС. 11. Середня кількість відвіданих пар (s, a) зі звичайним масштабуванням вертикальної шкали РИС. 12. Середня кількість відвіданих пар (s, a) з логарифмічним масштабуванням вертикальної шкали Висновки. Результати обчислень показані на графіках рис. 11, 12, підтверджують те, що під- ходи [10, 12], адаптовані для передбачення третинної структури білків, породжують проблему над- НОВЕ ГЕОМЕТРИЧНЕ ПОДАННЯ ПРОСТОРУ «СТАНІВ-ДІЙ» Q-LEARNING АЛГОРИТМУ ... ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.3 71 лишкової та недостатньої інформативності простору станів системи відповідно. Пропонований та підхід із [9], у цьому сенсі виглядають збалансовано, що і відображають результати у табл. 2. До того ж використання пропонованого подання простору станів та дій разом із пропонованою фу- нкцією винагороди в алгоритмі Q-learning показало кращі результати, ніж використання всіх ін- ших подань. Отримані результати підтверджують перспективність подальших досліджень. Серед важливих напрямів таких досліджень зазначимо. 1. Для пропонованих станів та дій функція переходу : S A S   між станами за певною дією не є детермінованою (рис. 10, а, б). Перспективним виглядає дослідження щодо незначної зміни або розширення опису станів системи для того, щоб зробити функцію переходу детермінованою. Це може покращити якість розв’язків, отриманих Q-learning алгоритмом. 2. Цікавим виглядає комбінація Deep Q-learning підходу з пропонованими поданням простору станів та дій, а також функцією винагороди. Незважаючи на те, що пропонований простір станів частково вирішує проблеми і недостатньої, і надлишкової інформативності, апроксимація Q(s, a) за рахунок нейронних мереж або інших евристик може суттєво покращити роботу алгоритму. Список літератури 1. Dill K.A. Theory for the folding and stability of globular proteins. Biochemistry. 1985. 24 (6). P. 1501–1509. https://doi.org/10.1021/bi00327a032 2. Bazzoli A., Tettamanzi A.G.B. A Memetic Algorithm for Protein Structure Prediction in a 3D-Lattice HP Model. Ap- plications of Evolutionary Computing. 2004. 3005. P. 1–10. https://doi.org/10.1007/978-3-540-24653-4_1 3. Custodio F.L., Barbosa H.J., Dardenne L.E. A multiple minima genetic algorithm for protein structure prediction. Ap- plied Software Computing, Elsevier. 2014. 15. P. 88–99. https://doi.org/10.1016/j.asoc.2013.10.029 4. Boscovic B., Brest J. Genetic algorithm with advanced mechanisms applied to the protein structure prediction in a hy- drophobic-polar model and cubic lattice. Applied Soft Computing. 2016. 45. P. 61–70. https://doi.org/10.1016/j.asoc.2016.04.001 5. Morshedian A., Razmara J., Lotfi S. A novel approach for protein structure prediction based on estimation of distribu- tion algorithm. Software computing. 2019. 23. P. 4777–4788. https://doi.org/10.1007/s00500-018-3130-0 6. Nazmul R., Chetty M., Chowdhury A.R. Multimodal Memetic Framework for low-resolution protein structure predic- tion. Swarm and Evolutionary Computation, Elsevier. 2020. 52. https://doi.org/10.1016/j.swevo.2019.100608 7. Hulianytskyi L.F., Rudyk V.O. Development and analysis of the parallel ant colony optimization algorithm for solving the protein tertiary structure prediction problem. Information Theories and Applications. 2014. 21 (4). P. 392–397. 8. Chornozhuk S.A. The new simulated annealing algorithm for a protein structure folding problem. Komp’uternaa ma- tematika. 2018. 1. P. 118–124. http://dspace.nbuv.gov.ua/handle/123456789/161856 9. Jafari R., Javidi M.M. Solving the protein folding problem in hydrophobic-polar model using deep reinforcement learning. SN Applied Sciences, Springer. 2020. 2 (259). https://doi.org/10.1007/s42452-020-2012-0 10. Czibula G., Bocicor M., Czibula I. A reinforcement learning model for solving the folding problem. Int J Computa- tional Technology Applied. 2011. 2. P. 171–182. 11. Li Y., Kang H., Ye K., Yin S. FoldingZero: protein folding from scratch in hydrophobic-polar model. Deep reinforce- ment learning workshop (Oral) of NIPS. 2018. https://arxiv.org/abs/1812.00967 12. Dogan B., Olmez T. A novel state space representation for the solution of 2D-HP protein folding problem using rein- forcement learning methods. Applied Soft Computing, Elsevier. 2015. 26. P. 213–223. https://doi.org/10.1016/j.asoc.2014.09.047 13. Гуляницький Л.Ф., Чорножук С.А. Генетичний алгоритм з жадібним стохастичним оператором схрещування для передбачення третинної структури білка. Cybernetics and Computer Technologies. 2020. 2. P. 19–29. https://doi.org/10.34229/2707-451X.20.2.3 14. Гуляницкий Л.Ф., Рудык В.А. Проблема предсказания структуры протеина: формализация с использованием кватернионов. Кибернетика и системный анализ. 2013. 49 (4). С. 130–136. https://doi.org/10.1007/s10559-013- 9546-8 15. Sutton R.S., Barto A.G. Reinforcement Learning: An Introduction. MIT Press, 1998. 9 (5). P. 1054. https://doi.org/10.1109/TNN.1998.712192 https://doi.org/10.1021/bi00327a032 https://doi.org/10.1007/978-3-540-24653-4_1 https://www.sciencedirect.com/science/article/pii/S0957417409003923#! https://doi.org/10.1016/j.asoc.2013.10.029 https://doi.org/10.1016/j.asoc.2016.04.001 https://doi.org/10.1007/s00500-018-3130-0 https://doi.org/10.1016/j.swevo.2019.100608 http://icyb180.org.ua/staff/hulianytskyi/ http://icyb180.org.ua/staff/rudyk/ http://dspace.nbuv.gov.ua/handle/123456789/161856 https://doi.org/10.1007/s42452-020-2012-0 https://arxiv.org/abs/1812.00967 https://doi.org/10.1016/j.asoc.2014.09.047 https://doi.org/10.34229/2707-451X.20.2.3 https://doi.org/10.1007/s10559-013-9546-8 https://doi.org/10.1007/s10559-013-9546-8 https://doi.org/10.1109/TNN.1998.712192 С.А. ЧОРНОЖУК 72 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 3 16. Yue K., Fiebig K.M., Thomas P.D., Chan H.S., Shakhnovich E.I., Dill K.A. A Test of Lattice Protein Folding Algo- rithms. Proceedings of the National Academy of Sciences. 1995. 92 (1). P. 325–329. https://doi.org/10.1073/pnas.92.1.325 Одержано 21.08.2020 Чорножук Сергій Анатолійович, аспірант Інституту кібернетики імені В.М. Глушкова НАН України, Київ. сhornozhuk@gmail.com УДК 519.8 С.А. Черножук Новое геометрическое представление пространства «состояние-действие» Q-learning алгоритма в проблеме предсказания пространственной структуры белка Институт кибернетики имени В.М. Глушкова НАН Украины, Киев Переписка: chornozhuk@gmail.com Введение. Сворачивание пространственной белковой структуры – важная и актуальная проблема вычислительной биологии. Рассматривая математическую модель задачи, можно легко сделать вывод, что поиск оптимального положения белка в трехмерной сетке является NP-сложной задачей. Следова- тельно, для решения проблемы можно использовать некоторые методы обучения с подкреплением, такие как Q-learning. В статье предлагается новое геометрическое представление пространства «состоя- ние-действие», которое существенно отличается от всех альтернативных представлений, используемых для этой задачи. Цель роботы. Анализ существующих подходов к представлению пространств состояний и дей- ствий для алгоритма Q-learning для задачи предсказания трехмерной структуры белков, выявление их преимуществ и недостатков, предложение нового геометрического представления пространства «состо- яние-действие». Дальше необходимо сравнить существующие и предлагаемые подходы, сделать выво- ды и описать возможные будущие шаги дальнейших исследований. Результат. Работа предложенного алгоритма сравнивается с другими на основе 10 известных цепочек длиной 48, впервые предложенных в [16]. Для каждой из цепочек алгоритм Q-learning с пред- ложенным представлением пространства «состояние-действие» превзошел тот же алгоритм Q-обучения с альтернативными существующими представлениями пространств «состояние-действие» как с точки зрения средних, так и минимальных значений энергии полученных положений белков. Более того, множество существующих представлений используется для двумерных предсказаний структуры белка. Однако в ходе экспериментов как существующие, так и предлагаемое представления были немного изменены или доработаны для решения проблемы в 3D, что является более сложной задачей с точки зрения вычислений. Вывод. Экспериментально подтверждено качество алгоритма Q-learning с предложенным геомет- рическим представлением пространства «состояние-действие». Следовательно, доказано, что дальней- шие исследования перспективны. Более того, уже было предложено несколько шагов будущих исследо- ваний, таких как объединение предлагаемого подхода с методами глубокого машинного обучения. Ключевые слова: пространственная структура белка, комбинаторная оптимизация, относительное кодирование, машинное обучение, Q-обучение, уравнение Беллмана, пространство состояний, пространство действий, базис в трехмерном пространстве. https://doi.org/10.1073/pnas.92.1.325 mailto:сhornozhuk@gmail.com mailto:chornozhuk@gmail.com НОВЕ ГЕОМЕТРИЧНЕ ПОДАННЯ ПРОСТОРУ «СТАНІВ-ДІЙ» Q-LEARNING АЛГОРИТМУ ... ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.3 73 UDC 519.8 S. Chornozhuk The New Geometric “State-Action” Space Representation for Q-Learning Algorithm for Protein Structure Folding Problem V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv Correspondence: chornozhuk@gmail.com Introduction. The spatial protein structure folding is an important and actual problem in computational biology. Considering the mathematical model of the task, it can be easily concluded that finding an optimal protein conformation in a three dimensional grid is a NP-hard problem. Therefore some reinforcement learning techniques such as Q-learning approach can be used to solve the problem. The article proposes a new geometric “state-action” space representation which significantly differs from all alternative repre- sentations used for this problem. The purpose of the article is to analyze existing approaches of different states and actions spaces repre- sentations for Q-learning algorithm for protein structure folding problem, reveal their advantages and disad- vantages and propose the new geometric “state-space” representation. Afterwards the goal is to compare exist- ing and the proposed approaches, make conclusions with also describing possible future steps of further re- search. Result. The work of the proposed algorithm is compared with others on the basis of 10 known chains with a length of 48 first proposed in [16]. For each of the chains the Q-learning algorithm with the proposed “state- space” representation outperformed the same Q-learning algorithm with alternative existing “state-space” rep- resentations both in terms of average and minimal energy values of resulted conformations. Moreover, a plenty of existing representations are used for a 2D protein structure predictions. However, during the experiments both existing and proposed representations were slightly changed or developed to solve the problem in 3D, which is more computationally demanding task. Conclusion. The quality of the Q-learning algorithm with the proposed geometric “state-action” space representation has been experimentally confirmed. Consequently, it’s proved that the further research is prom- ising. Moreover, several steps of possible future research such as combining the proposed approach with deep learning techniques has been already suggested. Keywords: Spatial protein structure, combinatorial optimization, relative coding, machine learning, Q- learning, Bellman equation, state space, action space, basis in 3D space. mailto:chornozhuk@gmail.com

Нове геометричне подання простору «станів-дій» Q-learning алгоритму в проблемі передбачення третинної структури білка

Institution

Ähnliche Einträge