Складність задач та ефективність процедур розпізнавання

Размещено на http://www.allbest.ru/

Національна академія наук України

Інститут кібернетики імені В.М. Глушкова

УДК 519.217.2

Автореферат

дисертації на здобуття наукового ступеня кандидата фізико-математичних наук

СКЛАДНІСТЬ ЗАДАЧ ТА ЕФЕКТИВНІСТЬ ПРОЦЕДУР РОЗПІЗНАВАННЯ

01.05.01 - теоретичні основи інформатики та кібернетики

ВАСИЛЬЄВ Сергій В'ячеславович

Київ - 2008

Дисертацією є рукопис.

Робота виконана в Інституті кібернетики імені В.М. Глушкова НАН України.

Науковий керівник: доктор фізико-математичних наук, професор,

Гупал Анатолій Михайлович,

Інститут кібернетики ім. В.М. Глушкова НАН України, завідувач відділу.

Офіційні опоненти: доктор фізико-математичних наук, професор,

Іванов Олександр Володимирович,

Київський національний університет «КПІ»,

доктор фізико-математичних наук,

старший науковий співробітник

Шаріфов Фірдоусі Ахун-огли,

Інститут кібернетики ім. В.М. Глушкова НАН України.

Захист відбудеться 23.05. 2008 р. о 11 годині на засіданні

Спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики ім. В.М. Глушкова НАН України за адресою:

03680, МСП, Київ-187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитись в науково-технічному архіві інституту.

Автореферат розісланий 23.04.2008 р.

Вчений секретар

спеціалізованої вченої ради СИНЯВСЬКИЙ В.Ф.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

розпізнавання білок байєсівський генетичний

Дисертаційна робота присвячена дослідженню ефективності байєсівських процедур розпізнавання на таких структурах, як незалежні ознаки та нестаціонарні ланцюги Маркова, застосуванню цих процедур для передбачення вторинної структури білків, статистичному аналізу послідовностей ДНК.

Статистична теорія відновлення залежностей по емпіричним даним розроблена В.Н. Вапніком і А.Я. Червоненкісом в кінці 60-х - на початку 70-х р. Ця теорія стала загальновідомою в середині 80-х. В наш час вона активно розвивається і застосовується для обґрунтування різноманітних алгоритмів машинного навчання.

В.Н. Вапнік і А.Я. Червоненкіс були одними із перших, хто надав задачам розпізнавання строге математичне трактування. В подальшому ця теорія привернула увагу багатьох дослідників. В роботах відмічається, що задачі розпізнавання зводяться до мінімізації середнього ризику в спеціальному класі розв'язуючих правил.

Основним результатом теорії є кількісні оцінки, які зв'язують узагальнюючу властивість алгоритмів з деякими характеристиками вибірки і методу навчання, зокрема, з довжиною навчальної вибірки і складністю родини алгоритмів. Ці оцінки необхідні для того, щоб передбачати, наскільки добре буде працювати побудований алгоритм.

Проте, існує й інша точка зору: спеціалісти вбачають проблему в тому, щоб знайти такі описи об'єктів, при яких можна побудувати ефективні і навіть оптимальні процедури розпізнавання. В дисертації будемо дотримуватись цього принципу: на основі байєсівського підходу будуть побудовані ефективні процедури розпізнавання для таких структур об'єктів, як ланцюги Маркова і незалежні ознаки.

Основні поняття і означення. Нехай задано множину об'єктів X, множину відповідей Y (станів об'єктів), і існує цільова функція y*:X>Y, значення якої y_i=y*(xⁱ) відомі на кінцевій підмножині об'єктів . Сукупність пар X^l=(xⁱ ,y_i)^l_i=1 називаються навчальною вибіркою.

Задача навчання полягає в тому, щоб відновити функціональну залежність між об'єктами і відповідями, тобто побудувати відображення a:X>Y. Алгоритм a(x) має володіти узагальнюючою властивістю, тобто наближати цільову функцію y*(xⁱ) не тільки на об'єктах навчальної вибірки, але й на усій множині X.

Ймовірнісна постановка задачі. Точний опис об'єкта може бути досягнуто при достатньо великому (або нескінченому) числі ознак, які визначають об'єкт. Тому одному і тому самому опису x можуть відповідати різні об'єкти, а отже і ціла множина відповідей (станів об'єктів). Наприклад, в задачах передбачення просторової структури білків, розглянутих в дисертації, кожна амінокислота може перебувати в трьох станах, які визначають вторинну структуру білка. Для формалізації цих міркувань вводиться ймовірнісна постановка задачі.

Замість існування невідомої цільової функції y*(x) припускається, що існує невідомий ймовірнісний розподіл p(y|x) на множині XЧY, згідно з яким отримана вибірка пар X^l=(xⁱ ,y_i)^l_i=1, x - неперервний вектор x=(x₁, x₂,…, x_n) розмірності n; стан y приймає два значення: нуль і одиниця.

Прийнято рахувати, що на просторі векторів X існує невідома нам ймовірнісна міра P(x). У відповідності з P(x) випадково і незалежно з'являються ситуації x, котрі класифікуються за допомогою правила p(y|x), тобто будується навчальна послідовність X^l=(xⁱ,y_i)^l_i=1. Для будь-якого розв'язуючого правила a(x) визначається якість навчання як ймовірність різноманітної класифікації за допомогою правила a(x) і правила p(y|x). Чим менша ця ймовірність, тим вище якісь навчання. Формально якість розв'язуючого правила можна записати у вигляді

. (1)

