страница1/7
Дата03.05.2018
Размер1.6 Mb.
ТипРеферат

Матема́тика — наука, изучающая количественные и пространственные соотношения, в действительном мире и человеческом воображении


  1   2   3   4   5   6   7


ВШЭ-ГУ

2010
Борис Григорьевич Миркин

Профессор

Кафедра анализа данных и искусственного интеллекта ГУ-ВШЭ Москва РФ

Department of Computer Science and Information Systems Birkbeck University of London UK

История и методология прикладной математики и информатики
Содержание:
1. Введение: чистая и прикладная математика; информатика . . . . . . . 2

2. Наследие античности: вклады Пифагора, Аристотеля и Архимеда. . . . 5

3. Развитие идей небесной механики . . . . . . . . . . . . . . . . . . . . . . 14

4. Развитие идей оптимизации. . . . . . . . . . . . . . . . . . . . . . . . . . 19

5. Развитие идей вероятности и статистики. . . . . . . . . . . . . . . . . . . 21

6. Развитие идей анализа данных . . . . . . . . . . . . . . . . . . . . . . . . 25

7. Развитие идей дискретной математики и графов . . . . . . . . . . . . . . 28

8. Развитие вычислительной техники и программирования . . . . . . . . 32

9. Развитие баз данных и знаний . . . . . . . . . . . . . . . . . . . . . . . . . 36

10. Работы по машинному интеллекту . . . . . . . . . . . . . . . . . . . . . 43

11. Перспективы дальнейшего развития . . . . . . . . . . . . . . . . . . . . 45

Курс отражает мои наблюдения и размышления за годы моей относительно успешной (5 монографий за период 1974-85) и в то же время не совсем удачной (4 докторские диссертации в 1974-1988) научной карьеры в СССР и работы за границей: Франция (1991-93), США (1993-98), Германия (1996-99) и Великобритания (2000-н.вр.). Степень подробности освещения разделов определяется двумя факторами: знакомством студента с материалами других дисциплин учебного плана, а также наличием у меня возможности для их описания.




  1. Математика, чистая и прикладная математика и информатика

Математика – это то, чем занимаются математики. За 2500 лет своего существования понятие о математике видоизменялось и обогащалось. Первоначально – это была абсолютно прикладная дисциплина, связанная с вычислениями (типа астрономических событий или разливами Нила) – в древнем Египте, и землемерием – в древнем Вавилоне, прежде всего с вычислением (они даже изобрели позиционную систему счисления и решали квадратные уравнения); в Египте – прежде всего с землемерием (по закону каждой семье выделялся одинаковый надел, и для поддержания справедливости надо было уметь перераспределять землю при нарушениях баланса, связанных с природными или семейными катаклизмами). Любопытно, что эти знания никак не обменивались, и идеи позиционного счисления вошли в Европейскую науку спустя многие сотни лет через арабскую математику.

Греки внесли в математику идею логического доказательства. Евклид описал планиметрию с помощью аксиоматического метода (аксиомы – логика – теоремы), который в настоящее время понимается многими как главная особенность математики в системе наук. Они же установили, что одни и те же соотношения могут описывать совершенно разные явления (созвучия как пропорции). Такие задачи как решение уравнений, вычисление объемов и описание движения вызвали к жизни появление развитых математических конструкций – вещественные и комплексные числа, функции и дифференциальное исчисление, теория оптимизации, дифференциальная геометрия, дифференциальные уравнения и пр. Это дало основание рассматривать математику как науку об описание количественных и пространственных форм окружающего нас мира.

Из русской Википедии

Матема́тиканаука, изучающая количественные и пространственные соотношения, в действительном мире и человеческом воображении. Существуют совершенно иные и весьма разнообразные трактовки предмета математики и её метода, например, некоторые придерживаются мнения, что математика — это наука о следствиях из непротиворечивых наборов аксиом

Математика изучает воображаемые, идеальные объекты и соотношения между ними, используя формальный язык. Математические понятия и теоремы не обязательно имеют соответствия чему-либо в физическом мире. Однако некоторые из исследуемых математикой объектов могут иметь прообразы в реальном мире, более или менее похожие на свои математические модели. Модель объекта учитывает не все его черты, а только самые необходимые для целей изучения. Например, изучая физические свойства апельсина, мы можем абстрагироваться от его цвета и вкуса и представить его шаром. Если же нам надо понять, сколько апельсинов получится, если мы сложим вместе два и три, — то можно абстрагироваться и от формы, оставив у модели только одну характеристику — количество. Абстракция и установление связей между объектами в самом общем виде — цель, к которой стремится математика. Наряду с моделированием математика прибегает к обобщениям, например, обобщая понятие «пространство» до пространства n-измерений.

Изучение объектов в математике происходит при помощи аксиоматического метода: сначала для исследуемых объектов формулируется список аксиом и вводятся необходимые определения, а затем из аксиом с помощью правил вывода получают теоремы.

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


Язы́к — система звуков, знаков, предназначенная для фиксации, переработки и передачи сведений от одного субъекта к другому.
Следует подчеркнуть, что «фиксация» в этом определении - это очень нетривиальный этап, связанный с выделением и пониманием существенных свойств явления.

Функции языка (релевантные выделены крупным шрифтом)


  • коммуникативная (или функция общения) — основная функция языка, использование языка для передачи информации;

  • когнитивная (или познавательная функция) — формирование мышления индивида и общества;

  • информативная (или аккумулятивная функция) — передача информации и её хранение;

  • эмотивная (или эмоциональная функция) — выражение чувств, эмоций;

  • волюнтативная (или призывно-побудительная функция) — функция воздействия;

  • метаязыковая — разъяснения самого языка средствами языка;

  • фатическая (или контактноустанавливающая);

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

  • омадативная (или формирующая реальности) - создание реальностей и их контроль

