Бадалова М.В. Рефлексивная организация этического пространства п. Рефлексивная организация этического пространства психолога
 Скачать 1.31 Mb.
|
|
МАШИННОЕ ОБУЧЕНИЕ И СЖАТИЕ ПРЕЦЕДЕНТНОЙ ИНФОРМАЦИИ Донской Владимир Иосифович Доктор физмат. наук, профессор, Крымский федеральный университет, г. Симферополь АННОТАЦИЯ Целью этой статьи является изучение теоретических вопросов машинного обучения на основе сжатия начальной прецедентной (обучающей) информации. Для достижения этой цели используются методы теории колмогоровской сложности. Даны определения сложности обучающей информации. Показано, как процесс построения гипотезы, основанной на сжатии обучающей информации, обеспечивает возможность эмпирического обобщения и достижения обучаемости. Предложен критерий остановки процесса машинного обучения на основе сжатия. Для реализации указанного критерия необходимо научиться оценивать величину удлинения описания гипотезы на шагах коррекции. В некоторых случаях, например, для решающих деревьев, это сделать сравнительно легко. Для параметрических моделей, в частности, для нейронных сетей фиксированной структуры, можно оценивать усложнение гипотезы увеличивающейся по мере обучения величиной максимального модуля параметров, а при растущей структуре сети – оценкой длины описания добавляемых элементов purpose of this article is studying of theoretical questions of machine learning based on the compression of the initial case (training) information. To achieve this purpose Kolmogorov complexity theory methods are used. Definitions of complexity of the training information are given. It is shown how process of creation of the hypothesis based on compression of the training information provides possibility of empirical generalization and achievement of learning ability. The stopping criterion of process of machine learning on the basis of compression is offered. For realization of the specified criterion it is necessary to learn to estimate the size of lengthening of the description of a hypothesis on correction steps. In some cases, for example, when decision trees are used, to make it rather easily. For parametrical models, in particular, for neural networks of the fixed structure, it is possible to estimate complication of a hypothesis by the size of the maximum module of parameters increasing in process of learning, and at the growing structure of a network – by estimation the length of the description of the added Ключевые слова машинное обучение, колмогоровская сложность, критерий остановки. Keywords: machine learning, Kolmogorov complexity, stopping Введение. Методы машинного обучения на основе сжатия описания начальной прецедентной информации стали привлекать внимание исследователей в области теоретической информатики и разработчиков интеллектуализированного программного обеспечения после появления парадигмы MDL – minimum description length [5]. Эта парадигма основана на принципе бритвы Оккама», согласно которому лучшей гипотезой для объяснения данных является та, которая соответствует наибольшему их сжатию. Под сжатием данных понимается процесс, который приводит к уменьшению объ- ёма данных без потери возможности их использования для получения целевой информации. Теоретической основой и математическим обоснованием построения теории обучения (эмпирической индукции) на основе сжатия явились работы Р. Соломонова и АН. Колмогорова Кроме достаточно строго обоснованных теоретических методов, базирующихся на принципах сжатия обучающей информации, известны эвристические подходы к построению алгоритмов машинного обучения на основе простой структурной закономерности, например, представленные в работе Н. Г. Загоруйко [7], и на поиске кратчайших отделителей тупиковых тестов и их обобщениях – в работах Ю.И. Журавлёва Целью этой статьи является дальнейшее изучение теоретических вопросов машинного обучения на основе сжатия начальной прецедентной (обучающей) информации и применения методов теории колмогоровской сложности. 1. Декомпрессоры и компрессоры Определение 1. [3, с. 221] Колмогоровская сложность словах при заданном способе описания – вычислимой функции (декомпрессоре) D есть { } ( ) ( ) | ( ) D KS x min l p D если существует слово p такое что ( ) D p x = . В противном случае полагается, что значение сложности не ограничено (+∞ ), и говорят, что колмогоровская сложность не определена. Здесь и далее l(x) означает длину слова x Определение 2. Условная колмогоровская сложность слова x при заданном слове y есть { } ( | ) ( ) | ( , ) D KS x y min l p D p y x = = . Если y – пустое слово, то ( | ) ( ) D D KS x y KS Определение 3. Говорят, что декомпрессор D 1 слова x не хуже декомпрессора D 2 , если 1 2 ( ) ( ) O(1) D D KS x KS Декомпрессор называют оптимальным, если он не хуже любого другого декомпрессора. Теорема 1 (Соломонова–Колмогорова) [3]. Существуют оптимальные декомпрессоры. □ 44 Евразийский Союз Ученых (ЕСУ) # 2 (23), 2016 | ФИЗИКО - МАТЕМАТИЧЕСКИЕ НАУКИ Далее запись KS(x) (или KS(x|y)) будет обозначать кол- могоровскую сложность (условную сложность) строки x по некоторому оптимальному декомпрессору. Теорема 2 (Колмогоров. Пусть A – перечислимое множество пари. Тогда ( ) ( ) ( ) | | M | 1 a KS x Теорема 3. [2, с. 75] Колмогоровская сложность конечной строки x как величина { } ( ) ( ) | ( ) D KS x min l p D определена тогда и только тогда, когда существует машина Тьюринга T c (x) (компрессор) такая, что T c (x)=p Определение 4. Пусть x – конечная строка, и множество её компрессоров ( ) ( ) { } T | C C C x T T x p = = не является пустым. Назовем ( ) ( ) ( ) ( ) { } * * T : | C C C T KT x p l p min l p T сжатием строки x наилучшим компрессором. Теорема 4 [2, с. 75]. Словарная функция KT(x) сжатия наилучшим компрессором не является вычислимой. 2. Сжатие обучающей информации. Пусть { } 1 , m j j j x α = – обучающая начальная прецедентная информация, где ( ) 1 ,..., j j j n x x x = – векторы-описания объектов, j α – номер класса объекта j x , принимающий для упрощения в рамках этой статьи) только два значения 0 и 1. Пусть каждая координата любого вектора j x использует ровно 1 бит памяти j α использует 1 бит памяти. Тогда длина обучающей информации составляет ( ) 1 m Mn + бит, из которых mMn – затрачивается на описания объектов, а m бит – на вектор ( ) 1 ,..., ,..., j m α α α α = . Следовательно, обучающую информацию можно представить двоичной строкой ( ) 1 m указанной длины. Обозначим ( ) ( ) 1 T T C C m M X + = – множество всевозможных компрессоров выборки. Пусть P – такая строка, что существует машина Тьюрин- га , которая для любого вектора j x , используя эту строку P, правильно вычисляет значение j α : ( ) , j j T P X α = Такая строка ( ) ( ) 1 m M P P X + = называется сжатием обучающей выборки. По строке P , вообще говоря, может оказаться невозможным вычислить (восстановить) обучающую выборку, представленную строкой ( ) 1 m M X + , однако можно вычислить частичную функцию, ставящую в соответствие любому описанию произвольного примера j x из обучающей информации { } 1 , m j j j x α = значение Определение 5. Колмогоровская сложность обучающей информации, представленной строкой ( ) 1 m M X + , относительно декомпрессора D есть ( ) ( ) ( ) ( ) ( ) ( ) { } 1 1 | , D j j j m M m M K X min l P x X D P x α + + = ∀ если существует хотя бы одно слово P , удовлетворяющее указанному условию. В противном случае полагается, что значение сложности не ограничено (+∞). Определение 6. Пусть ( ) 1 m M X + – строка, представляющая обучающую выборку, и множество её компрессоров ( ) ( ) 1 T : T C C m M X P + = не является пустым. Назовем величину сжатием обучающей выборки наилучшим компрессором. □ Подчеркнём, что сжатие P * заведомо гарантирует существование декомпрессора – машины Тьюринга D такой, что M x X D P x α + ∀ Если обучающая выборка не является случайной (в таком случае, согласно теории Колмогорова, она содержит закономерности, то должно выполняться неравенство ( ) ( ) * 1 l P m Mn < + . В тоже время по слову P * можно вычислить значение j α для любого вектора j x . Следовательно, слово P * содержит неполное признаковое описание объектов, а сокращенное. Если j x ω – сокращённое описание объекта j x , то это сокращённое описание подходит сразу для множества объектов, порождая таким образом обобщение на некоторое множество ( ) j G x объектов, элементы которого будут классифицироваться точно так, как объект j x . Этим объясняется способность сжатия к построению решающих правил, обеспечивающих обучаемость [2]. В общем случае словарная функция ( ) ( ) C 1 m M KT X + не является вычислимой, поэтому поиск компрессора, близкого к наилучшему, осуществляется эвристическими методами. Причём стем большим успехом, чем меньшей оказывается длина слова (сжатия, полученного выбранным компрессором. Это слово, как и оптимальное сжатие, далее также будем обозначать Критерий остановки обучения на основе сжатия. Принцип MDL гласит наилучшая гипотеза для данного набора данных та, которая минимизирует сумму длины описания кода гипотезы (также называемой моделью) и длины описания множества данных относительно этой гипотезы. В рассматриваемой постановке слово P * является кодом гипотезы (будем также говорить – гипотезой P * ), а длина части неправильно классифицируемых гипотезой P * объектов обучающей выборки является второй частью суммы, опре- делённой принципом MDL. Иначе говоря, сложность обучающей выборки относительно гипотезы P * определяется частью выборки, не объясняемой этой гипотезой Евразийский Союз Ученых (ЕСУ) # 2 (23), 2016 | ФИЗИКО - МАТЕМАТИЧЕСКИЕ НАУКИ Если m – число примеров в обучающей выборке, а величину принять в качестве длины её описания, то сложность одного необъяснённого примера составит 1 Mn + . Процесс обучения характеризуется поэтапным усложнением гипотезы, которая классифицирует объекты выборки, по мере необходимости исправлять неправильную классификацию некоторых примеров. Поэтому сложность синтезируемой таким образом гипотезы растет ( ) ( ) ( ) 1 2 t l P l P l P < < < , где 1,2,...,t – шаги коррекции. При этом число ошибочно классифицированных примеров выборки убывает ( ) ( ) ( ) 1 2 t Er P Er P Er P > > Критерий остановки процесса обучения определяется значениями суммы ) ( ) t t l P Er P g + и определяется шагом ( ) ( ) opt t t t t agmin l P Er P g = + , где величина γ может быть, например, взята равной 1 Mn + . Заметим, что минимум этой суммы может достигаться при нулевом количестве ошибок классификации обучающей выборки, что будет говорить об удачном выборе семейства, из которого извлекается гипотеза. Для реализации указанного критерия необходимо научиться оценивать величину удлинения описания гипотезы на шагах коррекции. В некоторых случаях, например, для решающих деревьев, это сделать сравнительно легко. Для параметрических моделей, в частности, для нейронных сетей фиксированной структуры, можно оценивать усложнение гипотезы увеличивающейся величиной максимального модуля параметров, а при растущей структуре сети – оценкой длины описания добавляемых элементов. Список литературы 1. Дмитриев АН, Журавлев Ю.И., Кренделев Ф.П. Ома- тематических принципах классификации предметов и явлений Дискретный анализ. Новосибирск ИМ СО АН СССР. 1966. Вып. 7. С. 3 – 11. 2. Донской В.И. Алгоритмические модели обучения классификации обоснование, сравнение, выбор. Симферополь ДИАЙПИ, 2014. 228 с. Колмогоров АН. Теория информации и теория алгоритмов. М Наука, 1987. 304 с. Колмогоров АН. Три подхода к определению понятия количество информации // Проблемы передачи информации. С. 3–11. 5. Rissanen, J. Modeling by shortest data description // Automatica. 1978. 14 (5). P. 465–658. 6. Solomonoff R. J. A Formal Theory of Inductive Inference. Part I // Information and Control. 1964. 7 (1). P. 1–22. 7. Zagoruiko N.G., Samochvalov K.F. Hypotheses of the Simplicity in the Pattern Recognition: Proc. of Second Int. Joint Conf. on Artificial Intelligence. London: William Kaufmann, 1971. P. 318-321 46 Евразийский Союз Ученых (ЕСУ) # 2 (23), 2016 | ФИЗИКО - МАТЕМАТИЧЕСКИЕ НАУКИ ДВА КЛАССА ЧАСТНЫХ РЕШЕНИЙ УРАВНЕНИЯ ВЛАГОПЕРЕНОСА Урманбетов Рысбек Джолдошевич кандидат физико-математических наук, доцент кафедры Высшей и прикладной математики Кыргызского Национального Аграрного Университета имени К.И. Скрябина, город Бишкек (Кыргызстан) Дыйканова Айнура Тынчыбековна кандидат физико-математических наук, доцент кафедры Высшей и прикладной математики Кыргызского Национального Аграрного Университета имени К.И. Скрябина, город Бишкек (Кыргызстан) TWO CLASSES OF PARTICULAR SOLUTION MOISTURE Urmanbetov Rysbek Djoldoshevich candidate of physico-matematicheskih Sciences, associate Professor of Kyrgyz National Agrarian University named after KI Scriabin, Bishkek (Kyrgyzstan) Dyikanova Ainura Tynchybekovna candidate of physico-matematicheskih Sciences, associate Professor of Kyrgyz National Agrarian University named after KI Scriabin, Bishkek (Kyrgyzstan) АННОТАЦИЯ Исследование нелинейного одномерного уравнения влагопереноса проведено численными, приближенно - аналитическими и аналитическими методами. Задачей является нахождение аналитических решений, определение распространения влаги в почвогрунте, с выявлением фронта смачивания и границы зон of nonlinear one-dimensional equation of moisture transfer numerical, approximate - analytical and analytical methods. The objective is to find analytical solutions, defining the spread of moisture in soils, the identification of the wetting front and the border Ключевые слова:влагоперенос; почва почвогрунт; гипергеометрическая функция moisture transfer; soil; soils; hypergeometric Известно, что движение влажности вглубь почвы происходит под действием самых разнообразных движущих сил, те. впитывание есть процесс поступление воды с поверхности почвы в ненасыщенную среду, причем она имеет неустановившийся характер. Наиболее полный характер исследования по одномерной инфильтрации имеется в классической работе Дж.Филиппа [1], в которой дается детальный анализ процесса горизонтального впитывания водно- родный грунт, доказано существование решения уравнения влагопереноса с учетом капиллярных, сил с коэффициентами зависящими от влажности. Исследование нелинейного одномерного уравнения вла- гопереноса проведено численными, приближенно - аналитическими и аналитическими методами. Нахождение аналитических решений, определение распространения влаги в почвогрунте, с выявлением фронта смачивания и границы зон раздела полного и неполного насыщения, является важной задачей. Нами предлагаются простые оригинальные аналитические методы решения математических моделей движения влаги в почвах для одномерного потока. Нелинейное уравнение влагопереноса без учета гравитационных сил для одномерного случае записывается в виде ∂ ∂ ∂ ∂ = ∂ ∂ x W D(W) x t W (1) Для этого уравнения сформулируем следующую началь- но - краевую задачу при ..., x A x A A 0) W(x, 0 t 0, õ 2 2 1 при ..., t B t B B 0) W(x, 0 t 0, õ 2 2 1 при 0 t) , W( 0 Уравнения (1) с начально - краевыми условиями (2-4) описывает процесс впитывания влаги в почву, когда на поверхности поддерживается некоторой напор воды те. имеется избыток жидкости на поверхности почвы с неизвестной границей фронта увлажнения. Так как уравнение (1) является нелинейным, то аппроксимируя коэффициент D(W) степенным рядом [1] , W D W D D D(W) 2 2 1 0 + + + = (5) а само решение задачи искать в виде ..., W å åW W W 2 2 1 0 + + + = (6) то относительно основного нулевого приближения имеем уже линейное уравнения 0xx 0 0t W D W Для него предложим решение в виде W 0 (x,t)=f 0 (t)∙f 1 (ξ) , ξ=ax 2 /t (8) Определяя частные производные ξ x =2ax/t, ξ t =-ax 2 /t 2 , W ot =f 0 f 1 -ξf 0 f 1 /t, W ox =f 0 f 1 2ax/t, W oxx =f 0 2a/ t(2ξf 1 ’’+f 1 ’’ ) и подставляя в уравнение (7), получим Евразийский Союз Ученых (ЕСУ) # 2 (23), 2016 | ФИЗИКО - МАТЕМАТИЧЕСКИЕ НАУКИ 47 ξf 1 ’’ +[1/2+ξ/4aD 0 ]f 1 ’ -в/4aD 0 -f 1 =0(9) вырожденное гипергеометрическое уравнение Гаусса, решение которого имеет вид ( ) ) î ; 2 3 , 2 1 k F( î A ) î ; 2 1 k, F( A î f 2 3 2 1 1 + − + − = (10) где - функция Похгамме- ра или вырожденная гипергеометрическая функция, представленная с помощью ряда. Другое частное решение уравнения (9) имеет вид ( ) ƒÌ exp ƒÌ f 1 = (11) те. решением уравнения (7) будет − = t 4D x exp t A t) (x, W 0 2 0 (12) Далее усложним решение (8), те. [ ] , ƒÌ à â ) ƒÌ ( f (t) f t) (x, W 1 Здесь, также определяя и подставляя в исследуемое уравнение, имеем при 0 4D 1 p − = и Это уравнение также имеет одно из частных решений при этом имеем систему алгебраических уравнений, из которых находим k=-3/2 , в , поэтому Полученное решение, также является точным решением уравнения (7). Если же решение (7) есть то, определяя частные производные и подставляя в рассматриваемое уравнение, после несложных выкладок имеем при этом предположили, что ft 0 0 = ′ а при p=- 1/4D 0 имеем Это уравнение имеет одночастное решение f 1 (ξ) =expξ, а коэффициенты определяются из системы алгебраических уравнений, причем k=-5/2 , a - произвольная величина, b=4a, c=4a/3 Таким образом, еще одним точным решением уравнения (7) будет Аналогично, можно найти еще одно решение методом индукции Если продолжить этот процесс, то можно записать целый класс частных решений в виде где f 0 (t)=At -k-1/2 , f 1 (ξ)=exp(-x 2 /4D 0 t) a 1, a 2 ,...,a n - определяются из подстановки (22) в исследуемое уравнение (Второй класс частных решений предлагаем находить в форме Вначале, определим частные производные А затем подставляя в уравнение (7), после некоторых математических преобразований, имеем В полученном уравнении разделение переменных не произошло. Но если взять f 2 (ξ)=x, f 0 (t)=t k , то оно записывается в форме вырожденного гипергеометрического уравнения а его два решения, имеют вид Уравнение (25) имеет также одно экспоненциальное решение, при k=-3/2 . Таким образом, одним из важных решений уравнения (7) будет Полученное решение можно усложнить, если искать решение исследуемого уравнения (7) в виде 48 Евразийский Союз Ученых (ЕСУ) # 2 (23), 2016 | ФИЗИКО - МАТЕМАТИЧЕСКИЕ НАУКИ Определяя частные производные и подставляя в уравнение (7), при p=-1/4D 0 , f 0 (t)=t k , имеем Отсюда, с учетом (2.7.28) имеем еще одно точное решение при k=-5/2 ,a - произвол, в , Полученное решение (30) подталкивает на мысль, что последнее произведение можно представить в виде полинома, например второй и.т.д. степени. Пусть решение (7) имеет форму Здесь, также определяя искомые частные производные и подставляя в (7), после несложных математических выкладок, имеем Последнее уравнение имеет одночастное решение в виде Мы заметили, что следующим решением для уравнения (7) будет Таким образом, уравнение (7) имеет еще один класс частных решений, общий вид которого записывается как где f 0 (t)=At -k-1/2 , f 1 (ξ)=exp(-x 2 /4D 0 t) в, в 2 ,...,в n - определяются подстановкой (34) в исследуемое уравнение (7). Итак, нами найдены два класса точных аналитических решений уравнения (7). Зная, что полученные два класса решения удовлетворяют определенным функциональным преобразованиям [2], можно получить другие классы новых решений, а постоянные интегрирования определятся изначально- краевых условий (2- 4). Список литературы 1. Филипп Дж.Р.Теория инфильтрации « Изотермические передвижение влаги в зоне аэрации.-Л.: Гидрометео- издат.1972.-168 с. 2. Нерпин СВ, Чудновский А.Ф. Физика почвы. М, Наука, с Евразийский Союз Ученых (ЕСУ) # 2 (23), 2016 | ФИЗИКО - МАТЕМАТИЧЕСКИЕ НАУКИ ГЕОМЕТРИЧЕСКАЯ МОДЕЛЬ ГРАВИТАЦИИ И |