Мінімізація середнього ризику (1) є узагальненням класичних задач, які розв'язуються за допомогою метода найменших квадратів, тобто коли спостереженню x=(x₁, x₂,…, x_n) відповідає не один, а декілька станів об'єктів (результатів експериментів). В роботах В.Н. Вапніка, А.Я. Червоненкіса та їх послідовників для мінімізації середнього ризику (1) розвиваються методи мінімізації емпіричного ризику по емпіричним даним X^l=(xⁱ,y_i)^l_i=1.

В дисертації розвиваються методи мінімізації середнього ризику

(2)

для дискретного випадку, де усереднення проводиться по усім дискретним векторам x=(x₁, x₂,…, x_n) та скінченій множині станів y.

Актуальність теми полягає в тому, щоб розробити ефективні (оптимальні) процедури мінімізації середнього ризику (2) для таких структур об'єктів, як ланцюги Маркова і незалежні ознаки, та отримати верхні та нижні оцінки похибок процедур від вхідних параметрів задачі. Побудова оцінок в дискретному випадку є нетривіальною задачею, оскільки заздалегідь невідомо, як кількість станів об'єктів, кількість ознак і кількість значень ознак будуть представлені в оцінках процедур розпізнавання.

Зв'язок роботи з науковими програмами, планами, темами. Дослідження, результати яких увійшли до дисертаційної роботи, були проведені в рамках планових фундаментальних досліджень ІК НАН України по темах: 1) ІП.235.07 “Теоретичні основи і принципи побудови ефективних процедур індуктивного виводу з поліноміальними оцінками погрішності” 2003-2005 рр., № 0103U003266; 2) ВФ.235.08 “Розробка математичних моделей для пошуку структурних закономірностей запису генетичної інформації на основі статистичного аналізу геномів” 2006-2010рр., № 0106U000548. Створено інформаційну технологію “Інформаційна технологія аналізу послідовностей ДНК” у рамках планових фундаментальних досліджень ВК.245.21 “Забезпечення підвищення надійності функціонування апаратно-програмних засобів суперкомп'ютерних систем СКІТ-1 і СКІТ-2, розробка інтелектуальних інформаційних технологій та прикладного програмного забезпечення для розв'язання складних завдань в економіці, національній безпеці, обороні України та в інших галузях народного господарства”, 2005р., №0105U005692. Створено інформаційну технологію “Інформаційна технологія розпізнавання структурних елементів просторової конформації білків” у рамках планових фундаментальних досліджень ВК.245.19 “Розробка та створення ряду високопродуктивних інтелектуальних ЕОМ на основі кластерних архітектур для розв'язку традиційних обчислювальних задач та задач штучного інтелекту”, 2006р., №0104U007390.

Мета і завдання дослідження. Метою дослідження є знаходження оцінки складності класу задач розпізнавання у дискретному випадку, асимптотичної верхньої оцінки байєсівської процедури розпізнавання для ланцюгів Маркова, ефективних методів розпізнавання вторинної структури білків на основі байесівської процедури.

В дисертації вирішуються наступні задачі:

отримати нижню оцінку складності класу задач розпізнавання у дискретному випадку в залежності від розмірів класів навчаючої вибірки, кількості ознак та числа значень ознак;

показати, що байєсівська процедура розпізнавання у булевому випадку еквівалентна процедурі розпізнавання, яка ґрунтується на використанні відокремлюючої гіперплощини;

розробити апарат розпізнавання гіпотез відносно стаціонарності (нестаціонарності) перехідних ймовірностей в моделях ланцюгів Маркова, а також визначення порядку ланцюга Маркова;

обґрунтувати байєсівську процедуру розпізнавання на нестаціонарних ланцюгах Маркова;

розробити методи розпізнавання вторинної структури білків на основі байєсівської процедури розпізнавання на нестаціонарних ланцюгах Маркова;

дослідити особливості запису генетичної інформації в послідовностях ДНК людини та геномах вищих організмів;

створити необхідне програмне забезпечення і провести експерименти на реальних даних з метою підтвердження теоретичних результатів отриманих у дисертації;

розробити інформаційну технологію розпізнавання вторинної структури білків для кластерного комп'ютера.

Об'єктом дослідження є верхні та нижні оцінки похибок процедур розпізнавання; емпіричні оцінки перехідних ймовірностей на моделях ланцюгів Маркова певного порядку; генетична інформація в послідовностях ДНК та білках.

Предметом дослідження є ефективність байєсівської процедури розпізнавання для таких структур об'єктів, як ланцюги Маркова та незалежні ознаки; розпізнавання вторинної структури білків; закономірності запису генетичної інформації в послідовностях ДНК вищих організмів.

Методи дослідження. Для вирішення поставлених задач використовуються методи теорії ймовірностей та математичної статистики, теорії мінімізації середнього ризику, результати теорії розпізнавання гіпотез із застосуванням критерію ч².

Наукова новизна отриманих результатів. Отримані результати є новими та такими, що узагальнюють існуючі.

Отримано поліноміальну нижню оцінку складності класу задач розпізнавання у дискретному випадку для незалежних ознак в залежності від розмірів класів навчаючої вибірки, кількості ознак та числа значень ознак. Нижня оцінка похибки відрізняється від верхньої оцінки байєсівської процедури на абсолютну константу, тобто байєсівська процедура розпізнавання є оптимальною.

У булевому випадку побудована процедура розпізнавання, яка ґрунтується на використанні відокремлюючої гіперплощини.

Обґрунтовано застосування критерію ч² в задачах розпізнавання гіпотез відносно стаціонарності перехідних ймовірностей для ланцюгів Маркова першого порядку, а також визначення порядку ланцюга Маркова.