Рассмотрим, как пример, теорию алгебраических квадратичных уравнений, создававшуюся более тысячелетия (от Пифагора, который обнаружил наличие нерациональных корней до Гаусса, который доказал основную теорему математики).
Две, по моему мнению, основные задачи этой теории –
(а) вычисление корней (известная формула x= = p/2sqrt(p2/4-q))
(б) установление связи между двумя языками их описания, внешним – коэффициентов, и внутренним – свойствами корней. Точнее, речь идет об утверждениях, связывающих свойства параметров описания уравнений (p,q) со свойствами корней, вещей ненаблюдаемых. Пример такого утверждения: для того, чтобы оба корня были вещественными необходимо и достаточно, чтобы p2/4-q>0. (Какой красивый и нетривиальный признак, p2/4-q, сформирован из исходных двух признаков - коэффициентов p и q!)
Мне могут возразить, что данная характеристика очевидно вытекает из вышеприведенной формулы – и я скажу, конечно, в данном случае это так. Но имеется значительно больше случаев более сложных уравнений – а всякая инженерная задача в той или иной мере сводится к решению уравнения – когда никакого аналитического решения указать нельзя;

тогда то утверждения о свойствах корней уравнений становятся главным инструментом анализа.


Почему я считаю, что языковый аспект, т.е. прежде всего, так называемые необходимые и/или достаточные условия, так важен? Математика разрастается, как финансовые инструменты. Три основных раздела математики – геометрия, алгебра и анализ – разрастаются, абстрагируются, взаимно проникают друг в друга. Вспомните, какие современные средства алгебры и геометрии понадобились для недавнего решения такой очень просто формулируемой проблемы как так называемая большая теорема Ферма.
Чем больше взаимопроникновение, тем больше понимание, тем больший круг явлений реального мира охватывается, а математизация новых явлений приводит к жизни новые конструкции, свойства которых надо изучать – для того, чтобы иметь возможность решать новые задачи. Считается, что изучение свойств уже определенных математических объектов может потребовать не одной сотни лет.
Вычислительная тематика все более передается прикладной математике и информатике, а языковая, связь между абстрактными математическими конструкциями, как гомотопии и соответствующие алгебры, все более углубляется и расширяется. В связи с этим, кстати, меняется понятие «нетривиальности» или «силы» математического результата. Раньше степень нетривиальности ассоциировалась со сложностью, т.е. длиной, доказательства, теперь, по-моему, с «расстоянием» между языками, между которыми устанавливается соответствие.
Чистая математика работает на математику, изучая свойства математических объектов. Прикладная математика ориентирована на приложения вне математики, в других областях науки, технике, экономике и пр. Информатика – реализация математических построений на компьютере; включает существенную инженерную компоненту типа разработки хардвера, поддержки безопасности, формирования протоколов электронных сообщений и пр.

Не существует границы между прикладной и чистой математикой по предмету – граница проходит по области применения: внутри математики (чистая) или в другой области науки или практики (прикладная).


Пример, поясняющий эту мысль:
Малая теорема Ферма (1601-1665, Тулуза). Рассмотрим два взаимно простых натуральных числа (без общих нетривиальных делителей) a и n. Обозначим (n) количество натуральных чисел от 1 до n, являющихся взаимно простыми с n. Например, если n – простое, т.е. делится без остатка только на себя и на 1, то (n)=n-1. Теорема утверждает, что число a(n) 1 делится на n без остатка.

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


.


2. Наследие античности: вклад Пифагора, Аристотеля, Архимеда
2.1. Пифагор (предположительно 580-500 до р.Х., Самос, потом Кротон в Италии, место смерти неизвестно)
(а) «Все есть число». И действительно, Пифагору удалось установить связь между такими вещами как:

– Арифметика: Пифагорейские числа; тетрада (квадратные числа – выкладывание и счет камешков, отсутствие нуля)

– Музыка: Консонантные созвучия как простые отношения 1:2, 1:3 и т.д., между длинами струн (точнее, частотой звука, о чем Пифагор не знал)

– Геометрия: Теорема Пифагора и правильные («Платоновские») многогранники

– Астрономия: Расположение планет вокруг общего центра, не солнца!, а «анти-Земли» с диаметрами, отражающими те же числовые соотношения (Понятия о «Музыке сфер», термин «космос» – порядок)

– Философия: Риторика

Эти пять лежат в основе классического образования до сих пор.

С тех пор идея о том, что математическая красота сама может являться критерием истины, неоднократно подтверждалась. Один из популярных примеров – когда П. Дирак описал движение электрона (отрицательный заряд) так, что решение уравнения оказалось двойным, вместе с отрицательным корнем обнаружился равновеликий положительный, Дирак объявил о необходимости существования «позитрона», который и был действительно открыт вскоре как физический объект.


