Выбор субоптимальных методов для решения сложных технических задач. Феномен ДНК крупский Максим Андреевич цо №1840, 10 класс г. Москва



Скачать 42.39 Kb.
Дата04.05.2016
Размер42.39 Kb.

Выбор субоптимальных методов для решения сложных технических задач. Феномен ДНК

Крупский Максим Андреевич ЦО №1840, 10 класс г. Москва


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

В основе процедур распознавания лежит формула Байеса.

Известно, что индуктивный подход – основа изучения объектов в естественных науках. Однако в математике он широко не используется, поскольку до настоящего времени не имел убедительного обоснования. Ключевым моментом обоснования процедур распознавания или индуктивного вывода является наличие всех классов в выборке и усреднение погрешности по множеству обучающих выборок. Поэтому попытки оценить процедуры индуктивного вывода без учёта таких вопросов не приводили к положительному результату. Основной принцип дедуктивной математики – строгое доказательство и получение точного решения. Работа в процессе дедуктивного вывода ведётся только на одном классе истинных утверждений, ложные утверждения не используются. Дедуктивные правила вывода имеют высокую сложность и низкую эффективность. Продолжая перечень ограничений, отнесли к ним неполноту асимптотических систем, которая вытекает из знаменитой теоремы Геделя.

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

В 70-е годы прошлого века была построена теория сложности переборных и комбинаторных задач. Выясняется, что многие известные задачи принадлежат к труднорешаемым. Для того, чтобы справится с такими сложными задачами учёные стали развивать другие схемы организации вычислений, которые кардинально отличаются от традиционных: квантовые, ДНК и нейро-компьютеры. По оценкам специалистов для их изготовления потребуется развитие новых технологий. Эта работа может потребовать значительного времени.

Понятия условной вероятности, а также независимости событий, занимают центральное место в теории вероятности. Условная вероятность каждой гипотезы Ai при наступлении события В определяется формулой:


P(A)P(B/A)

P(A/B)=

P(B)
Эта формула установлена одним из основателей теории вероятностей английским математиком Томасом Байесом(ум. в 1763г.) и носит его имя. Событие В состоит в том, что измерения объекта принимают конкретные значения X1,X2,…,Xn . Событие A1 определяется тем, что характеристика f принимает значение f = 0, а событие A2 – f = 1. Распределение вероятностей удовлетворяет условию:


P(X1,X2,…,Xn f = i) = ∏nj =1P(Xj f = i),i=0, 1.
Этот факт означает независимость признаков Xj для каждого класса объектов; здесь

P(Xj f = i) – условная вероятность. Заметим, что, по крайней мере, для медицинской экспертной системы такое условие выполняется. Тогда формула Байеса связывает указанные условные вероятности зависимостью:




nj =1P(Xj f = i)P(f = i)




P(f = i X1,X2,…,Xn)= , i = 0, 1. (1)

P(B)
Вероятность P(B) не влияет на работу процедуры, поэтому её можно не учитывать. Сама же Байесовская процедура распознавания, обучения QB (или индуктивного вывода) строится на основе того, что каждая из вероятностей P( Xj f = i) и P( f = i) приближённо заменяются частотой появлений признаков Xi , i=1,2 … n, f в обучающей выборке. Из формулы (1) видно, что вычисления проводятся одновременно по всем столбцам обучающей выборки. В байесовской процедуре QB характеристика f принимает значения того класса, для которого оценка условной вероятности P( f = i X1,X2,…,Xn ) в формуле (1) больше, чем у другого. Тогда точная оценка погрешности байесовской процедуры распознавания, которая в булевом случае имеет очень простой вид:



a n+1 (2)

m

где a >0 – константа, n – число измерений объекта, m = min(m0,m1) – размер наименьшего класса в обучающей выборке. Отсюда непосредственно вытекает, что погрешность стремится к нулю с ростом обучающей выборки, т.е. достоверность байесовской процедуры распознавания возрастает вместе с увеличением размеров всех классов обучающей выборки. Данный результат подтверждает обоснование процедур индуктивного вывода. Формулу Байеса называют еще принципом обратной вероятности, или концепцией индуктивной вероятности. Таким образом, можно сказать, что большая часть результатов в теории вероятностей - логическое следствие формулы Байеса и принципа независимости событий. Поэтому нет ничего удивительного в том, что процедура распознавания, построенная на основе формулы Байеса, оказалась оптимальной.



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

Вывод: Таким образом, Байесовская процедура распознавания является универсальной перерабатывающей поступающую информацию оптимальным образом.



Одним из направлений применения указанных процедур распознавания может быть феномен ДНК.

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


База данных защищена авторским правом ©bezogr.ru 2016
обратиться к администрации

    Главная страница