Побудовано байєсівську процедуру розпізнавання на нестаціонарних ланцюгах Маркова. У спеціальному випадку, якщо початковий розподіл ймовірностей ланцюга Маркова є стаціонарним, показано, що оцінки похибки байєсівської процедури розпізнавання на ланцюгах Маркова аналогічні оцінкам для незалежних ознак. Виведено нові співвідношення комплементарності в запису генетичної інформації по одному ланцюгу ДНК.

Практичне значення отриманих результатів. Проведено дослідження ефективності байєсівських процедур розпізнавання на нестаціонарних ланцюгах Маркова, отримано поліноміальні оцінки похибки процедур розпізнавання. Байєсівські процедури мають високу точність передбачення вторинної структури білків (80%). Це вказує на перспективність використання таких методів в задачах синтезу штучних білків, пошуку закономірностей згортання білків в просторові структури.

Проведений статистичний аналіз хромосом ДНК людини, виведено важливі співвідношення комплементарності щодо запису генетичної інформації упродовж одного ланцюга ДНК, які стабільні по всіх 24-х хромосомах людини. Ці результати, на наш погляд, є фундаментальними в молекулярній біології і пояснюють ряд важливих особливостей функціонування ДНК і синтезу білків.

Дослідження виконувались на фактичному матеріалі, представленому в Інтернеті сервером NCBI (National Center of Biotechnology Information), який є найбільшою біологічною базою даних.

Обґрунтовано використання кластерних комп'ютерів для задач аналізу послідовностей ДНК і розпізнавання просторової структури білків. Показано, що такі задачі ідеально розпаралелюються, можливо організувати процес обчислень без обміну повідомлень між різними процесами, що дає оптимальну швидкодію.

Особистий внесок здобувача. В роботі [1] автором реалізовано алгоритм для обчислення частот і перехідних ймовірностей послідовностей ДНК для кластерного комп'ютера, проведені числові обрахунки, виведені нові співвідношення комплементарності основ. В [2] проведені спрощення в доведенні теореми про нижню оцінку, показано, що похибка процедури Байєса строго позитивна за умови відсутності інформації про стани об'єктів. В [3] розроблено метод і реалізовано алгоритм розпізнавання вторинної структури білків, проведено порівняльний аналіз для різних порядків ланцюга Маркова, проведено числові розрахунки на кластерному комп'ютері. В [4,5] автором реалізовано алгоритм паралельних обчислень для кластерного комп'ютера, проведені чисельні розрахунки, проаналізовано результати. В [6] побудовано таблиці розподілу перехідних ймовірностей і порівняно з таблицями спряжених ознак. В [7] виведено статистичний критерій ч² у вигляді відношення ймовірностей ланцюга, підрахованих для двох послідовних порядків. В [8,9] автором поставлено числові експерименти і розроблено алгоритми для проведення розрахунків на кластерному комп'ютері.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися та обговорювалися на наукових семінарах в Інституті кібернетики ім. В.М. Глушкова НАН України та Закарпатському Державному Університеті, а також міжнародних симпозіумах: «Вопросы оптимизации вычислений ХХХIII» (с. Кацивеллі, Крим, 2005), «Вопросы оптимизации вычислений ХХХIV» (с. Кацивеллі, Крим, 2007).

Публікації. Основні результати дисертації опубліковано в семи статтях у наукових журналах, з них шість у фахових виданнях за спеціальністю, а також у матеріалах і тезах двох міжнародних конференцій.

Структура та обсяг роботи. Дисертація складається із вступу, п'яти розділів, висновків, списку використаних джерел, що містить 79 найменувань. Загальний обсяг дисертаційної роботи - 145 сторінок. Робота включає 4 рисунки, 11 таблиць.

ЗМІСТ РОБОТИ

У вступі аналізується стан наукової проблеми, обґрунтовується актуальність вибраної тематики, формулюються мета і задачі дослідження, наводиться зміст одержаних результатів.

Перший розділ присвячено огляду методів розпізнавання та навчання. В огляді охоплені питання сучасної теорії узагальнюючої здібності методів розпізнавання. У підрозділі 1.1 описана постановка задачі навчання по прецедентах. У підрозділі 1.2 дано огляд теорії мінімізації емпіричного ризику. Дано оцінки алгоритмів, побудованих на основі даної теорії, викладено зауваження щодо описаної теорії.

Основним результатом теорії відновлення залежностей по емпіричним даним є кількісні оцінки, які зв'язують узагальнюючу властивість алгоритмів з довжиною навчаючої вибірки і складністю родини алгоритмів. Головна ціль теорії - вказати шляхи підвищення узагальнюючої властивості алгоритмів, що навчаються, зокрема, вибрати оптимальну структуру моделі.