(б) Идея математического (= логического) доказательства. Перевод математики из полуэмпирической дисциплины в разряд теоретической (т. е. устроенной как система вывода: аксиомы – правила вывода – теоремы), программа блестяще реализованная «Началами» Эвклида, сочинением, посвященным построению геометрии плоскости, включая доказательство существования ровно пяти правильных многогранников.
(в) Теорема Пифагора (сумма квадратов катетов равна квадрату гипотенузы) – Открытие иррациональных чисел (длина диагонали квадрата со стороной единица – sqrt(2) не может быть представлена в виде отношения натуральных чисел, так как это приводит к противоречию) – Первый кризис математики: вместо естественной для нас идеи о том, что для выхода из кризиса надо пополнить множество чисел – включить туда иррациональные числа, Пифагор преодолел проблему, переведя всю арифметику на язык геометрии, так что число стало соответствовать длине интервала, сложение чисел – соединению интервалов, умножение чисел – вычислению площади соответствующего прямоугольника и т.п. Наряду с некоторыми положительными моментами (очевидность коммутативности и ассоциативности, общая наглядность) – колоссальные недостатки: например, невозможность оперировать более, чем с двумя числами одновременно, невозможность позиционной системы счисления, отсутствие алгебраической нотации, в целом задержавшие развитие математики на 2000 лет!
(г) Золотое сечение: с пропорцией x=(1-x)/x, x=(-15)/2 – числа Фибоначчи. В основе пентаграммы – правильной пятиконечной звезды.
2.2. Вклад Аристотеля
Аристотель (384-322 до р.Х., Стагира-Афины-..?) – ученик Платона (, который стал сам учить других учеников, за что был изгнан Платоном из здания, подаренного ему Академом, и продолжал учить, прогуливаясь по саду (перипатетики); позднее был приглашен царем Македонии Филиппом в наставники своему сыну Александру, который очень уважал Аристотеля (и философию вообще – сохранился рассказ о его посещении Диогена, который учил, что человек должен жить естественно, как собаки (кинизм), и сам жил в большой винной амфоре – «Диоген, могу ли я что-нибудь для тебя сделать,» - «Да, конечно: отойди, ты загораживаешь свет.» - «Я бы хотел быть Диогеном, если бы не был Александром!») и даже брал его с собой в походы. )
Он оформил античную науку; его утверждения, даже и неверные, признавались до 16-17 веков. Можно сказать, что современная наука первоначально развивалась путем эвристической проверки и опровержения Аристотелевских принципов. Для нас интересны три аристотелевских понятия.
(а) Причинность по Аристотелю:

Четыре вида:

- материальная: часть-целое,

- формальная: целое-часть,

- эффективная-современное понимание,

- целевая (конечная) - не «почему», а «зачем», включая психологическую мотивацию.


Понимал циркулярность причинных сетей.

Исследование причин – одна из основных доминант познания. Когда найдена причина, возникает теория, описывающая механизм рассматриваемого явления и процесса. Отметим, что каждая найденная причина (механизм) открывает новый, объемлющий, сценарий с тем же самым вопросом «почему».


(б) Логика – силлогизмы Аристотеля (силлогизм: предложение о связи А и В, вытекающее из двух посылок, о связи А и Б, и о связи Б и В).
Предложения бывают 4 типов: утвердительное - отрицательное, универсальное -частное (кванторы всеобщности и существования).
«Все люди смертны. Кай – человек. Значит, Кай смертен.»
Имеются три понятия, А Б и В.
Посылки дают утверждения о связи А с Б (Большая посылка) – 4 вида ут/от – ун/ча, связи Б с В (Малая посылка), тоже 4 вида, а вывод – о связи А с В, тоже 4 вида – итого 64. Поскольку каждая связь может иметь одну из 2 фигур (А есть Б или Б есть А), то всего 256 возможных силлогизмов.
Из них только 24 правильных. Например, «Если некоторые А есть Б, а некоторые Б – В, то все А являются В» - чепуха, а вот «Если все А есть Б, а все Б – В, то все А являются В» - хорош. Но и часть правильных – не нужна, поскольку они выражают частные случаи других силлогизмов.. Например, «Если все А есть Б, а все Б – В, то некоторые А являются В» - верно, но верно и значительно более сильное заключение, что «все (а, значит, и некоторые) А являются В».
Два пути современного развития этих принципов, которые можно выразить в терминах интенсиональный – экстенсиональный. Что это такое?

Любое понятие можно трактовать двояко. С одной стороны, это термин, включённый в какую-то область знаний (), обычно даже определяемый в терминах этой области знаний. С другой стороны, понятию соответствуют конкретные объекты, подпадающие под него. Например, «компьютер» может быть определён как цифровое устройство для определенных действий с числами, а с другой стороны, может быть представлен множеством всех вычислительных устройств, произведённых такими-то компаниями и находящихся в пользовании в офисах и квартирах. Первый, «определительный», «теоретический», аспект называется интенсиональным, второй, «перечислительный», «эмпирический», аспект, – экстенсиональным.



Математическая логика пошла по интенсиональному пути через идею выводимости. В математике идея, что все можно вывести из нескольких точно сформулированных понятий, удовлетворяющих четким аксиомам, была очень убедительно доведена до совершенства в так называемой «программе Гильберта» (Д. Гильберт 1862=1943 Германия, последний великий математик), попытке свести математику к математической формальной логической машине. Оказалось, что путь этот приводит к гносеологическим трудностям. Австрийский математик Курт Гёдель доказал, что если такая формальная система включает арифметику (т.е. целые числа и арифметические операции с ними), то существует истинное высказывание, не выводимое из аксиом. Можно сказать – ну и что, давайте добавим это высказывание к списку аксиом, и все будет в порядке. Увы – нет, ведь теорема Геделя применима и к новой, расширенной системе: найдется другое не выводимое высказывание. Интенсиональный путь заведомо не полон, никакая формальная система не сможет вывести все правильные утверждения.
В этой связи поражает, что исследования по искусственному интеллекту вначале в основном шли по интенсиональному пути – грубо говоря, сводились к автоматизации логического вывода – долго, пожалуй до начала 90х, когда ведущие деятели просто сошли со сцены, не оставив никаких сколь-нибудь интересных результатов, разве что концепцию экспертной системы и язык ПРОЛОГ, предназначенный для реализации формальных построений. В этой связи припоминаю, что в 1974 в Тбилиси была организована – чуть ли не впервые в СССР – Международная конференция по Искусственному интеллекту. Меня включили в список рассылки, чем я был очень доволен, и мы послали туда новый метод обобщения данных – агрегирование больших графов в малые, что я считал – и считаю – безусловно относящимся к искусственному интеллекту: по-моему, обобщение фактов или структур – одна из главных интеллектуальных операций. Увы, Оргкомитет так не считал, нашу рукопись мне вернули; на манускрипте округлым девичьим почерком был выведен вердикт: «Никакого отношения к искусственному интеллекту».
Экстенсиональный путь усиленно развивается в настоящее время. Дисциплина «Разработка данных» (Data mining and knowledge discovery) – деятельность по выявлению «интересных» образов или закономерностей в наблюденных данных – фундаментальная часть усилий по искусственному интеллекту – лучше отсчитывать с 90х, хотя, конечно, разрозненные усилия предпринимались с 60х. Согласно этому подходу, каждое понятие представляется неким предикатом, определенным в терминах признаков наблюденных данных и тем самым может соответствовать тому подмножеству множества обрабатываемых данных, на котором оно истинно. Это позволяет перевести логические операции на язык операций над множествами.
Логическое отношение следования соответствует теоретико-множественному включению (Рис. 1).
Рис. 1: Иллюстрация некоторых логических отношений в терминах подмножеств.


Понятие ассоциации, одно из основных в разработке данных, соответствует «интересной» продукции АБ: как (а) множество О(А) достаточно велико, так и (б) множество О(АБ)=О(А)  О(Б) достаточно велико, т.е. составляет значительную долю от О(А). Вычислительно эти свойства обеспечиваются пороговыми значениями, например, чтобы О(А) составляло не менее 30% от всей выборки (условие (а)), а О(АБ) – не менее 90% от объема О(А) (условие (б)). Условие (б) обеспечивает факт импликации (логического следования), а условие (а) – ее интересности, с точностью до заранее фиксированных пороговых значений. Будучи применен к анализу данных о транзакциях (индивидуальных покупках) в цепи американских супермагазинов «Хоум Депо (Всё для дома)» в середине 90х, перебор всех «интересных» продукций привел к успеху – одна из существенных глав в любом учебнике по разработке данных (дата майнинг).

Проблемы –

(аа) определение пороговых значений для экспликации двух «достаточно больших величин и

(бб) слишком много «интересных» импликаций, зачастую значительно больше по объёму, чем исходные данные.


Вероятно, поэтому задача получения нетривиальных силлогизмов не очень пока рассматри-вается в анализе данных, кроме, пожалуй, российского исследователя Чеснокова С.В. , который, впрочем, тоже занят в основном импликациями (Детерминационный анализ), да и далек от основных научных сообществ.
Я вижу ещё одну проблему с силлогистикой:

(вв) при вычислениях типы множеств не различаются.


Например, базовый силлогизм про Кая, который смертен, потому что тоже человек.

«Кай – человек» - это индивидуальное суждение или одно-элементное множество?


Математика заплатила большим, третьим (первый – открытие, что не все числа рациональны; второй – открытие, что среди корней уравнений с целочисленными коэффициентами могут быть комплексные числа), кризисом около 100 лет назад. Оказалось, что понятие «множества» как совокупности объектов, объединенных каким-либо признаком, приводит к парадоксу – одновременно истинны как некое утверждение, так и его отрицание. Б. Рассел сформулировал это как историю о Севильском цирюльнике, который бреет всех тех и только тех жителей Севильи, которые не бреются сами: может ли он побриться сам? (с одной стороны, не может, но тогда – обязан!) В терминах множеств: рассмотрим «множество всех абстрактных понятий» Ф. Очевидно, это множество само – абстрактное понятие, т.е. ФФ. Рассмотрим теперь множество Г всех таких множеств, которые не являются своими элементами. Можно ли утверждать, что ГГ? Если нет, то Г удовлетворяет определению и, значит, Г Г – парадокс! Чем опасен этот парадокс – тем, что позволяет, в вычислительном плане, вывести любые утверждения; как известно, в математической логике импликация А  Б всегда верна, если А ложно.
Современные объектно-ориентированные языки такие как Джава или Си++ широко используют принадлежность (через наследование классов), но по самому своему определению от подобного парадокса избавлены – через понятие типа, приписываемого любым переменным и классам.
(в) Классификация – это понятие после Аристотеля практически не развивалось (и накопило много повседневных смыслов – вспомните американские classifieds в газетах и classified files в офисах), а между тем, для меня оно одно из главных, по крайней мере, с позиций разработки искусственного интеллекта. Я формулирую это так: «Понятие классификации для описания интеллектуальных систем так же важно, как понятие функции для описания физических систем. Только в классификации пока ещё не нашлось своих Ньютона и Лейбница.» Остановлюсь на этом подробнее.
Аристотель рассматривал классификации, которые обычно называют таксономиями, такие, например, как универсальная библиотечная классификация.
Согласно Порфирию (133 г. после р.Х.), Аристотель рассматривал 5 основополагающих понятий (Predicables) в учении о классификации:

Genus: a set of species (Род - множество видов).

Species: an element of a genus (Вид – элемент рода).

Difference: an attribute added to the genus name to specify a species (Атрибут – признак, выделяющий вид из рода).

Property: a species modality which is characteristic to the genus, although not involved in the genus definition (Свойство –характеристика видов, одинаковая для всех видов данного рода, но не использованная в определении рода).

Accident: a species attribute, modalities of which differ for different species (Признак вида, который .может различаться на разных видах).