Спочатку розглядається випадок скінченої множини параметричних функціональних залежностей F(x,б) (клас розв'язуючих правил). Усі функції F(x,б) - характеристичні, тобто приймають два значення: нуль і одиниця.

Розглядається задача мінімізації середнього ризику

I(б)=P(б)=?(y - F(x,б))²P(x,y)dxdy (3)

по емпіричним даним x¹,y₁,…,x^l,y_l.

Теорема 1.1. Нехай множина розв'язуючих правил складається з N елементів, і нехай для розв'язуючих правил F(x,б_i) частоти помилок на навчаючій послідовності довжини l дорівнюють v(б_i). Тоді з імовірністю 1-з можна стверджувати, одночасно для усіх розв'язуючих правил виконуються нерівності

. (4)

Очевидно, що скінчене число розв'язуючих правил є занадто бідною множиною для неперервних задач розпізнавання. Тому робиться спроба узагальнення цих результатів на випадок нескінченого числа розв'язуючих правил.

Нехай задано нескінчену множину S розв'язуючих правил F(x,б) і дана вибірка x¹,…,x^l. Ця вибірка, в загальному випадку може бути розділена на два класи способами (за допомогою правила F(x,б) множина ділиться на дві підмножини - підмножину, на якій F(x,б) = 1, і на підмножину, на якій F(x,б) = 0). Число таких способів розділення залежить як від класу розв'язуючих правил F(x,б), так і від складу вибірки. Це число позначається величиною

Д^S(x¹,…,x^l).

Визначення. Функція

m^S (l)=max Д^S(x¹,…,x^l), (5)

де максимум вибирається по усім можливим вибіркам довжини l, називається функцією росту системи подій, яка утворена розв'язуючими правилами F(x,б).

В роботі Вапніка В.Н. (Восстановление зависимостей по эмпирическим данным.-М.: Наука, 1979) відмічається, що максимум в (5) завжди досягається, тому що індекс Д^S(x¹,…,x^l) приймає скінчене число значень. Проте це зовсім не так, оскільки область визначення функції росту в неперервному випадку складає континуальну (рекурсивно не перераховану) множину. Замість операції максимуму в (5) потрібно застосовувати операцію супремуму. Необхідно організувати нескінчену (континуальну) множину вибірок довжини l, і потім до кожної вибірки застосувати нескінчене число розв'язуючих правил, які розділяють вибірку на два класи. В (5) не вказано механізму вибору усіх можливих векторів навчаючої вибірки, і тому треба довести, що функцію (5) можна ефективно обчислити. Інакше визначення функції росту у такому випадку сприймається як акт віри, і тому воно є неконструктивним і некоректним.

Теорема 1.2. Нехай F(x,б) - класс розв'язуючих правил обмеженої ємності h, і нехай v(б) - частота помилок, обчислена по навчаючій послідовності для правила F(x,б). Тоді з імовірністю 1-з можна стверджувати, що для усіх правил F(x,б) ймовірність помилкової класифікації міститься в межах

. (6)

З теореми 1.2 випливає, що для правила F(x,б_э), яке мінімізує емпіричний ризик, з імовірністю 1-з справедлива оцінка зверху

. (7)

Особливість ймовірнісних оцінок (4), (6), (7) полягає в тому, що в них входить невизначений параметр з. Необхідно задати цей параметр, підставити у формули і обчислити оцінку похибки. Для того, щоб ці оцінки мали високу надійність, параметр з треба покласти якомога ближчим до нуля. Внаслідок цього вони набувають завищеного характеру.

Перші оцінки узагальнюючої здібності були отримані в кінці 60-х років Вапніком і Червоненкісом. Їх числові значення були завищені і дозволяли лише на якісному рівні обґрунтовувати застосування деяких методів навчання. Однак для багатьох методів, які успішно застосовуються на практиці, строгі обґрунтування до сих пір не отримані. Вивід точних кількісних оцінок узагальнюючої здібності поки залишається відкритою проблемою.

Специфіка методів мінімізації емпіричного ризику полягає в тому, що вибірка X^L розбивається на навчаючу і контрольну підвибірки. Природно, що при такому скороченні вибірки ефективність алгоритму зменшується, оскільки в приведених вище оцінок фігурує довжина вибірки. Для байєсівських процедур розпізнавання, які досліджуються в дисертації, розбиття вибірки на навчаючу і контрольну проводити не треба, оскільки при підрахунку похибки враховується робота процедури на усій множині навчаючих вибірок.

В теорії Вапніка-Червоненкіса верхні оцінки похибки методу мінімізації емпіричного ризику отримані для вузького класу параметричних функцій. Тому функція a(x), яка мінімізує середній ризик (1), може не належати до класу параметричних функцій. Оскільки мінімум середнього ризику невідомий, то побудовані оцінки (6), (7) не визначають величину відхилення мінімуму емпіричного ризику від мінімуму (1).

Дотримуючись канонів теорії складності алгоритмів, задача розпізнавання в силу своєї специфіки в дискретному випадку визначається наступними вхідними параметрами: розмірами класів об'єктів в навчаючій вибірці, кількістю ознак і кількістю значень ознак. В оцінки (6), (7) розміри класів не входять. Цей факт, на наш погляд, є принципіальною помилкою. Можна уявити, наприклад, що експертна система будується тільки на класі хворих або здорових пацієнтів (або розміри цих класів відрізняються одне від одного в сотні разів), зрозуміло, що ефективних процедур розпізнавання в такому випадку побудувати не можна.

У підрозділі 1.3 описано баєсівський підхід до мінімізації середнього ризику і дано порівняльний аналіз цих двох підходів.

У другому розділі - отримано оцінки похибки байєсівської процедури розпізнавання, які поліноміально залежать від числа ознак, кількості класів та кількість значень ознак.

У підрозділі 2.1 описана постановка задачі розпізнавання в дискретному випадку.

Нехай маємо скінчену множину B описів об'єктів b=(x₁, x₂,…, x_n, f); тут n - натуральне число, x_j {0,1,…,g-1}, j=1,2,…,n; ; g, h - натуральні числа, g>2, h>2.

Нехай на множині B визначений розподіл ймовірностей P, що нам заздалегідь невідомий. Нехай деякій опис об'єкту отримано з множини B незалежно від вибірки D згідно розподілу P, причому відомі лише значення ознак x₁, x₂,…, x_n. Вимагається по цих значеннях та по навчальній вибірці D визначити значення цільової ознаки f.

Далі розглядаються необхідні поняття: клас задач, функція та процедура розпізнавання, байєсівська процедура розпізнавання, похибка процедури розпізнавання.

Функцію розпізнавання a(x) слід обирати таким чином, щоб якомога більшим було значення P(f=a(x)). Оскільки кількість функцій a(x) скінченна, то серед них існує найкраща функція розпізнавання a*(x) така, що для усіх a(x) справедливо P(a*)?P(a). Похибка функції a на розподілі P - величина

v(a,P)=?P(d,a*(d))-P(d,a(d)). (8)

Процедура розпізнавання Z - однозначна функція, що визначена на множині {D} допустимих значень навчаючої вибірки та приймає значення на множині функцій розпізнавання; процедура Z будує функцію a по навчаючій вибірці , тобто a=Z(). Похибка процедури Z на розподілі P - величина

v(Z,P)= ? v(a,P)P₁(D=), (9)

де a=Z(), - ймовірність події, що полягає у тому, що навчаюча вибірка D приймає значення . Усереднення в (9) - ключовий момент в оцінюванні похибки індуктивних процедур, без нього неможливо отримати поліноміальні оцінки похибки для байєсівської процедури розпізнавання.

Клас задач C=C(g,h,l^(h),n) - сукупність усіх можливих розподілів ймовірності P на множині B разом з величинами g,h,l^(h),n. Множина задач та множина розподілів даного класу знаходяться у взаємно-однозначній відповідності. Похибкою процедури розпізнавання Z на класі C є число

v(Z,C)=sup v(Z,P),

а складністю класу C - число

м(C)=inf v(Z,C)=inf sup v(Z,P).

Нехай d=(d₁, d₂,…, d_n) - цілочисловий вектор. Вважаємо, що розподіли P з класу C для кожного d задовольняють умову

, ,

що означає незалежність ознак x_j для кожного класу об'єктів.

Визначимо випадкові величини , що залежать від d та i як від параметрів, за допомогою формули

, , (10)

де m(d_j,i) - кількість значень рівних d_j, j-ї ознаки у j -му стовпчику матриці D_i; m_i - кількість значень цільової ознаки f, рівних i, у векторі D_h. Оберемо a(d), яке дорівнює мінімальному числу s з множини {0,1,…,h-1} такому, що

о(d,s)? о(d,i),i {0,1,…,h-1}. (11)

Процедуру розпізнавання, що визначається співвідношеннями (10), (11), позначимо Z_B. Зауважимо, що величини являють собою наближені значення ймовірностей P(f=i|x₁=d₁,x₂=d₂,…,x_n=d_n), обчислених за формулою Байєса, тому процедуру розпізнавання Z_B будемо називати байєсівською.

Теорема 2.1. Існує абсолютна константа b₀<? така, що справедлива нерівність

,

де .

В верхню оцінку похибки байєсівської процедури розпізнавання входять розміри класів в навчаючій вибірці, а не об'єм вибірки, як це спостерігається в оцінках методів мінімізації емпіричного ризику.

У підрозділі 2.2 доведено леми, в яких показано, що якщо в навчальній вибірці відсутній один з класів об'єктів, то будь-яка процедура працює погано і її похибка строго додатна.

Лема 2.1. Якщо l₀=0, то для будь-якої індуктивної процедури Z існує такий розподіл P, що її похибка

v(Z,P)?C>0.

Наступний результат леми 2.2 показує, що при відсутності у вибірці D вектора D_h, будь-яка процедура працює також незадовільно.

Лема 2.2. Якщо l_h=0, то для будь-якої індуктивної процедури існує такий розподіл , що

v(Z,P)?C>0.

У підрозділі 2.3 доведено важливу теорему про оцінку знизу складності класу задач C.

Теорема 2.2. Існує абсолютна константа b₁>0 така, що справедливо наступне. Якими б не були натуральні числа g, h, n, що задовольняють нерівності g?2, 2?h?2gⁿ цілі невід'ємні числа l₀,l₁,…,l_h і процедура розпізнавання Z, існує такий розподіл ймовірностей P з класу C, що виконується нерівність

, (12)

де .

Доведення нерівності (12) проводиться значно складніше, ніж у булевому випадку, тому що в (12) присутня величина h, яка задає число класів і величина g, яка задає кількість значень ознак.

У підрозділі 2.4 побудовано відокремлюючу гіперплощину для байєсівської процедури розпізнавання.

Нехай d=(d₁, d₂,…, d_n) - булів вектор. Процедура відокремлюючої гіперплощини (позначимо її R) полягає в наступному. Якщо виконується нерівність , то вектор d відноситься до класу об'єктів 0, інакше - до класу об'єктів 1; тут б₀,б₁,..,б_n - дійсні числа. Справедлива наступна теорема.

Теорема 2.3. Байєсівська процедура Z_B у булевому випадку еквівалентна процедурі розпізнавання, яка побудована на використанні відокремлюючої гіперплощини R.

В третьому розділі обґрунтовується використання байєсівської процедури на нестаціонарних ланцюгах Маркова. Показано, що оцінки похибки байєсівської процедури аналогічні оцінкам побудованих для незалежних ознак.

Байєсівські процедури оптимальні на таких структурах як ланцюги Маркова та незалежні ознаки. Вони мають поліноміальні оцінки похибки в залежності від розмірів навчальних вибірок та кількості ознак. При побудові процедур розпізнавання необхідно вирішити питання відносно стаціонарності чи не стаціонарності перехідних ймовірностей, а також відносно порядку ланцюга Маркова. Розв'язавши серію таких задач для визначених даних (навчальної вибірки), отримуємо конкретну модель ланцюга Маркова, яку будемо використовувати в реальних задачах розпізнавання для даної конкретної вибірки.

У підрозділі 3.1 розв'язується задача розпізнавання гіпотез відносно стаціонарності перехідних ймовірностей. Обґрунтовано використання критерію ч² в задачах розпізнавання гіпотез відносно стаціонарності перехідних ймовірностей для ланцюгів Маркова.

Нехай маємо m об'єктів, що описуються ланцюгом Маркова. Позначимо моменти спостереження t=0,1,…,T, стани i=1,2,…,k; m_ij(t) (i,j=1,2,…,k, t=0,1,…,T) - кількість об'єктів у стані j в момент часу t при заданому стані i в момент часу t-1; p_ij(t) (i,j=1,2,…,k, t=0,1,…,T) - ймовірність стану j в момент часу t при стані i в момент часу t-1; p_ij (i,j=1,2,…,k) - ймовірність стану j при заданому стані i в попередній момент часу.

Доведено наступну лему.

Лема 3.1. При нульовій гіпотезі, що ланцюг Маркова є стаціонарним і альтернативній гіпотезі, що перехідні ймовірності залежать від часу, сума



має граничний розподіл ч² з k(k-1)(T-1) ступенями свободи.

У підрозділі 3.2 виведено статистичний критерій ч² у вигляді логарифма відношення ймовірностей ланцюга, підрахованим для двох послідовних порядків Доведення проводиться за допомогою результатів підрозділу 3.1. Доведено наступну лему.

Лема 3.2. При нульовій гіпотезі відносно ланцюга першого порядку і альтернативній гіпотезі, що ланцюг - другого порядку величина

має асимптотичний розподіл ч² з k(k-1)² ступенями свободи, де , m_ijk(t) - число об'єктів, які знаходяться в стані i в момент часу t-2, стані j в момент часу t-1 і стані k в момент часу t.

В підрозділі 3.3 проведено обґрунтування байєсівської процедури розпізнавання на нестаціонарних ланцюгах Маркова. У спеціальному випадку, якщо початковий розподіл ймовірностей ланцюга Маркова є стаціонарним, показано, що асимптотичні оцінки похибки байєсівської процедури розпізнавання на ланцюгах Маркова аналогічні оцінкам для незалежних ознак.

В четвертому розділі розроблені і досліджені методи розпізнавання вторинної структури білків на основі байєсівської процедури розпізнавання.

На сьогодні спільними зусиллями вчених всього світу розшифровано геноми людини, шимпанзе, куриці, риби, деяких рослин та більше тисячі бактерій. Основне питання сучасної молекулярної біології: яку функцію виконує визначений ген? Ген - це частина молекули ДНК, яка кодує відповідний йому білок. Знаючи нуклеотидну послідовність гена, можна однозначно визначити амінокислотну послідовність білка, оскільки кожна із 20 амінокислот кодується цілком певним триплетом нуклеотидів (кодоном). Після трансляції послідовності амінокислот з молекули РНК білок відразу набуває просторової конфігурації. Саме просторова конфігурація білка визначає його функціональність, оскільки білки в живих організмах взаємодіють як трьохвимірні об'єкти в просторі. Тому у дослідженнях білків та їх функцій дотримуються доктрини «послідовність-структура-функціональність». Це означає, що функціональність білка однозначно визначається його просторовою структурою, а просторова конфігурація однозначно задається його амінокислотною послідовністю. У четвертому розділі розв'язана задача розпізнавання вторинної структури заданого білка по відомій амінокислотній послідовності і навчальній вибірці. При цьому розв'язується серія задач розпізнавання гіпотез для визначення порядку ланцюга Маркова, а також вирішення питання щодо його стаціонарності (для кожної навчальної вибірки).

У підрозділі 4.1 дано опис вторинної структури білка як предмета дослідження.

У підрозділі 4.2 проведено огляд сучасних методів передбачення вторинної структури білка.

У підрозділі 4.3 побудовано метод розпізнавання, оснований на передбаченні стану однієї амінокислоти в залежності від порядку ланцюга Маркова, який вибирається як модель, і від радіусу околу амінокислоти.

Вторинна структура білка визначається за допомогою процедури, принцип роботи якої базується на використанні формули Байєса:

, (13)

тут f - стан амінокислоти. Зазначимо, що кількість різних класів f дорівнює 60, оскільки 20 - кількість амінокислот, 3 - кількість вторинних структур. Тип вторинної структури визначається околом x₁, x₂,…, x_n з сусідніх амінокислот, розташованих зліва і справа від досліджуваної амінокислоти x_s (в числових розрахунках вибирається, як правило, центральною)

Для моделі ланцюга Маркова першого порядку ймовірність ланцюга x₁, x₂,…, x_n задається співвідношенням

, (14)

де P(x₁|f) - початковий розподіл, P(x₂|x₁,f) - нестаціонарні перехідні ймовірності.

Ймовірності в (13), (14) замінюються частотами, підрахованими на основі навчальних вибірок.

Проведені числові розрахунки показують, що байєсівські процедури розпізнавання, побудовані на основі моделі нестаціонарних ланцюгів Маркова порядків 3 і 4, успішно передбачають вторинну структуру білків. Підтверджено, що деякі оцінки перехідних ймовірностей виявляються нульовими через недостатній розмір навчальної вибірки. Тим не менше, навіть в такому випадку маємо прийнятні результати передбачення вторинної структури.

У підрозділі 4.4 виведено апріорну точність розпізнавання. При визначенні точності розпізнавання білка важливо оцінювати цю точність без порівняння розпізнаної структури з оригінальною. В реальних задачах розпізнавання нам невідома вторинна структура білка - її треба визначити. Назвемо цю величину оцінкою впевненості розпізнавання, і будемо визначати її значення у відсотках. Оцінку впевненості ми отримуємо на основі обчислених перехідних ймовірностей ланцюга Маркова для кожної амінокислоти.

Для вибірки з 19450 білків середній відсоток розпізнавання, підрахований на основі порівняння з оригінальними вторинними структурами, дорівнює 79,5% - апостеріорна оцінка (розпізнавання трійок на основі моделі ланцюга Маркова 2-го порядку и радіусом околу 14). Середній відсоток підрахований по попереднім оцінкам впевненості дорівнює 79,45% - апріорна оцінка. Апріорна оцінка дає можливість оцінити точність розпізнавання білка з невідомою вторинною структурою. Це означає, що отримавши на виході вторинну структуру, ми можемо вказати на приблизну точність розпізнавання.

У підрозділі 4.5 обґрунтовано застосування паралельних обчислень в задачах розпізнавання вторинної структури білків. Для визначення точності методу розпізнавання, необхідно визначити вторинну структуру усіх 19450 білків з навчаючої вибірки. На сучасному ПК для вирішення цієї задачі необхідно близько 200 годин машинного часу. На кластері з 64-ма вузлами час аналогічного обрахунку становитиме приблизно 200 хвилин (за умови ідентичного процесора і рівного об'єму оперативної пам'яті). Усі обчислення проводились на побудованих в інституті кібернетики кластерних суперкомп'ютерах СКІТ-1 та СКІТ-2. Дана задача ідеально розпаралелюється. Кожен процесор обробляє окремі назначені йому файли і процесори не обмінюються між собою повідомленнями; після виконання обчислень кожен процес записує результати у назначений йому вихідний файл. Тому швидкість обрахунку залежить від найбільшого із середніх значень довжин файлів назначених одному процесу. Це означає, що найдовше працювати буде той процесор, сумарна довжина файлів якого максимальна.

У п'ятому розділі розглянуто результати статистичного аналізу нуклеотидних послідовностей ДНК. ДНК має форму подвійної спіралі, інформація записана в чотирьох-літерному алфавіті основ: аденін (A), цитозин (C), гуанін (G), тимін (T). Відомо, що C - G, A - T - комплементарні пари основ, які зв'язують два ланцюга. Хромосоми - неперервні ділянки ДНК, в яких міститься інформація щодо тисяч генів, тому розрахунки проводяться на рівні усієї хромосоми, а не на рівні окремого гена. Проведений статистичний аналіз генома людини і декількох геномів вищих організмів (шимпанзе, риби, куриці).

Обчислення показали, що кількості основ A і T, а також C і G, підраховані по одній нитці ДНК, практично співпадають на усіх хромосомах. Тому по властивості комплементарності основ для кожної з двох ниток хромосом виконуються співвідношення

m(A)?m(T), m(C) ?m(G), (15)

де m(j) - число літер j, j{A,C,G,T}. Ми не ставимо знак рівності в (15) по наступним причинам: геном - динамічна структура, яка постійно піддається модифікаціям в процесі еволюції; геноми усіх людей, які населяють Землю відрізняються один від одного; наявність пробілів в геномі людини і в більшості інших геномів; має місце визначена точність секвенування геномів.

Запис і зчитування основ у першої нитки виконується зліва направо у напрямі -, а у комплементарної нитки в напрямі - справа наліво

Якщо припустити, що запис інформації в другій нитці проводиться по такій же схемі, що й у першої нитки, то кількість пар AC в першій нитці повинно співпадати з кількістю пар GT, оскільки в силу комплементарності парі AC на другій нитці відповідає пара GT на першій нитці. Те ж саме стосується інших пар. Розрахунки підтвердили це припущення: для пар літер виконуються наступні співвідношення комплементарності:

m(AC) ?m(GT), m(AG) ?m(CT),

m(TC) ?m(GA), m(TG) ?m(CA),

m(AA) ?m(TT), m(CC) ?m(GG).

Кодони (трійки основ) пов'язані наступними співвідношеннями компліментарності

,

де i,j,k{A,C,G,T} , , - антикодон кодона (ijk).

Статистичний аналіз усіх хромосом проводився за допомогою мультипроцесорної системи «СКІТ-1». Задача була розбита на 24 підзадачі (по числу хромосом генома людини), які виконувались в паралельному режимі без обміну даними між процесами, що забезпечує мінімальну затрату часу на обмін повідомленнями між процесорами і максимальну швидкодію системи.

Встановлені та підтверджені за допомогою кластерних комп'ютерів нові співвідношення комплементарності в хромосомах ДНК, які істотно доповнюють сучасні представлення відносно запису генетичної інформації в ДНК. На основі отриманих статистичних даних можні зробити висновок про те, що існують точні правила формування структури ДНК, які справедливі для усіх видів організмів.

ВИСНОВКИ

У дисертаційній роботі проведено детальний аналіз методів мінімізації емпіричного ризику і байєсівських процедур розпізнавання, а також побудованих похибок для цих методів. Виведено детерміновані нижні і верхні оцінки похибки байєсівської процедури розпізнавання у дискретному випадку для незалежних ознак. На основі критерію ч² розв'язано серію задач розпізнавання гіпотез відносно стаціонарності або нестаціонарності ланцюгів Маркова, а також визначення порядку ланцюга Маркова. Побудовано байєсівську процедуру розпізнавання на нестаціонарних ланцюгах Маркова. Проведено статистичний аналіз запису генетичної інформації в послідовностях ДНК людини та вищих організмів. На кластерному комп'ютері проведено обчислювальні експерименти розпізнавання вторинної структури білків на реальних даних з Всесвітнього банку даних білкових сполук.

Основні наукові результати дисертаційної роботи наступні

1. Отримано нижню оцінку складності класу задач розпізнавання у дискретному випадку в залежності від розмірів класів навчаючої вибірки, кількості ознак та числа значень ознак.

2. На основі байєсівської процедури розпізнавання у булевому випадку побудована оптимальна процедура розпізнавання, яка ґрунтується на використанні відокремлюючої гіперплощини.

3. Розроблено апарат розпізнавання гіпотез відносно стаціонарності (нестаціонарності) перехідних ймовірностей в моделях ланцюгів Маркова, а також визначення порядку ланцюга Маркова.

4. Обґрунтовано байєсівську процедуру розпізнавання на нестаціонарних ланцюгах Маркова. Отримано верхню оцінку похибки процедури від вхідних параметрів моделі.

5. Розроблено алгоритми розпізнавання вторинної структури білків на основі байєсівської процедури розпізнавання на нестаціонарних ланцюгах Маркова.

6. Встановлено комплементарні закономірності у запису генетичної інформації в послідовностях ДНК людини та вищих організмів.

7. Створено програмне забезпечення і проведено обчислювальні експерименти на реальних даних з метою підтвердження теоретичних результатів, отриманих у дисертації.

8. Розроблено інформаційну технологію розпізнавання вторинної структури білків на кластерному комп'ютері.

ОСНОВНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ ОПУБЛІКОВАНІ В ТАКИХ ПРАЦЯХ

Васильев С.В., Гупал А.М. Исследование структурных особенностей записи оснований в ДНК на кластерном компьютере // Комп'ютерні засоби, мережі та системи. - 2006. - №5. - C.61-66.

Белецкий Б.А., Вагис А.А., Васильев С.В., Гупал А.М. Сложность байесовской процедуры индуктивного вывода // Проблемы управления и информатики. - 2006. - №6 - С.55-70.

Белецкий Б.А., Васильев С.В., Гупал А.М. Предсказание вторичной структуры белков на основе байесовских процедур распознавания // Проблемы управления и информатики. - 2007. - №1 - С.61-69.

Сергиенко И.В., Белецкий Б.А., Васильев С.В., Гупал А.М. Предсказание вторичной структуры белков на основе байесовских процедур распознавания на цепях Маркова // Кибернетика и системный анализ. - 2007. - №2 - С.59-64.

Белецкий Б.А., Васильев С.В., Вагис А.А., Гупал А.М. Процедуры распознавания вторичной структуры белков // Проблемы управления и информатики. - 2007. - № 4. - С. 134-139.

Белецкий Б.А., Вагис А.А., Васильев С.В.. Распознавание гипотез в моделях цепей Маркова // Компьютерная математика. - 2007. - №1 - С.104-112.

Белецкий Б.А., Вагис А.А., Васильев С.В. Распознавание гипотез для цепей Маркова данного порядка // Компьютерная математика. - 2007. - № 2 - С.116-121.

Гупал А.М., Васильєв С.В. Використання мультипроцесорних комп'ютерів для статистичного аналізу генома людини // Международный симпозиум «Вопросы оптимизации вычислений ХХХIII». Сборник тезисов. Пгт. Кацивелли, Крым, Украина. 18-23 сентября 2005 г. С.67.

Белецкий Б.А., Васильев С.В. Эффективность байесовских процедур распознавания для предсказания вторичной структуры белков // Международный симпозиум «Вопросы оптимизации вычислений ХХХIV». Сборник тезисов. Пгт. Кацивелли, Крым, Украина. 23-28 сентября 2007 г. С.59-60.

АНОТАЦІЇ

Васильєв С.В. Складність задач та ефективність процедур розпізнавання. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 - теоретичні основи інформатики та кібернетики. - Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, 2008.

У дисертаційній роботі виведено детерміновані нижні і верхні оцінки похибки байєсівської процедури розпізнавання у дискретному випадку для незалежних ознак. Отримані оцінки є поліноміальними від таких вхідних параметрів задачі розпізнавання, як розміри класів навчаючої вибірки, кількості ознак та числа значень ознак. Побудовано і експериментально підтверджено ефективний метод розпізнавання вторинної структури білків на основі байєсівської процедури розпізнавання на моделях ланцюгів Маркова. У якості навчаючої вибірки взята інформація з відкритих баз даних генетики та біології NCBI. Визначено порядок моделі ланцюга Маркова шляхом розв'язання гіпотез із використанням критерію ч². Проведено статистичний аналіз ДНК людини, отримано та підтверджено за допомогою кластерних комп'ютерів нові співвідношення комплементарності у записі основ для моделей ланцюгів Маркова.

Ключові слова: біоінформатика, байєсівська процедура розпізнавання, оцінка похибки процедури, нестаціонарний ланцюг Маркова, вторинна структура білка, статистичний аналіз ДНК.

Васильев С.В. Сложность задач и эффективность процедур распознавания. - Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.01 - теоретические основы информатики и кибернетики. - Институт кибернетики имени В.М. Глушкова НАН Украины, Киев, 2008.

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

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

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

...