Эти понятия хорошо работают в таксономиях. Таксономия – это классификация реально сушествующих вешей, такая как Линнеевская классификация флоры и фауны (растений и животных) – крупные деления по произвольным единицам строения (позвоночные, насекомые и пр.), а мелкие деления (на уровне семейства и вида) – по сходству на уровне совокупности признаков. Удобно представлять таксономию классификационным деревом (Карл Линней, 1707--1778). Подобные классификации делают для многих областей науки (например, ACM Classification of Computer Subjects 1998 или классификации протеиновых структур такие как CATH и SCOP) и техники (в основном для стандартизации продукции). В терминах такой классификации, род – это одна из внутренних вершин дерева, виды – её дети, атрибут – основание деления рода на виды, свойства – признаки, одинаковые для всех видов – детей, а признаки – обычные характеристики, по которым виды могут сравниваться. Работающая таксономия содержит четыре компонента:

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

  2. описание таксонов;

  3. номенклатура – список названий всех таксонов;

  4. идентификационный ключ – правило, позволяющее найти местоположение в таксономии любого ее элемента.

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


Но компьютеры вторгаются в области, где знаний мало, а данных много: Компания хочет оценить перспективные сегменты ранка для своего продукта. Разработчик сложного химического вещества хочет знать его свойства без проведения объемных испытаний. Международная организация хочет представить себе интегральную схему разработок в области нанотехнологии. Комплексный анализ функций нового вируса невозможен без включения его в эволюционное древо родственных вирусов. Эти ситуации порождают проблему построения надежных классификаций по эмпирической информации при отсутствии надежных теоретических представлений о явлении. Возникает необходимость выяснения роли, структуры и механизма действия классификации в подобных ситуациях. Возникаюшие вопросы касаются критериев классификации, роли отдельных переменных, интерпретации компьютерных решений и пр.
Развиваемые подходы – кластер-анализ (cluster analysis), решающие деревья (decision trees), теория умозаключений (knowledge base reasoning) и пр. основаны на очень поверхностных представлениях о классификации. Работ по существу вопроса – единицы.
Стоит упомянуть работу российских ученых Мейена и Шрейдера (1976), в которой сделан шаг к анализу двойственного к таксономии понятия архетипа. В моей книге (Mirkin 1996) обращено внимание на роль классификации в качестве связующего звена между разными аспектами явлений:

- структурой и историей («корреляция» в геологии, соответствие между порядком пластов и временем их отложения),

- структурой и функцией (периодическая таблица),

- структурой, историей и функцией (в биологической таксономии речь идет о структуре частей организма, их функциях, и эволюции организмов),

- структурой и функцией (тип личности) (форма ногтей – тип личности, например, «Короткие ногти – энергичный, любознательный, интуитивный», «Очень большие квадратные ногти – холодный и эгоистичный», и т.п., Bosanko, 1983),

- функцией, установкой (attitude – отношение?) и действием (в психологической теории «traits», тип характера определяет интересы и предпочтения (установки), а также выбор профессиональной деятельности и образа жизни, Brew 1987),



- структурой, установкой и действием (в социологии Маркса класс создает партию, которая приводит к революции).
Эти примеры показывают, что каждое реальное явление или процесс могут быть охарактеризованы триадой структура-история-функция, к которой в человеческих системах добавляются ещё два аспекта – установка-действие. По-моему, интересно «навесить» эту структуру на какие-нибудь современные процессы.
Ещё одна замеченная вещь: неполная корреляция между структурой на множестве элементов и функцией, которую они выполняют в действии: в языкознании, совокупность слов разделена на части речи (глагол, сушествительное, и пр.), которые используются языком в предложениях в соответствующей функции (сказуемое, подлежащее и пр.). Например, обычно роль сказуемого в предложении выполняется глаголом, но вот в предложениях «Он мастер. У него характер твёрже стали.» это не так. Аналогично, члены парламента обычно голосуют согласно платформе партий, которые они представляют, кроме каких-то специальных случаев, которые отражают их личную историю. То же – пространственная конформация белков. Возможно, это отражает необходимость адаптации к меняющимся ситуациям.
Стоит отметить другую, неаристотелевскую форму классификации: типологию, задаваемую совокупностью типов и применяемую на начальных этапах постижения феномена. Тип – это определенная комбинация значений признаков. Например, древнее деление темпераментов на 4 типа (холерик, флегматик, сангвиник, меланхолик) было сформировано по превалирующей в организме «жидкости – хумору» (отвергнуто наукой, но реинтерпретировано недавно в терминах силы и скорости реакции (высокая – низкая). В эмпирических областях типы могут быть представлены конкретными представителями (виноделие, минералогия, литературоведение («Печорин – лишний человек»)). В отличие от таксономии, типология не обязательно предусматривает четкое разбиение – (а) принадлежность к типу может быть менее 100% (fuzzy set), и (б) множество типов не обязательно покрывает все возможности – неполная классификация.
В последнее время классификационное направление получает практическую реализацию в так называемых онтологиях – классификационных схемах хранения и обогащения знаний. Обычно онтология имеет форму таксономии, дополненной содержательными определениями и фактами о связи между таксонами. Такое впечатление, что понятие онтологии выходит на передний план в исследованиях по организации знания. Наиболее развитой является так называемая Gene Ontology (GO). Эта последняя уже начинает использоваться исследователями для анализа получаемых результатов.
Рассказать о моей работе с S. Nascimento and L. Moniz Pereiro (New University, Lisbon, Portugal) по отбражению исследовательской активности на Классификацию Понятий Информатики (ACM CCS 1998).
Рис. 2. Типы (слева) и страты (справа).
К этому примыкает стратификация, в которой классы представляют не типы, а страты такие как классы семей разного дохода – с разным уровнем потребления, как показано на Рис. 2, где оси могут представлять разные направления потребления, скажем, затраты на путешествия и затраты на предметы роскоши..Тогда группы слева соответствуют разным типам потребительской ориентации, а группы справа – разным уровням дохода. Я недавно предложил метод для автоматического выделения страт и делаю пробные расчеты, взял бы(ло) аспирантку в Лондоне, а она вышла замуж и уехала в Париж...
Итак, классификация какого-либо множества – это распределение объектов по классам таким образом, чтобы внутри классов объекты были похожи, а между классами – нет. Этим выявляется структура соответствующей области, а также связи между разными её аспектами. Роль эмпирической классификации в настоящее время огромна. А вычислительных разработок – кот наплакал.
Посмотрим, например, на подход кластер-анализа: кластеры формируются как относительно отделённые группы; например, мы видим два кластера на рис. 3 слева и один – справа.
Рис. 3: Одно- и двух модальное распределения, соответствующие ситуациям одного и двух кластеров, соответственно. На оси ординат отложены частоты (на самом деле, плотность) значений признака на осо абсцисс.

Разумно? Разумно; да и ничего другого пока и не предложено. Но когда группирование делается для определенной цели, этот критерий может оказаться непригодным, и в этом направлении сделано очень мало. Мне помогает в размышлениях вот такой пример – в старой российской армии рекрутирование шло в основном по росту, распределение которого соответствует правой части Рис.2: тех кто ниже 150 см, не брали; а среди новобранцев, тех кто выше 185 см, не брали во флот. То же с группировкой боксеров по весу (пропорционален силе удара).
В недавней работе Robert Stanforth и я пытались делать автоматическую группировку по критерию минимизации ошибки линейной регрессии токсичности сложных химических веществ, так чтобы применять её в условиях, когда токсичность неизвестна (PhD диссертация успешно защищена в 2008).

2.3. Вклад Архимеда

3. История некоторых идей в небесной механике

3.1 Измерение расстояний: распространение простого на сложное.

3.2 Теория тяготения и ненаблюдаемые теоретические величины.

3.3. Эквивалентное выражение различающихся подходов.

3.4. Методы наименьших квадратов и наименьших модулей; нормальное распределение.
3.1 Измерение расстояний: распространение простого на сложное.
Относительно легко померить линейное расстояние длиной до нескольких метров – линейкой. Значительно труднее – большее расстояник, в сотни метров и километры; здесь мы используем менее точные инструменты – шаги, или угловые расстояния и оптические приборы, использующие тригонометрию. Эта же техника помогает измерять высоту холмов. Но для высоты гор – прибегаем к достаточно сложной теории изменения атмосферного давления с высотой. Измерять расстояние до солнца и между звездами требует привлечения даже более прдвинутых теорий, связываюших скорость света и движение звезд. Урок: даже простые на вид измерения становятся очень сложными при распространении на ситуации, не охватываемые руками.

Это касается и таких простых, на первый взгляд, величин как численность населения страны или объем добываемой нефти – их никак не получается измерить без погрешности порядка 5% из-за относительно независимой текучести, запаздываний в операциях и разной интерпретации правил.


3.2 Теория тяготения и ненаблюдаемые теоретические величины.

Теория тяготения была разработана И. Ньютоном (1642-1727) – с подачи Р. Гука (1635-1703), лаборанта, а потом секретаря, Королевского общества, который предложил объяснить законы планетарного движения, сформулированные придворным математиком императора Рудольфа Второго, Иоганном Кеплером (1571-1630), тем, что тела притягиваются к центру Земли с силой, обратно пропорциональной квадрату расстояния до него. (Позднее Ньютон, став президентом Королевского Общества, уничтожит все приборы Гука и его изображения.) Закон этот кажется естественным в терминах жидкости, изливаемой из центра во всех направлениях так, чтобы на любом расстоянии поддерживался баланс между втекающей и вытекающей жидкостями, так как тогда ее количество через любую площадь должно быть пропорционально квадрату расстояния от центра.


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

Первый:

Планеты вращаются по эллипсам, в одном из полюсов которого находится Солнце.


Второй:

Каждая планета, в каком бы месте орбиты она ни находилась, за одно и то же время заметает сектор одной и той же площади.


Третий:

Квадраты периодов обращения планет пропорциональны кубам больших осей их эллиптических орбит.



Напомню, что эллипс определяется заданием каких-либо двух точек, называемых его фокусами – это геометрическое место точек, сумма расстояний которых до фокусов одна и та же. (Можно взять нитку с фиксированным положением концов и обрисовать ее карандашом.)
Закон всемирного тяготения вводит концепцию массы, величины, неизмеримой опытным путем, вместо концепции веса, измеряемого разнообразными весами – почему? Потому, что он утверждает, что любые два тела притягиваются друг к другу пропорционально произведению их масс и обратно пропорционально квадрату расстояния между ними:
(1)
Это значит, что вес предмета (сила притяжения к центру планеты) зависит от места, где его взвешивают! Недаром же говорят, что на Луне все тела весят меньше, чем на Земле.
Ньютон доказал, что законы Кеплера эквивалентны закону всемирного тяготения – первые можно вывести из второго и, наоборот, второй из первых.
Этот вывод рассматривается как обоснование справедливости закона всемирного тяготения, хотя мы до сих пор не умеем обращаться ни с тяготением, ни массой непосредственно – определенный позитивизм: принятие знания без попытки его привязки к основам мироздания. Господствует в современной науке. Мы без боязни вводим всевозможные скрытые, неизмеримые величины в попытках объяснения поведения. Одно из них – объяснение человеческого поведения как рационального – максимизация функции предпочтения при некоторых внешних и внутренних ограничениях.

3.2. Эквивалентное выражение различающихся подходов.

Еще один урок из законов планетарного движения – возможность эквивалентной переформулировки одного и того же уравнения таким образом, чтобы удовлетворять различным критериям.


Классическая формулировка
Классическая формулировка имеет характер формулы (1) и предусматривает дальнодействие силы тяготения.
Локальная формулировка.
Многие не согласны с таким сильным допущением и настаивают на формулировке, использующей только «локальные» взаимодействия. Такая формулировка предложена в терминах так называемого потенциального поля тяготения. Согласно этой формулировке, каждой точке пространства приписано число таким образом, что на каждый предмет действует сила пропорциональная градиенту (т.е. направлению наибольшего увеличения) поля. Само же потенциальное поле организовано таким образом, что потенциал в центре маленькой сферы равен среднему потенциалу на сфере минус член, пропорциональный массе сферы и обратно пропорциональный её диаметру. Коэффициент пропорциональности равен тому G, что фигурирует в формулировке закона всемирного тяготения (1). Эта формулировка локальна по времени и пространству, и она эквивалентна закону всемирного тяготения.
Рациональная формулировка.
Понятие поля удобно, поскольку разделяет условия (поле) и движение анализируемой частицы. В частности, оно позволяет сформулировать так называемую функцию Лагранжа – разность между кинетической энергией и потенциальной энергией ( для наших целей определения этих энергий не так существенны). Теперь мы можем сформулировать еще один принцип, эквивалентный закону всемирного тяготения, но использующий только движение частицы в потенциальном поле. При движении из одной точки в другую частица движется по пути, минимизирующем функцию Лагранжа!
Все три формулировки эквивалентны в механике Ньютона. При этом переформулировки оказались возможными только потому, что в формуле (1) используется квадрат расстояния. Измени степень, и эти формулировки оказываются практически невозможными.
Кроме того, разные формулировки используют разные понятия, поэтому удобны для одних обобщений и неудобны для других. Например, обобщение для квантовой механики опирается на локальную формулировку, а обобщение на общую теорию относительности, в которой скорость гравитации не бесконечна, а ограничена, опирается на принцип минимума.
Различные формулировки модели Кейнса
Более близкий пример – теория государственного вмешательства Дж. М. Кейнса, основанная на его модели, вариант которой можно сформулировать так:
X = aX + b + t,
где Х слева – созданный в экономике продукт, а справа его выражение через потребление населения, которое предполагается пропорциональным Х, производственные инвестиции (b) и правительствен-ные расходы (t). Выражая Х через остальные показатели, получаем
X = b/(1-a) – t/(1-a),
откуда следуют парадоксальные кейнсианские выводы. Если хочешь увеличить производство Х, увеличивай склонность к потреблению (a), инвестиции (b) и государственные расходы (t).
Выраженная в словесной форме, скажем, для государственных расходов, эта идея может быть выражена так. Найми безработных, не важно что делать – рыть ямы или прокладывать дороги, например, лишь бы они получали зарплату. Часть а этой зарплаты они потратят на покупки товаров, тем самым оплатив труд реальных производителей, которые долю а от этого, т. е. а2, тоже потратят на потребление, породив аналогичным образом покупки а3, а4, и т. д., в сумме дающие 1/(1-а). При этом уменьшится безработица, но возрастет инфляция (поскольку ненужный труд безработных оплачивается путем допечатки денег), порождая имманентную для кейнсианства обратную связь: уменьшение безработицы – увеличение инфляции. Ничего такого в математической формулировке нет, так как в ней не отражены механизмы увеличения параметров.
3.4 Методы наименьших квадратов и наименьших модулей; нормальное распределение.
К началу 19 века количество астрономических постов ведущих измерения координат астрономических объектов увеличилось до полутора десятков – возникла надобность в сведении их данных воедино. Быстро выявились систематические ошибки отдельных наблюдателей, например, один был крив на один глаз и всегда выдавал левое смещение, которое было нетрудно учесть. Однако, даже и в скорректированном виде, измерения разнились, и возникла проблема согласования различных измерений одной и той же величины. Эта проблема была сформулирована следующим образом.
При данных М значениях х1, х2,…, хМ, найти значение а, удовлетворяющее уравнениям хм = а + ем, так чтобы минимизировать аддитивные ошибки ем. В данной – многокритериаль-ной – формулировке задача не имеет единственного решения. Возникло два подхода к скаляризации критериев. Один, принцип наименьших модулей, представлял Пьер Лаплас (1749-1827): надо минимизировать сумму абсолютных величин |е1|+|е2|+…+|еМ|. Второй, принцип наименьших квадратов, представлял Карл Гаусс (1777-1855) – надо минимизировать сумму квадратов ошибок, |е1|2+|е2|2+…+|еМ|2. Решением по первому критерию является медиана – то значение из величин хм, которое стоит в середине отсортированного по величине ряда значений. Решением по второму критерию является арифметическое среднее,  =(е1+е2+…+еМ)/М. Оба хороши, медиана обладает теми преимуществами, что является одним из наблюденных значений и, кроме того, не зависит от крайних значений, которым, значит, позволительны любые сколь большие уклонения без какого-либо воздействия на медиану. Напротив, среднее, как правило, не совпадает ни с одним из наблюдений и, более того, неустойчиво относительно изменений в крайних значениях. См., например, ряд значений 1, 5, 1, 5, 3, который после сортировки становится 1, 1, 3, 5, 5, так что медиана равна 3. Среднее этого ряда тоже 3. Если второе значение 5 сильно увеличилось, скажем, до 15, так что сортированный ряд становится 1, 1, 3, 5, 15, то медиана все еще 3, а среднее увеличивается до 5.

Однако, Гаусс предложил теорию для своего критерия, которая оказалась настолько убедительной, что впоследствии легла в основание всего здания математической статистики, где и сейчас занимает центральное место. В основе теории Гаусса – два факта:




  1. Мелкие случайные ошибки, складываясь, приводят к тому, что распределение среднего значения наблюденных величин, в стандартных предположениях независимости и случайности наблюдений, является асимптотически Гауссовым, или нормальным, распределением с плотностью вероятности f(x, , )=Cexp{((x – )/)2}, где параметры  и  - математическое ожидание и стандартное отклонение, соответственно.

  2. Принцип максимального правдоподобия – общее правило, состоящее в том, что при заданной случайной и независимой выборке х1, х2,…, хМ, неизвестные параметры распределения таковы, что вероятность получения именно этой выборки – максимальна – для распределения Гаусса приводит именно к той оценке математического ожидания , которая вытекает из принципа наименьших квадратов. При этом оценкой  является среднеквадратичное отклонение наблюдений от среднего.

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


Однако дискуссия, какой из принципов – наименьших квадратов или наименьших модулей – лучше далека от завершения, и, по сути, едва началась.
Основные выводы:

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

  2. Обоснованием введения ненаблюдаемых величин является возможность объяснения поведения некоторых наблюдаемых величин;

  3. Различные эквивалентные формулировки могут оказаться полезными для различных приложений – сам факт наличия нескольких переформулировок может рассматриваться как эвристическое подтверждение осмысленности соответствующих утверждений;

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



4 Развитие оптимизации

4.1 Точные методы – история и проблемы машинных вычислений.

4.2 Локальные методы и эвристики – проблемы инициализации.

4.3 Нейронные сети для поиска по градиенту.

4.4 Подход имитации природы – эволюция популяции: методы генетические, эволюционные, пчелиного роя и муравьиной кучи.
4.1 Точные методы – история и проблемы машинных вычислений.

Оптимизация – один из самых распространенных принципов в инженерном подходе к природе (принцип наименьшего действия Мопертьюи 1746, химическое равновесие – минимум энергии Гиббс 1857), технике и обществу (Вальрас и Курно – модели, основанные на оптимизации полезности).

Систематический подход – после изобретения дифференциального исчисления на основе уточнения и обобщения свойства обнуления градиента в экстремальной точке (установленного еще Ферма 1646). Работа Лагранжа (1754) устанавливает метод множителей Лагранжа для оптимизации с ограничениями, продолженный в 20 столетии установлением теоремы Куна-Таккера (1951). Градиентный метод изобретен Коши (1847)

Вариационное исчисление Эйлера 1707-1783 (оптимальные функции), увенчавшееся в 20 веке теорией оптимального управления Л.С. Понтрягина (). Линейное программирование и теория игр (Л.В. Канторович, Дж. Фон Нейман и Дж. Данциг). Выпуклое программирование.

Для многих задач, в частности, для всех конечных, известен метод для отыскания точного решения. К сожалению, компьютеры накладывают ограничения:

А. Последовательный, не параллельный, характер вычислений – слишком большие вычисления невозможны по ресурсам времени и среды (например, перебор всех подмножеств миллион-элементного множества, что породило забавную дисциплину теории не полиномиальных задач, таких как задача нахождения общего метода для отыскания всех нулей произвольной булевой функции большого числа переменных (для монотонных функций – задача полиномиальная, применялась академиком О.И. Ларичевым в алгоритмах принятия решений)) – в настоящий момент появились первые архитектуры, так называемые кластеры, с большим количеством определенным образом соединенных машин, на которых можно вести параллельные вычисления;

Б. Ограниченная память – невозможность держать в памяти большие массивы; преодолевается тем же путем – см. Европейскую концепцию Грид – чтобы компьютерная ресурсы были доступны так же, как вода в водопроводе.

В. Фиксированная разрядная сетка для представления чисел – неадекватность, например, отсутствие гарантии сходимости сходящихся рядов. Накладывает требование более глубокой проработки методов, например, для изучения числа обусловленности при обращении матриц (точная задача в условном мире арифметики вещественных чисел).



4.2 Локальные методы и эвристики – проблемы инициализации.

Типичный локальный метод оптимизации функции f(x) по x X, работает следующим итеративным образом:

Для каждого x X определи его окрестность, О(x)X, таким образом, чтобы она содержала относительно небольшое число элементов (например, если x – подмножество заданного множества А, то О(x) может состоять из всех подмножеств, отличающихся от x только одним элементом и принадлежашим X).

0. Возьми начальное допустимое решение x0 X и рассмотри О(x0).

1. Перебери все x О(x0) и выбери из них оптимальное, x1.

2. Если x1 лучше, чем x0, то переопредели x0 – сделай его равным x1, и вернись к шагу 1; в противном случае выдай x1 и f (x1) в качестве окончательного решения.


Работает быстро, да вот решение может быть далеко от оптимального. Возникло направление по выведению оценок близости локальных решений к оптимуму, пока, увы, только по функционалу. На мой взгляд, более перспективно направление отыскания «хороших» инициализаций.
4.3 Нейронные сети для поиска по градиенту.
Нейрон (искусственный) это преобразование входных сигналов в выходной сигнал с помощью их суммирования с весами; выход появляется когда сумма выше порога:


Figure 2. A scheme of artificial neuron, on the left. The same neuron with the firing threshold shown as a wiring weight on the fictitious input always equal to 1, on the right.
Возможность аппроксимировать сложную функцию «квазилинейными» функциями, а для поиска решения использовать локальный метод с выбором не лучшего решения в окресности, а лучшего направления движения. Оказалось, градиентный метод в этой ситуации можно представить как метод взаимодействия между нейронами, составляюшими сеть, при которой каждый нейрон оперирует только с поступающей с предыдущих уровней информацией об ошибке и своими собственными передаточными возможностями, ничего не зная о структуре соседей.

Богатые структурные возможности обеспечившие небывалую популярность в 90-е; но – ограничения: невозможность разумной интерпретации (не в нейрофизике, где, впрочем пока этот аппарат не смог помочь в имитации нейроритмов) и локальность получаемого решения.


4.4 Подход имитации природы – эволюция популяции: методы генетические,

эволюционные, пчелиного роя и муравьиной кучи (genetic algorithms, evolutionary algorithms,
  1   2   3   4   5   6   7

Коьрта
Контакты

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


Матема́тика — наука, изучающая количественные и пространственные соотношения, в действительном мире и человеческом воображении