ВШЭ-ГУ
2011
Борис Григорьевич Миркин
Профессор, Кафедра анализа данных и искусственного интеллекта ОПМИ НИУ ВШЭ, Москва, РФ
Emeritus Professor, 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-1993), США (1993-1998), Германия (1996-1999) и Великобритания (2000-2011).
Математика, чистая и прикладная математика и информатика
Математика – это то, чем занимаются математики. За 2500 лет своего существования понятие о математике видоизменялось и обогащалось. Первоначально – это была абсолютно прикладная дисциплина, связанная с вычислениями (типа астрономических событий или разливами Нила) – в древнем Египте, и землемерием – в древнем Вавилоне, прежде всего с вычислением (они даже изобрели позиционную систему счисления и решали квадратные уравнения); в Египте – прежде всего с землемерием (по закону каждой семье выделялся одинаковый надел, и для поддержания справедливости надо было уметь перераспределять землю при нарушениях баланса, связанных с природными или семейными катаклизмами). Любопытно, что эти знания никак не обменивались, и идеи позиционного счисления вошли в Европейскую науку спустя многие сотни лет через арабскую математику.
Греки внесли в математику идею логического доказательства. Евклид описал планиметрию с помощью аксиоматического метода (аксиомы – логика – теоремы), который в настоящее время понимается многими как главная особенность математики в системе наук. Они же установили, что одни и те же соотношения могут описывать совершенно разные явления (созвучия как пропорции). Такие задачи как решение уравнений, вычисление объемов и описание движения вызвали к жизни появление развитых математических конструкций – вещественные и комплексные числа, функции и дифференциальное исчисление, теория оптимизации, дифференциальная геометрия, дифференциальные уравнения и пр. Это дало основание рассматривать математику как науку об описание количественных и пространственных форм окружающего нас мира.
Из русской Википедии
(i)Матема́тика — наука, изучающая количественные и пространственные соотношения, в действительном мире и человеческом воображении. Существуют совершенно иные и весьма разнообразные трактовки предмета математики и её метода.
(ii) Математика изучает воображаемые, идеальные объекты и соотношения между ними, используя формальный язык. Математические понятия и теоремы не обязательно имеют соответствия чему-либо в физическом мире. Однако некоторые из исследуемых математикой объектов могут иметь прообразы в реальном мире, более или менее похожие на свои математические модели. Модель объекта учитывает не все его черты, а только самые необходимые для целей изучения. Например, изучая физические свойства апельсина, мы можем абстрагироваться от его цвета и вкуса и представить его шаром. Если же нам надо понять, сколько апельсинов получится, если мы сложим вместе два и три, — то можно абстрагироваться и от формы, оставив у модели только одну характеристику — количество. Абстракция и установление связей между объектами в самом общем виде — цель, к которой стремится математика. Наряду с моделированием математика прибегает к обобщениям, например, обобщая понятие «пространство» до пространства n-измерений.
Изучение объектов в математике происходит при помощи аксиоматического метода: сначала для исследуемых объектов формулируется список аксиом и вводятся необходимые определения, а затем из аксиом с помощью правил вывода получают теоремы. Поэтому иногда считают, что (iii) математика — это наука о следствиях из непротиворечивых наборов аксиом
Многие нематематики рассматривают математику как некий универсальный язык, на котором удобно формулировать предположения или факты о свойствах различных явлений, после чего она, как мельница, переработает их в всевозможные следствия. Эти результаты возвращаются в знание о явлении путем их интерпретации. Мне близка эта точка зрения. Я бы сказал, что (iv) математика - это дисциплина, занимающейся разработкой языков для описания структурных и количественных сторон различных явлений и способов перевода между ними.
Язы́к — система звуков, знаков, предназначенная для фиксации, переработки и передачи сведений от одного субъекта к другому.
Следует подчеркнуть, что «фиксация» в этом определении - это очень нетривиальный этап, связанный с выделением и пониманием существенных свойств явления.
Функции языка (релевантные выделены крупным шрифтом)коммуникативная (или функция общения) — основная функция языка, использование языка для передачи информации;
когнитивная (или познавательная функция) — формирование мышления индивида и общества;
информативная (или аккумулятивная функция) — передача информации и её хранение;
эмотивная (или эмоциональная функция) — выражение чувств, эмоций;
волюнтативная (или призывно-побудительная функция) — функция воздействия;
метаязыковая — разъяснения самого языка средствами языка;
фатическая (или контактноустанавливающая);
идеологическая функция — использование того или иного языка или типа письменности для выражения идеологических предпочтений. Например, ирландский язык используется главным образом не для общения, а в качестве символа ирландской государственности. Использование традиционных систем письма часто воспринимается как культурная преемственность, а переход на латиницу — как модернизаторство.
омадативная (или формирующая реальности) - создание реальностей и их контроль
Рассмотрим, как пример, теорию алгебраических квадратичных уравнений, создававшуюся более тысячелетия (от Пифагора, который обнаружил наличие нерациональных корней до Гаусса, который доказал основную теорему математики).
Две, по моему мнению, основные задачи этой теории –
(а) вычисление корней (известная формула x= = p/2sqrt(p2/4-q))
(б) установление связи между двумя языками их описания, внешним – коэффициентов, и внутренним – свойствами корней. Точнее, речь идет об утверждениях, связывающих свойства параметров описания уравнений (p,q) со свойствами корней, вещей ненаблюдаемых. Пример такого утверждения: для того, чтобы оба корня были вещественными необходимо и достаточно, чтобы p2/4-q>0. (Какой красивый и нетривиальный признак, p2/4-q, сформирован из исходных двух признаков - коэффициентов p и q!)
Мне могут возразить, что данная характеристика очевидно вытекает из вышеприведенной формулы – и я скажу, конечно, в данном случае это так. Но имеется значительно больше случаев более сложных уравнений – а всякая инженерная задача в той или иной мере сводится к решению уравнения – когда никакого аналитического решения указать нельзя;
тогда то утверждения о свойствах корней уравнений становятся главным инструментом анализа.
Почему я считаю, что языковый аспект, т.е. прежде всего, так называемые необходимые и/или достаточные условия, так важен? Математика разрастается, как финансовые инструменты. Три основных раздела математики – геометрия, алгебра и анализ – разрастаются, абстрагируются, взаимно проникают друг в друга. Вспомните, какие современные средства алгебры и геометрии понадобились для недавнего решения такой очень просто формулируемой проблемы как так называемая большая теорема Ферма («Ни для каких натуральных чисел а, б и в и ни для какого р>2, невозможно равенство аp+ бp = вp.»)
Чем больше взаимопроникновение, тем больше понимание, тем больший круг явлений реального мира охватывается, а математизация новых явлений приводит к жизни новые конструкции, свойства которых надо изучать – для того, чтобы иметь возможность решать новые задачи. Считается, что изучение свойств уже определенных математических объектов может потребовать не одной сотни лет.
Вычислительная тематика все более передается прикладной математике и информатике, а языковая, связь между абстрактными математическими конструкциями, как гомотопии и соответствующие алгебры, все более углубляется и расширяется. В связи с этим, кстати, меняется понятие «нетривиальности» или «силы» математического результата. Раньше степень нетривиальности ассоциировалась со сложностью, т.е. длиной, доказательства, теперь, по-моему, с «расстоянием» между языками, между которыми устанавливается соответствие.
Чистая математика работает на математику, изучая свойства математических объектов. Прикладная математика ориентирована на приложения вне математики, в других областях науки, технике, экономике и пр. Информатика – реализация математических построений на компьютере; включает существенную инженерную компоненту типа разработки хардвера, поддержки безопасности, формирования протоколов электронных сообщений и пр.
Не существует границы между прикладной и чистой математикой по предмету – граница проходит по области применения: внутри математики (чистая) или в другой области науки или практики (прикладная).
Пример, поясняющий эту мысль:
Малая теорема Ферма (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=(-15)/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 лет назад. Оказалось, что понятие «множества» как совокупности объектов, объединенных каким-либо признаком, приводит к парадоксу – одновременно истинны как некое утверждение, так и его отрицание. Б. Рассел сформулировал это как историю о Севильском цирюльнике, который бреет всех тех и только тех жителей Севильи, которые не бреются сами: может ли он побриться сам? (с одной стороны, не может, но тогда – обязан!) В терминах множеств: рассмотрим «множество всех абстрактных понятий» Ф. Очевидно, это множество само – абстрактное понятие, т.е. ФФ. Рассмотрим теперь множество Г всех таких множеств, которые не являются своими элементами. Можно ли утверждать, что ГГ? Если нет, то Г удовлетворяет определению и, значит, Г Г – парадокс! Чем опасен этот парадокс – тем, что позволяет, в вычислительном плане, вывести любые утверждения; как известно, в математической логике импликация А Б всегда верна, если А ложно.
Современные объектно-ориентированные языки такие как Джава или Си++ широко используют принадлежность (через наследование классов), и, вероятно, от подобного парадокса избавлены – через понятие instance – конкретного экземпляра объекта.
(в) Классификация – это понятие после Аристотеля практически не развивалось (и накопило много повседневных смыслов – вспомните американские 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) и техники (в основном для стандартизации продукции). В терминах такой классификации, род – это одна из внутренних вершин дерева, виды – её дети, атрибут – основание деления рода на виды, свойства – признаки, одинаковые для всех видов – детей, а признаки – обычные характеристики, по которым виды могут сравниваться. Работающая таксономия содержит четыре компонента:
иерархическая, обычно дерево-образная организация элементов рассматриваемого множества, листьями которой являются сами элементы, а внутренние вершины – таксоны – соответствуют классам элементов в под-дереве, корнем которого является таксон;
описание таксонов;
номенклатура – список названий всех таксонов;
идентификационный ключ – правило, позволяющее найти местоположение в таксономии любого ее элемента.
До последнего времени эта схема оставалась неизменной – а что тут менять, когда все – роды, виды и их соотношение – определено данной областью знания? Не нравится классификация – развивай знание данного явления или процесса.
Но компьютеры вторгаются в области, где знаний мало, а данных много: Компания хочет оценить перспективные сегменты ранка для своего продукта. Разработчик сложного химического вещества хочет знать его свойства без проведения объемных испытаний. Международная организация хочет представить себе интегральную схему разработок в области нанотехнологии. Комплексный анализ функций нового вируса невозможен без включения его в эволюционное древо родственных вирусов. Эти ситуации порождают проблему построения надежных классификаций по эмпирической информации при отсутствии надежных теоретических представлений о явлении. Возникает необходимость выяснения роли, структуры и механизма действия классификации в подобных ситуациях. Возникаюшие вопросы касаются критериев классификации, роли отдельных переменных, интерпретации компьютерных решений и пр.
Развиваемые подходы – кластер-анализ (cluster analysis), решающие деревья (decision trees), теория умозаключений (knowledge base reasoning) и пр. основаны на очень поверхностных представлениях о классификации. Работ по существу вопроса – единицы.
Стоит упомянуть работу российских ученых Мейена и Шрейдера (1976), в которой сделан шаг к анализу двойственного к таксономии понятия архетипа. Архетип – это как бы скелет организма, в соответствии с которым организуются его свойства.
В моей книге (Mirkin 1996) обращено внимание на роль классификации в качестве связующего звена между разными аспектами явлений:
- структурой и историей («корреляция» в геологии, соответствие между порядком пластов и временем их отложения),
- структурой и функцией (периодическая таблица),
- структурой, историей и функцией (в биологической таксономии речь идет о структуре частей организма, их функциях, и эволюции организмов),
- структурой и функцией (тип личности) (форма ногтей – тип личности, например, «Короткие ногти – энергичный, любознательный, интуитивный», «Очень большие квадратные ногти – холодный и эгоистичный», и т.п., Bosanko, 1983),
- функцией, установкой (attitude – отношение?) и действием (в психологической теории «traits», тип характера определяет интересы и предпочтения (установки), а также выбор профессиональной деятельности и образа жизни, Brew 1987),
- структурой, установкой и действием (в социологии Маркса класс создает партию, которая приводит к революции).
Эти примеры показывают, что каждое реальное явление или процесс могут быть охарактеризованы триадой структура-история-функция, к которой в человеческих системах добавляются ещё два аспекта – (психологическая или политическая) установка и (физическое или политическое) действие. По-моему, интересно «навесить» эту структуру на какие-нибудь современные процессы. Подобного рода анализ выполнен в популярном учебнике M.G. Roskin, Countries and Concepts: Politics, Geography, Culture, Longman, 11th Edition, 2010. Автор рассматривает основные страны мира, включая Россию в единообразной схеме: (1) вклад прошлого (в России – наибольшая страна мира, особенности славян, русская автократия, насильственная модернизация, войны и коммунизм), (2) ключевые институты (в России - сталинская модель, бюрократия, неизменность паттерна), (3) политические установки (В России - иллюзия общества, расизм, отсутствие культуры демократии), (4) модели взаимодействия, (5) дискуссии. Очевидна связь (1) – история, (2) – структура, (3) и (5) – установка, (2) и (4) – функция, и пр.
Ещё одна замеченная вещь: неполная корреляция между структурой на множестве элементов и функцией, которую они выполняют в действии: в языкознании, совокупность слов разделена на части речи (глагол, сушествительное, и пр.), которые используются языком в предложениях в соответствующей функции (сказуемое, подлежащее и пр.). Например, обычно роль сказуемого в предложении выполняется глаголом, но вот в предложениях «Он мастер. У него характер твёрже стали.» это не так. Аналогично, члены парламента обычно голосуют согласно платформе партий, которые они представляют, кроме каких-то специальных случаев, которые отражают их личную историю. То же – пространственная конформация белков. Возможно, таким пластичным способом отражается необходимость адаптации к меняющимся ситуациям.
Все большее значение приобретают неаристотелевские формы классификации. Из них наиболее популярна типология, задаваемая совокупностью типов и применяемая на начальных этапах постижения феномена. Тип – это определенная комбинация значений признаков. Например, древнее деление темпераментов на 4 типа (холерик, флегматик, сангвиник, меланхолик) было сформировано по превалирующей в организме «жидкости – хумору» (отвергнуто наукой, но реинтерпретировано недавно в терминах силы и скорости реакции (высокая – низкая)). В эмпирических областях типы могут быть представлены конкретными представителями (виноделие, минералогия, литературоведение («Печорин – лишний человек»)). В отличие от таксономии, типология не обязательно предусматривает четкое разбиение – (а) принадлежность к типу может быть менее 100% (fuzzy set), и (б) множество типов не обязательно покрывает все возможности – неполная классификация.
Рис. 2. Типы (слева) и страты (справа).
К этому примыкает стратификация, в которой классы представляют не типы, а страты такие как классы семей разного дохода – с разным уровнем потребления, как показано на Рис. 2, где оси могут представлять разные направления потребления, скажем, затраты на путешествия и затраты на предметы роскоши..Тогда группы слева соответствуют разным типам потребительской ориентации, а группы справа – разным уровням дохода. Я недавно предложил метод для автоматического выделения страт и делаю пробные расчеты, взял бы(ло) аспирантку в Лондоне, а она вышла замуж и уехала в Париж...
Итак, классификация какого-либо множества – это распределение объектов по классам таким образом, чтобы внутри классов объекты были похожи, а между классами – нет. Этим выявляется структура соответствующей области, а также связи между разными её аспектами. Роль эмпирической классификации в настоящее время огромна. А вычислительных разработок – кот наплакал.
Посмотрим, например, на подход кластер-анализа: кластеры формируются как относительно отделённые группы; например, мы видим два кластера на рис. 3 слева и один – справа.
Рис. 3: Одно- и двух модальное распределения, соответствующие ситуациям одного и двух кластеров, соответственно. На оси ординат отложены частоты (на самом деле, плотность) значений признака на оси абсцисс.
Разумно? Разумно; да и ничего другого пока и не предложено. Но когда группирование делается для определенной цели, этот критерий может оказаться непригодным, и в этом направлении сделано очень мало. Мне помогает в размышлениях вот такой пример – в старой российской армии рекрутирование шло в основном по росту, распределение которого соответствует правой части Рис.2: тех кто ниже 150 см, не брали; а среди новобранцев, тех кто выше 185 см, не брали во флот. То же с группировкой боксеров по весу (пропорционален силе удара).
В последнее время классификационное направление получает практическую реализацию в так называемых онтологиях – классификационных схемах хранения и обогащения знаний. Обычно онтология имеет форму таксономии, дополненной содержательными определениями и фактами о связи между таксонами. Такое впечатление, что понятие онтологии выходит на передний план в исследованиях по организации знания. Наиболее развитой является так называемая Gene Ontology (GO). Эта последняя уже начинает использоваться исследователями для анализа получаемых результатов. В последнее время большой импульс получило дело создания медицинской онтологии для практических приложений (SNOMED CT, USA).
В моей работе с S. Nascimento and L. Moniz Pereiro (New University, Lisbon, Portugal) (2008-2011) проводилось отображение исследовательской активности на Классификацию Понятий Информатики, разработанную Всемирной ассоциацией вычислительных машин (Association for Computing Machinery, ACM CCS 1998).
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.
Однако, Гаусс предложил теорию для своего критерия, которая оказалась настолько убедительной, что впоследствии легла в основание всего здания математической статистики, где и сейчас занимает центральное место. В основе теории Гаусса – два факта:
Мелкие случайные ошибки, складываясь, приводят к тому, что распределение среднего значения наблюденных величин, в стандартных предположениях независимости и случайности наблюдений, является асимптотически Гауссовым, или нормальным, распределением с плотностью вероятности f(x, , )=Cexp{((x – )/)2}, где параметры и - математическое ожидание и стандартное отклонение, соответственно.
Принцип максимального правдоподобия – общее правило, состоящее в том, что при заданной случайной и независимой выборке х1, х2,…, хМ, неизвестные параметры распределения таковы, что вероятность получения именно этой выборки – максимальна – для распределения Гаусса приводит именно к той оценке математического ожидания , которая вытекает из принципа наименьших квадратов. При этом оценкой является среднеквадратичное отклонение наблюдений от среднего.
В дальнейшем принцип наименьших квадратов был распространен на значительно более общие задачи анализа данных, включая регрессионный, факторный и кластерный анализы. Главным при этом явились не столько вероятностные свойства, сколько удобство математической формы критерия и хорошие математические свойства получаемых решений, в основном определяемые многомерными аналогами теоремы Пифагора, когда квадратичный разброс данных раскладывается на сумму «квадратов» его объясненной и необъясненной частей.
Однако дискуссия, какой из принципов – наименьших квадратов или наименьших модулей – лучше далека от завершения, и, по сути, едва началась.
Основные выводы:
Измерения, даже интуитивно очевидных величин, при переходе к большим системам требуют разработки неочевидных теорий и сопряжены с ошибками;
Обоснованием введения ненаблюдаемых величин является возможность объяснения поведения некоторых наблюдаемых величин;
Различные эквивалентные формулировки могут оказаться полезными для различных приложений – сам факт наличия нескольких переформулировок может рассматриваться как эвристическое подтверждение осмысленности соответствующих утверждений;
Принципы наименьших квадратов и модулей удобны для обработки данных, но их использование нуждается в дальнейшем исследовании.4 Развитие оптимизации
4.1 Точные методы – история и проблемы машинных вычислений.
4.2 Локальные методы и эвристики – проблемы инициализации.
4.3 Нейронные сети для поиска по градиенту.
4.4 Подход имитации природы – эволюция популяции: методы генетические, эволюционные, пчелиного роя и муравьиной кучи.
4.1 Точные методы – история и проблемы машинных вычислений.
Оптимизация – один из самых распространенных принципов в инженерном подходе к природе (принцип наименьшего действия Мопертьюи 1746, химическое равновесие – минимум энергии Гиббс 1857), технике и обществу (Вальрас и Курно – модели, основанные на оптимизации полезности).
Систематический подход – после изобретения дифференциального исчисления на основе уточнения и обобщения свойства обнуления градиента в экстремальной точке (установленного еще Ферма 1646). Работа Лагранжа (1754) устанавливает метод множителей Лагранжа для оптимизации с ограничениями, продолженный в 20 столетии установлением теоремы Куна-Таккера (1951). Градиентный метод изобретен Коши (1847)
Вариационное исчисление Эйлера 1707-1783 (оптимальные функции), увенчавшееся в 20 веке теорией оптимального управления Л.С. Понтрягина (1957). Линейное программирова-ние и теория игр (Л.В. Канторович 1939, Дж. Фон Нейман 1948 и Дж. Данциг 1950).
Для многих задач, в частности, для всех конечных, известен метод для отыскания точного решения. К сожалению, компьютеры накладывают ограничения:
А. Последовательный, не параллельный, характер вычислений – слишком большие вычисления невозможны по ресурсам времени и среды (например, перебор всех подмножеств миллион-элементного множества, что породило забавную дисциплину теории не полиномиальных задач, таких как задача нахождения общего метода для отыскания всех нулей произвольной булевой функции большого числа переменных (для монотонных функций – задача полиномиальная, применялась академиком О.И. Ларичевым в алгоритмах принятия решений)) – в настоящий момент появились первые архитектуры, так называемые кластеры, с большим количеством определенным образом соединенных машин, на которых можно вести параллельные вычисления;
Б. Ограниченная память – невозможность держать в памяти большие массивы; преодолевается тем же путем – см. Европейскую концепцию Грид – чтобы компьютерная ресурсы были доступны так же, как вода в водопроводе.
В. Фиксированная разрядная сетка для представления чисел – неадекватность, например, отсутствие гарантии сходимости сходящихся рядов. Накладывает требование более глубокой проработки методов, например, для изучения числа обусловленности при обращении матриц (точная задача в условном мире арифметики вещественных чисел).
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 Подход имитации природы – эволюция популяции: методы генетические,
эволюционные, пчелиного роя и муравьиной кучи (geneticalgorithms, evolutionaryalgorithms, particleswarmoptimizationandantcolonyoptimization).
Во всех этих методах главное то, что моделируется эволюция популяции решений, тогда как в классической оптимизации речь идет только об одном решении и его последовательном улучшении. Это – основа современного развития вычислительного интеллекта. Здесь всё еще только начинается.
Генетические алгоритмы – представляют возможные решения последовательностями – «хромосомами», которые от итерации к итерации «скрещиваются», подвергаются «кроссинговеру» и «мутируют». При этом лучшие решения запоминаются и определенным образом используются. После определенного числа итераций (поколений) наилучшее достигнутое решение выдается в качестве результата.
Эволюционные алгоритмы – так же осуществляют переход от поколения к поколению, но без использования «хромосом». Решения здесь обычно представляют, как обычно, через числовые значения, векторы и матрицы, а мутации и скрещивания заменяют изменениями в случайных направлениях.
Оптимизация роя частиц – еще дальше отходит от генетической интерпретации. Здесь популяция – это частиц рой, движущихся в случайном направлении со случайными скоростями, модифицируемыми в направлении достигнутых наилучших решений. На удивление, подобные методы довольно легко «раскалывают» задачи оптимизации сложных нелинейных функций с нелинейными же ограничениями.
В применении же к большим данным обнаруживается общий недостаток методов, инспирированных природой – долгое время вычислений.
5. Некоторые идеи вероятности и статистики.
В настоящее время, когда многие математики подходят к статистике как части теории вероятностей, трудно представить, что в начале статистика не имела ничего общего с вероятностью, хотя обе возникли в государствах Северной Италии в период зарождения капитализма, 17 век. Статистика – от слова «стата» (государство) – для отражения показателей народного хозяйства и населения, теория вероятности из потребности анализа карточных игр – карточная игра там была тогда средой для формирования отношений и заключения договоров. Можно сказать, что теория вероятностей зародилась в переписке П.Ферма (1601-1665) и Б. Паскаля (1623-1662).
Вероятность - это мера случайности. Что такое случайность? Вот четыре довольно разных подхода:
(а) Выбор из хорошо перемешанной колоды – классический взгляд. Вера в существование механизма, устойчиво перемешивающего колоду.
(б) Вероятность события сопряжена с частотой его появления в «вероятностном эксперименте» (по сути – та же хорошо перемешанная колода).
(в) Степень нашей уверенности в появлении события – это понимание отсеялось недавно в так называемые нечеткие множества.
(г) Подход А.Н. Колмогорова: случайность это отсутствие закономерности; тогда степень случайности данной последовательности – сложность или даже длина программы, ее порождающей. Этот взгляд объединяет случайность со сложностью и информативностью. Он связан с развитием вычислительной техники и необходимостью разработки алгоритмов для генерации «случайных» - математики говорят, псевдослучайных – чисел.
Первоначально статистика не имела ничего общего с вероятностью; она развивалась - сначала в Англии как политическая арифметика (родоначальник – Уильям Петти (1623-1687))– для демографических и народнохозяйственных оценок. Связь с вероятностью, равно как и обоснование идеологии статистического вывода, а также и практики статистического наблюдения – в трудах одного из основателей статистики как науки, включая переписи населения – бельгийца Адольфа Кетле (1796-1874) при исследовании частот различных социальных явлений таких как самоубийство. Серьезную роль сыграли российские ученые П.Л. Чебышев (1821-1894), А.А. Марков (1856-1922), А.И. Чупров (1842-1908), А.М. Ляпунов (1857-1918) и А.Н. Колмогоров (1903-1987).
5.1 Вероятностная статистическая модель как средство анализа данных.
Рассмотрим множество N наблюденных значений какого-либо показателя X={x1,…,xN}. Хотя рассматривается одномерная характеристика, все дальнейшее верно и для многомерных наблюдений.
Вероятностник будет считать, что эти числа – независимая случайная выборка из распределения с плотностью f(u/a), где a – параметры распределения, как например, в случае нормального распределения
f(u/(, )= Cexp{-(u - )2 / 22},
где a=(, математическое ожидание и дисперсия.
Вероятностный статистик будет склонен рассматривать математическую модель наблюдений, например, в форме уравнения
xi = a + ei, для всех i=1,2,…, N
где ei - аддитивные ошибки, подчиняющиеся определенному закону распределения.
И в том, и в другом случае данные используются для оценки параметров соответствующих моделей. Основные проблемы – насколько точно оценены параметры? Как сделать оценки поточнее? Нельзя ли уменьшить зависимость от вида функции распределения? Как убедиться, что распределения соответствуют предположениям?
5.2 Смысл коэффициента корреляции.
Рассмотрим множество N наблюденных пар значений показателей (x,y)={(x1, y1), …,(xN, yN)}. Вопрос – можно ли что-нибудь сказать о связи y с x? На этот вопрос Ф. Галтон – а его интересовала связь способностей родителей и их детей, - предложил свою теорию регрессионного анализа (1896), смысл которой состоял в том, что надо построить линейную зависимость y=ax+b с оценкой постоянных коэффициентов a и b исходя из идеи минимизации суммарной квадратичной погрешности оцененных через х значений y с наблюденными. Согласно этой теории, характеристикой связи x и y является коэффициент корреляции
= [i (xi – mx)(yi-my)] ⁄[Nx)y)]
А именно, оптимальные значения коэффициентов регрессионного уравнения определяются формулами
a = (y) /(x)
b = my –a*mx
где mx, my– средние значения, а (y), (x) – среднеквадратичные (стандартные) отклонения переменных величин xi и yi,соответственно. При этом минимальное значение суммы квадратов погрешностей в значениях yi , получаемых если принять линейную зависимость yi = axi+b, равно
Lm(a,b) = N2(y)(1- 2)
так что величина 2 показывает, насколько уменьшается дисперсия y , если учесть линейную зависимость y от x.
Таким образом, коэффициент корреляции, действительно, характеризует связь между переменными, но не вообще, как неправильно пишут в интернете, а именно ЛИНЕЙНОЙ связи. Например, на Рис. 2 представлены три ситуации нулевого коэффициента корреляции, из которых только одна характеризует полное отсутствие связи.
Figure 2. Three scatter-plots corresponding to zero or almost zero correlation coefficient ; the case on the left: no relation between x and y; the case in the middle: a non-random quadratic relation y=(x-2)2+5; the case on the right: two symmetric linear relations, y=2x-5 and y=-2x+3, each holding at a half of the entities.
К. Пирсон, сотрудничавший с Ф. Галтоном, нашел потрясающую вероятностную интерпретацию коэффициенту корреляции, тем самым дав фундамент математической статистике на последующие десятилетия. Оказалось, что коэффициент корреляции может трактоваться как выборочная оценка параметра двумерного Гауссового распределения. Функция плотности z-score нормированного Гауссова распределения:
f(u, )= C* exp{-uT-1u/2}
где =(x, y) двумерный вектор с компонентами x и y, а - ковариационная (корреляционная) матрица
в которой - это параметр определяющий параметры эллиптических линий уровня функции плотности. На любой линии уровня uT-1u является постоянной, так что x2-2xy+y2=const. Как известно, это – уравнение эллипса, вырождающегося в окружность при =0 и в пару прямых при = 1.
Рис. 3. Пример двумерного нормального распределения.
Этот факт – в основе следующего недоразумения. Некоторые статистики утверждают, что расчет линейной регрессии и коэффициента корреляции имеет смысл только в ситуации двумерной нормальности (Гауссовости). Очевидно, что здесь –расширение импликации «Гаусс Коэффициент корреляции» до эквивалентности «Гаусс Коэффициент корреляции», как обычно, совершенно неоправданное.
Линейная зависимость сама по себе ничего общего не имеет с Гауссовостью; как описано выше, в чисто аппроксимационном контексте коэффициент корреляции имеет вполне разумное, хотя и другое истолкование.
5.3. Проблема выбора вида модели описания корреляции: Бритва Окхама, принципы простоты и минимума сложности описания, сложность по Вапнику-Червоненкису.
To specify a problem of learning correlation in a data table, one has to distinguish between two parts in the feature set: predictor, or input, features and target, or output, features. Typically, the number of target features is small, and in generic tasks, there is just one target feature. Target features are usually difficult to measure or impossible to know beforehand. This is why one would want to derive a decision rule relating predictors and targets so that prediction of targets can be made after measuring predictors only. Examples of learning problems include:
(a) chemical compounds: input features are of the molecular structure, whereas target features are activities such as toxicity or healing effects;
(b) types of grain in agriculture: input features are those of the seeds, ground and weather, and target features are of productivity and protein contents,
(c) industrial enterprises: input features refer to technology, investment and labor policies, whereas target features are of sales and profits;
(d) postcode districts in marketing research: input features refer to demographic, social and economic characteristics of the district residents, target features – to their purchasing behavior;
(e) bank loan customers: input features characterize demographic and income, whereas output features are of (potentially) bad debt;
(f) gene expression data: input features relate to levels of expression of DNA materials in the earlier stages of an illness, and output features to those at later stages.
A decision rule predicts values of target features from values of input features. A rule is referred to as a classifier if the target is categorical and as a regression if the target is quantitative. A generic categorical target problem is defined by specifying just a subset of entities labeled as belonging to the class of interest – the correlation problem in this case would be of building such a decision rule that would recognize, for each of the entities, whether it belongs to the labeled class or not. A generic regression problem – the bivariate linear regression – has been considered выше.
Figure 5.1. Structure of a training/testing problem: In training, on the top, the decision rule is fitted to minimize the difference between the predicted and observed target data. In testing, the bottom part, the rule is used to calculate the difference so that no feedback to the rule is utilized.
A decision rule is learnt over a dataset in which values of the targets are available. These data are frequently referred to as the training data. The idea underlying the process of learning is to look at the difference between predicted and observed target feature values on the training data set and to minimize them over a class of admissible rules. The structure of such a process is presented on the upper part of Figure 5.1.
The notion that it ought to be a class of admissible rules pre-specified emerges because the training data is finite and, therefore, can be fit exactly by using a sufficient number of parameters. However, this would be valid on the training set only, because the fit would capture all the errors and noise inevitable in data collecting processes. Take a look, for example, at the 2D regression problem on Figure 5.2 depicting seven points on (x,u)-plane corresponding to observed combinations of input feature x and target feature u.
u
x
Figure 5.2. Possible graphs of interrelation between x and u according to observed data points (black circles).
The seven points on Figure 5.2 can be exactly fitted by a polynomial of 6th order u = p(x) = a0+a1x+a2x2+ a3x3 +a4x4+a5x5+a6x6. Indeed, they would lead to 7 equations ui=p(xi) (i=1,…,7), so that, in a typical case, the 7 coefficients ak of the polynomial can be exactly determined. Having N points observed would require an N-th degree polynomial to exactly fit them.
However, the polynomial, on which graph all observations lie, has no predictive power both within and beyond the range. The curve may go either course (like those shown) depending on small changes in the data. The power of a theory – and a regression line is a theory in this case – rests on its generalization power, which, in this case, can be cast down as the relation between the number of observations and the number of parameters: the greater the better. When this ratio is relatively small, statisticians would refer to this as an over-fitted rule. The overfitting normally would produce very poor predictions on newly added observations. The blue straight line fits none of the points, but it expresses a simple and very robust tendency and should be preferred because it summarizes the data much deeper: the seven observations are summarized here in just two parameters, slope and intercept, whereas the polynomial line provides no summary: it involves as many parameters as the data entities. This is why, in learning decision rules problems, a class of admissible rules should be selected first. Unfortunately, as of this moment, there is no model based advice, within the data analysis discipline, on how this can be done, except very general ones like “look at the shapes of scatter plots”. If there is no domain knowledge to choose a class of decision rules to fit, it is hard to tell what class of decision rules to use.
A most popular advice relates to the so-called Occam’s razor, which meansthat the complexity of the data should be balanced by the complexity of the decision rule. A British monk philosopher William Ockham (c. 1285–1349) said: “Entities should not be multiplied unnecessarily.” This is usually interpreted as saying that all other things being equal, the simplest explanation tends to be the best one. Operationally, this is further translated as the Principle of Maximum Parsimony, which is referred to when there is nothing better available. In the format of the so-called “Minimum description length” principle, this approach can be meaningfully applied to problems of estimation of parameters of statistic distributions (see P.D. Grьnwald 2007). Somewhat wider, and perhaps more appropriate, explication of the Occam’s razor is proposed by Vapnik (2006). In a slightly modified form, to avoid mixing different terminologies, it can be put as follows: “Find an admissible decision rule with the smallest number of free parameters such that explains the observed facts” (Vapnik 2006, p. 448). However, even in this format, the principle gives no guidance about how to choose an adequate functional form. For example, which of two functions, the power function f(x)=axb or logarithmic one, g(x)=blog(x)+a, both having just two parameters a and b, should be preferred as a summarization tool for graphs on Figure 5.3?
Figure 5.3. Graph of one two functions, f(x)=65x0.3 and g(x)=50log(x)+30, both with an added normal noise N(0,15), is presented on each plot. Can the reader give an educated guess of which is which? (Answer: f(x) is on the right and g(x) on the left.)
Another set of advices, not incompatible with those above, relates to the so-called falsifability principle by K. Popper (1902-1994), which can be expressed as follows: “Explain the facts by using such an admissible decision rule which is easiest to falsify” (Vapnik 2006, p. 451). Inprinciple, to falsify a theory one needs to give an example contradicting to it. Falsifability of a decision rule can be formulated in terms of the so-called VC-complexity, a measure of complexity of classes of decision rules: the smaller VC-complexity the greater the falsifability.
Figure 5.4. Any two-part split of three points (not on one line) can be made by a linear function, but the pr
Let us explain the concept of VC-complexity for the case of a categorical target, so that a decision rule to be would be a classifier. However many categorical target features are specified, different combinations of target categories can be assigned different labels, so that a classifier is bound to predict a label. A set of classifiers is said to shatter the training sample if for any possible assignment of the labels, a classifier exactly reproducing the labels can be found in . Given a set of admissible classifiers , the VC-complexity of a classifying problem is the maximum number of entities that can be shattered by classifiers from . For example, 2D points have VC complexity 3 in the class of linear decision rules. Indeed, any three points, not lying on a line, can be shattered by a line; yet not all four-point sets can be shattered by lines, as shown on Figure 5.4, the left and right parts, respectively.
The VC complexity is an important characteristic of a correlation problem especially within the probabilistic machine learning paradigm. Under conventional conditions of the independent random sampling of the data, an reliable classifier “with probability a% will be b% accurate, where b depends not only on a, but also on the sample size and VC-complexity” (Vapnik 2006).
The problem of learning correlation in a data table can be stated, in general terms, as follows. Given N pairs (xi, ui),i =1, …, N, in which xi are predictor/input p-dimensional vectors xi=(xi1,…,xip) and ui = (ui1,…,uiq) are target/output q-dimensional vectors (usually q=1), build a decision rule
ы = F(x)
such that the difference between computed ы and observed u is minimal over a pre-specified class of admissible rules F.
5.4 Принципы статистической оценки: Максимум правдоподобия и Бэйесов подход.
Максимум правдоподобия: Используется для оценки значений параметров распределения. Параметры распределения – те, при которых наблюденные значения обращают вероятность наблюденной выборки в максимум. Очень успешен: удалось математически доказать, что оценки таких статистик как среднее и дисперсия по этому принципу – не смещенные. В последнее время дополняется принципом минимума длины описания, так как сам по себе о числе параметров не говорит.
Подход Бэйеса: Используется не для оценки значений параметров, но лишь для уточнения характера распределения. Исходное распределение f(y) заменяется при этом на распределение f(y/x), где - x наблюденные данные, с помощью теоремы Бэйеса, которая позволяет вычислить p(y/x) по известной p(x/y).
6 История и методология анализа данных
6.1 Понятие признака; виды шкал измерения; адекватность количественных утверждений.
6.2 Основные задачи анализа данных в связи с обогащением знаний
6.3 Аппроксимационный подход к анализу данных: метод наименьших квадратов как эвристический принцип; декомпозиция разброса данных.
6.4. Другие парадигмы в анализе данных (классической статистики, машинного обучения, обогащения знаний, эвристического моделирования)
6.5 Разработка данных и концепция «интересного».
6.6 Современные подходы к представлению знаний.
6.1 Понятие признака; виды шкал измерения; адекватность количественных утверждений.
Математик считает, что признак – это отображение множества (всех возможных) объектов в какое-либо множество, называемое множеством значений. Математический статистик полагает, что признак – это случайная величина. Физик или социолог включают сюда способ измерения с постоянной – и не очень-то решаемой – проблемой: как убедиться, что измеряется именно заявленный показатель (валидность), а также как понять насколько точно измерение –(надежность). Социальные измерения – это настоящая головная боль. Это особенно ясно, когда измеряешь такие характеристики как общественный продукт (сильно влияет количество трансформаций типа зерно/мука/хлеб или более сложных как, скажем, при строительстве домов) или производительность труда (задача нелегкая даже когда речь идет об относительно однородном труде, как вождение автофургона, а если речь идет о всех водителях региона за год – надо учесть, например, их болезни, отпуска, поломки и т.п.). Или возьмите Марксову категорию «общественно необходимый труд» - как узнать? – А ведь вся теория социализма опирается на это понятие.
Много внимания было уделено проблеме: как отделить количественные признаки от качественных.
На основе более ранних изысканий Гельмгольца и др. в физике, психолог С. Стивенс сформулировал понятие типа шкалы (1948 г.), которое в основном стало общепринятым. Тип шкалы x, понимаемой как отображение множества объектов в множество значений, кодированное вещественными числами, определяется множеством её допустимых преобразований Ф={}, так что признак остается тем же после преобразования (x) для всякого Ф. В соответствии с этим выделяют типы шкал:
- абсолютный (Ф состоит из одного тождественного преобразования (x)=x; пример – счет индивидов),
- отношений или относительный (Ф состоит из преобразований вида (x)=ax для произвольных вещественных a; всякое выбранное a соответствует выбору масштаба),
- интервалов или интервальный (Ф состоит из преобразований вида (x)=ax+b для произвольных вещественных a, b; всякое выбранное a соответствует выбору масштаба, а b – выбору начала шкалы; пример – шкалы Цельсия и Фаренгейта для измерения температуры воздуха),
- порядка или порядковый или ординальный (Ф состоит из всех монотонно возрастающих преобразований (x) ),
- наименований или номинальный (Ф состоит из всех взаимно-однозначных преобразований (x)).
Откуда берется множество Ф? Разные точки зрения. Репрезентационная теория (П. Суппис, Д. Льюс и др. 1963) – из свойств отношений между объектами, соответствующими данному признаку. Например, свойства отношений «масса а больше массы б», «разница между массами а и б больше разницы между массами в и г» приводят к тому, что масса выражается в относительной шкале. Физики утверждают, что из свойств инвариантности уравнений соответствующей физической теории. Радикалы как я выводят Ф из общественной практики. Например, практика использования среднего балла по результатам тестов/экзаменов для ранжирования студентов по успеваемости: если мы признаем справедливость (=осмысленность) этих сравнений, то мы тем самым признаем, что экзаменационные оценки выражаются в интервальной шкале (это – теорема, попробуйте доказать).
6.2 Основные задачи анализа данных в связи с обогащением знаний
В международной литературе, задачи анализа данных систематизированы в соответствии со схемой, предложенной в книге Дуда и Харт, Анализ сцен и распознавание образов (1973) – главное, это задача узнавания/диагностики/классификации, а задачам факторного анализа или ранжирования места не нашлось вообще – их помещают в предобработку данных. В книге Миркин (1980) «Анализ качественных признаков и структур» я предложил более систематизированную классификацию (была включена в ГОСТ СССР). Эта классификация, недавно представленная в моем учебнике Mirkin (2011), исходит из того, что главная цель анализа данных – это обогащение теоретических представлений (знаний) об анализируемом объекте. Знания структурно – не что иное как совокупность понятий и связывающих их утверждений. Значит, есть два главных способа обогащения знаний – формирование новых понятий, признаков, и формирование новых связей между признаками. Анализ данных делает это на основе существующих признаков и данных о них. Формирование новых признаков происходит в форме агрегирования имеющихся признаков в виде ранжирования (ординальная шкала) или разбиения (номинальная шкала) или количественной комбинации (интервальная шкала). Формирование новых связей – в форме решающего правила, связывающего значения одних, целевых, признаков с значениями других, входных, признаков.
Типичные примеры таких задач можно увидеть в следующей таблице:
Колич Анализ главных компонент
Агрегирование
Номин Кластер-анализ
Ордин Ранжирование
Колич Регрессионный анализ
Связь
Номин Распознавание образов
Классификация с учителем
Ордин Ординальная регрессия
6.3 Аппроксимационный подход к анализу данных: метод наименьших квадратов как эвристический принцип; декомпозиция разброса данных.
Согласно аппроксимационному подходу, любая специфическая задача анализа данных должна включать в себя два аспекта: первый, кодирование, формирование по данным Х результата А в требуемом формате (разбиение, продукция, решающее дерево и т.п.), и второй, декодирование – восстановление данных в том формате, в котором они представлены, на основе имеющегося решения, У(А). Чем точнее результат, У(А), воспроизводит данные Х, тем лучше полученное в результате анализа данных решение. Этот принцип позволяет ставить задачу так:
Исходя из данных Х, сформировать решение заданного вида А таким образом, чтобы разность Х-У(А) была как можно меньше. Если Х – сложный объект, например, матрица, минимизация разности обычно осуществляется в соответствии с принципом наименьших квадратов, как минимизация суммы квадратов разностей. По-видимому, этот принцип отражает какие-то глубинные свойства нашего мира, и что приятно, позволяет использовать теорему Пифагора: //Х//2=//У(А)// 2 + //Х-У(А)// 2, разлагающую разброс данных на объясненную и необъясненную части, что сильно помогает при поиске и интерпретации решений.
Как обосновать квадратичный критерий? При вероятностном истолковании данных, он возникает как реализация критерия максимального правдоподобия. А без оного – можно идти по методике Гука-Ньютона – показать, что из него выводятся какие-либо другие, хорошие, вещи. Например, я показал, что подобный квадратичный анализ нечисловых признаков приводит к статистическим характеристикам, типа коэффициентов ассоциации хи-квадрат, которые популярны в статистике (из других соображений) и, кроме того, связаны с совсем казалось бы не относящимися к делу вещами типа коэффициентов нормализации данных (Mirkin 2005б 2011).
6.4. Другие парадигмы в анализе данных (классической статистики, машинного обучения, пополнения знаний, эвристического моделирования)
Классическая статистика: имеется модель изучаемого явления/процесса; данные представляют интерес лишь постольку, поскольку они могут помочь в уточнении модели и ее параметров.
Машинное обучение: объекты появляются один за одним; задача состоит в том, чтобы построить решающее правило как можно точнее прогнозирующее интересующие нас свойства.
Пополнение знаний: имеются признаки и связи между ними; данные используются для того, чтобы сформировать новые признаки и/или связи.
Эвристическое моделирование: Давайте преобразуем данные по некоторому разумному правилу и применим к реальным проблемам.
6.5 Разработка данных и концепция «интересного».
Дата майнинг (разработка данных) как направление возникло в середине 90-х, оформив сразу большие данные и задачу об анализе транзакций – списков покупок и построенных на них ассоциативных правил. В отличие от статистиков, которые оперировали ошибками первого и второго рода, разработчики данных обратили внимание на поддержку и точность. Рассмотрим, например, множества товаров А и Б, а также множества покупателей, купивших А (безотносительно к Б) или и А, и Б, соответственно, численностей Р(А) и Р(АБ). Тогда величина р(Б/А)= Р(АБ)/Р(А) (условная доля) характеризует точность логической продукции АБ. Если, например, р(Б/А)=0.9,
это значит, что ошибка продукции АБ (на материале обучения) равна 0.1 (ошибка первого рода). Но для настоящего анализа этого мало. Ведь на множестве людей предикаты А=«когда-нибудь ел огурцы» и Б=«умер» дают р(Б/А)=1, ноль ошибок ! Надо смотреть на дополнительные события в четырех-клеточной таблице
Б не Б Всего
А a b a+b
не А c d c+d
Всего a+c b+d 1
Такие таблицы очень уместны, когда речь идет о правилах обнаружения событий. Например, когда Б – правило для обнаружения события А (спам-фильтр и спам, детектор и террорист, и пр.) Ошибка первого рода: 1- р(Б/А)= b/(a+b), второго – c/(c+d). Но в ситуации транзакций, они вообще не смотрят «не А», тогда то и используется «поддержка», р(А)=a+b, а чтобы отсеять смерть от огурцов вводится концепция интересного. Хотя и могли бы использовать ошибки второго рода – но это совсем другое направление анализа, почему-то не получившее развития.
Интересное = необычное, очень редкое или аномальное. Смерть от огурцов логически правильна, но не интересна. Много методов выявления, описания и формирования аномальных паттернов.
6.6 Современные подходы к представлению знаний.
Формальная система (начальный, во многом дезавуированный в 80 годы, этап):
- знание представляется в виде формальной системы – основных предикатов, аксиом накладываемых на них, и правил вывода. В последнее время сюда включаются характеристики пространства, времени, а также модальности (долженствования) и этики.
Экспертная система:
Когда элементы знания сообщаются, хотя бы частично, человеком;
Онтология (современный этап):
- знание представляется в виде:
(а) иерархии основных понятий,
(б) системы отношений, в которых они участвуют (сюда могут включаться предикаты и правила вывода), и
(в) индивидуальных фактов, соответствующих тем или иным отношениям.
7. Дискретная математика и графы
7.1 Сложность задач: алгоритмическая и полиномиальная невозможность.
7.2 Графы и модели их порождения.
7.3 Визуализация графов.
Классические математики не считали дискретные задачи математикой, т.к. в них решение может в принципе быть найдено перебором. Однако постепенно пришло понимание, что математические задачи возникают, если учитывать неизбежные ограничения на скорость вычислений, объем памяти и другие характеристики сложности алгоритма. Типичная задача: сформулировать алгоритм последовательного перебора всех подмножеств данного конечного множества, не используя конструкцию вложенных циклов.
7.1 Сложность задач: алгоритмическая и полиномиальная невозможность.
Если класс задач слишком широк, то единого алгоритма не существует (Канторовский диагональный процесс – алгоритм, перерабатывающий себя, а в конечном пространстве – он сводится к перебору (почти) всех подмножеств (их число экспоненциально). Типичный пример – задача о нулях произвольной булевой функции. Выход:
(а) сужение класса – обычно трудно, надо понимать специфику задач и ввести соответствующие ограничения;
(б) аппроксимационное или эвристическое решение;
(в) новые подходы на основе случайных элементов и агрегирования решений.
7.2 Графы и модели их порождения.
До недавнего времени графы, введенные как научный объект Леонардом Эйлером (1707-1783), Кёнигсбергские мосты, связь элементов многогранника, – в том числе в результате 20 лет проведенных в Пруссии, были чисто математическим объектом с чисто математическими или инженерными задачами вокруг них. В настоящее время они становятся инструментом анализа социальных сетей в глобальном масштабе.
В применении к социальным явлениям, нормальное распределение не является очень распространенным. Степенное распределение (power law) значительно чаще. Например, степени инциденций вершин в социальных сетях (интернет – число ссылок на интернет-страницу, число страниц на веб-сайте, количество посещений, а также такие характеристики как цитируемость или количество телефонных звонков) распределены степенным образом. Если бы были случайны – то должны бы по Пуассону.
Степенной закон впервые возник в работе Лозаннского экономиста итальянского инженера Вильфредо Парето, который построил функцию распределения итальянских семей по доходу (1897). Закон Парето утверждает, что доля семей с доходом, превышающим x.обратно пропорциональна степени x:
P[X > x]~ x--k.
Он еще формулировал это как закон 80-20: 20% населения обладают 80% богатства. Или торговцы говорят – 80% дохода идет от 20% покупателей. Мне больше всего нравится формулировка польского математика Стефана Банаха, подчеркивающая системный характер этого распределения: «В математике, 5% математиков производят 95% всей математики, но они не произвели бы и 5% математики, если бы не было остальных 95% математиков».
| Fig. 1a Linear scale plot of the distribution of users among web sites | Fig. 1b Log-log scale plot of the distribution of users among web sites |
На Фигуре 1 изображен пример из работы http://www.hpl.hp.com/research/idl/papers/ranking/ranking.html,
показывающий распределение чисел пользователей сети АОЛ в декабре 1997 относительно ранга сайтов по популярности.
Другой способ выразить степенной закон был предложен в работе Гарвардского профессора Джорджа Зипфа, который упорядочил 100 наиболее частых слов по убыванию частоты встречаемости, которую он называл размером (size). Оказалось, что «размер» y обратно пропорционален его рангу r в последовательности:y ~ r-b, где b примерно равно единице (1951). В результате математического анализа обнаружилось, что эта и предыдущая формулировки связаны напрямую. Ключ к доказательству эквивалентности: высказывание «В городе с номером r в упорядочении городов по убыванию населения живет n человек» эквивалентно высказыванию "r городов имеют не менее n жителей".
Фигура 2 изображает график рангов популярности сайтов (ось абсцисс), сопоставленных с количествами посетителей – Зипф работает! Правда, с отклонениями, которые еще нужно объяснить.
| Fig. 2 Sites rank ordered by their popularity |
Наиболее популярный механизм порождения степенного распределения – предпочтительное присоединение (preferential attachment – “rich gets richer” effect), впервые рассмотренный в работе Удны Юла (Yule 1925) для объяснения распределения числа видов в таксонах растений. Следующие имена: Simon 1955, разработавший модель для объяснения размеров городов, Price 1976, для объяснения распределений цитируемости (в частности ввел понятие scale-free network) и Barabбsi and Albert 1999 , для анализа интернет сети (они-то и ввели термин "preferential attachment" ).
Социолог Роберт Мертон (1976) предложил называть это явление эффектом Матфея: "Ибо кто имеет, тому дано будет и приумножится; а кто не имеет, у того отнимется и то, что имеет." (Матфей, 13:12). Предпочтительное присоединение не включает часть, относящуюся к изъятию. Урновый процесс, включающий оба механизма, скорее ведет к логнормальному распределению.
При ближайшем рассмотрении оказывается, что реальные социальные сети характеризуются двумя особенностями: (а) короткое в среднем кратчайшее расстояние между вершинами (феномен степеней Эрдеша или Кевина Бекона) и (б) высокая степень кластерности (для данной вершины – отношение числа связей между ее соседями к масимально возможному) - small world phenomenon.
Watts and Strogatz 1998 предложили простую модель для этого явления – сеть вершин окружности, соединенных со всеми своими соседями до r, в которой малая часть соединений случайно произвольно пересоединена, но эта модель слишком упрощена. Ждите новостей!
Возможны и другие модели порождения графов, например, модель организационного управления с линейной и функциональной компонентами.
7.3 Визуализация графов.
Граф – сам по себе визуализация, но – когда вершин больше, чем пикселей – проблема! Очень недавнего времени, в пределах 10 последних лет. Различают следующие стратегии:
Минимизация энергии – сила принимается пропорциональной квадрату связей, и пр.
Спектральный макет – использование собственных векторов матриц, связанных с графом, в качестве координат.
Ортогональный макет: представление вершинами целочисленной решетки с минимизацией занятой площади и пересечений между ребрами.
Симметрический макет – основан на группах симметрии данного графа.
Древовидный макет: обычно для иерархий или онтологий с малым числом перекрестных ссылок.
Ациклический макет, основанный на представлении графа как потока связей от источника к стоку.
Вопрос в том, чего хотеть от визуализации – ясно, быстрого и понятного обозрения графа. «Понятный» здесь – еще много работы по уточнению.
История:
Сначала – многоуровневый подход (зуминг). Основные подходы связаны с представлением на плоскости – многомерное шкалирование и собственные вектора. В последнее время – модификации, связанные с учетом локальной структуру связностей. Я бы предложил вернуться к графам и зумингу, но осмысленно, так чтобы подграфы действительно соответствовали каким-то подструктурам в графе – мне кажется, что у меня есть определенный подход, с которым можно надеяться на успех. Этот подход состоит в том, чтобы представить граф с большим числом вершин через граф с малым числом вершин так, чтобы вершины малого графа отвечали множествам вершин большого графа, а наличие дуги в малом графе соответствовало бы очень большому количеству дуг большого графа и отсутствие дуги – очень малому. В отличие от классического кластер-анализа, где надо разбить множество вершин большого графа на сравнительно мало связанные куски, здесь надо так разбить, чтобы все или почти все дуги большого графа оказались соединяющими одни и те же группы (задача о выявлении подсистем и их связей).
Фигура 3. Типичные структуры больших графов: линейная и циклическая.
8 Вычислительная техника и программирование
8.1 Эволюция вычислительной техники и системы будущего
Эволюция:
1623 – механический калькулятор, W.Schickard
1801 – перфокарты для ткацких станков (воспроизводимая структура ткани), J.-M. Jackard
1833 – проект аналитического мотора с памятью, перфокартами и программируемой частью (A. Lovelace), C. Babbage, UK
1890 – табулирующие машины с перфокартами, H. Hollerith (futureIBM), US
1927 – аналоговая машина, дифференцирующий анализатор, H. NiemanandV. Bush, US
1937 – вычислительная реле схема G. StibitzUS (используя магистерский диплом C. Shannon)
1939 – решатель линейных уравнений, использующий продвинутую архитектуру диодов и емкостей, J. AtanasoffandC. Berry, US
1941 – первый в мире компютер на бинарных элементах с числами с плавающей запятой и программой запоминаемой в памяти (так называемая архитектура Фон-Неймана), K. Zuse, Germany
1943 – первый электронный компютер, хотя и не унивесальный, Колосс, M. NewmanandT. Flowers, UK
1944 – Марк 1, основанный на идеях Баббаджа, но не вполне универсальный, H. Aiken, USA
1945 – ENIAC(Electronic Numerical Integrator and Computer), первый настоящий компютер, но без перфокарт – программу надо было сформировать руками в памяти, J. Mauchly, J. Eckert, USA
1950 – первая советская машина МЭСМ, С.А. Лебедев, Киев, Украина, СССР
1953 – БЭСМ, продвинутая и конкурентоспособная машина, С.А. Лебедев, Москва, СССР
1954 – УРАЛ, одноадресная малая машина, Б.И. Рамеев (без высшего образования как сын врага народа), Пенза, СССР
1964 – Наири, малая машина с параллельным считыванием разрядов и троичной системой счисления, Г. Овсепян, Армения, СССР
1974 – начало эксплуатации машин Единой Серии, копий серийных машин IBM на отечественной базе (переход объясняется необходимостью серийного производства компютеров)
Поколения
1 поколение – ламповые (диод, триод, пентод) машины
II поколение – транзисторы (вместо ламп)
III поколение – микрочипы (логические функции вместо операций)
И так далее – каждый месяц какая-нибудь новинка
Цель международного сообщества - создать вычислительную среду по типу водопровода – уже довольно близка! Более того, получается не просто вычислительная, а информационная среда.
Современные типы компютеров:
Мэйнфрэйм – огромные компютеры с высокой скоростью, надежностью, безопасностью, интеграцией с устарелыми программными системами, типично поставляемые фирмой ИБМ (основные пользователи языка COBOL, давно устаревшего)
Суперкомпютер – отличается требованиями к внутренним вычислениям, уступая мэйнфрэйму в обработке внешних данных (по входу и по выходу)
Кластер – система компютеров, которые могут использоваться совместно в зависимости от архитектуры кластера (Беовульф, Грид и пр.), либо для обеспечения дополнительных мощностей, либо для параллелизации вычислений (ставит новые задачи перед вычислительной математикой такие, как параллелизация обращения матриц)
Сервер – компютер, ориентированный на серверные применения – помощь другим программам.
Server-oriented operating systems tend to have certain features in common that make them more suitable for the server environment, such as
an optional or absent GUI,
ability to reconfigure both hardware and software to some extent without restart,
advanced backup facilities to permit online backups of critical data at regular and frequent intervals,
transparent data transfer between different volumes or devices,
flexible and advanced networking capabilities,
automation capabilities like daemons in UNIX and services in Windows, and
tight system security, with advanced user, resource, data, and memory protection.
Персональный компютер
Уорк- станция – персональный компютер, специализированный для какого-либо типа применений, например, качественной графики
Ноутбук
Планшет (?)
8.2. Информационные протоколы и безопасность.
Создание интернета не только преобразует нашу цивилизацию как глобальное теперь в подлинном смысле этого слова – сообщество. Сложные многоуровневые пакеты, посылаемые по различным протоколам, преобразовали науку о компютерах опять в инженерию. (IP (Internet Protocol) – Протокол Интернета и TCP (Transmission Control Protocol) – Протокол передачи пакета).
С веб-сайта http://lemoi-www.dvgu.ru/lect/protoc/tcpip/indextcp/indextcp.htm:
«Причина, по которой TCP/IP столь важен сегодня, заключается в том, что он позволяет самостоятельным сетям подключаться к Internet или объединяться для создания частных интрасетей. Вычислительные сети, составляющие интрасеть, физически подключаются через устройства, называемые маршрутизаторами или IP-маршрутизаторами. Маршрутизатор - это компьютер, который передает пакеты данных из одной сети в другую. В интрасети, работающей на основе TCP/IP, информация передается в виде дискретных блоков, называемых IP-пакетами (IP packets) или IP-дейтаграммами (IP datagrams). Благодаря программному обеспечению TCP/IP все компьютеры, подключенные к вычислительной сети, становятся "близкими родственниками". По существу оно скрывает маршрутизаторы и базовую архитектуру сетей и делает так, что все это выглядит как одна большая сеть. Точно так же, как подключения к сети Ethernet распознаются по 48-разрядным идентификаторам Ethernet, подключения к интрасети идентифицируются 32-разрядными IP-адресами, которые мы выражаем в форме десятичных чисел, разделенных точками (например, 128.10.2.3). Взяв IP-адрес удаленного компьютера, компьютер в интрасети или в Internet может отправить данные на него, как будто они составляют часть одной и той же физической сети.
TCP/IP дает решение проблемы данными между двумя компьютерами, подключенными к одной и той же интрасети, но принадлежащими различным физическим сетям. Решение состоит из нескольких частей, причем каждый член семейства протоколов TCP/IP вносит свою лепту в общее дело. IP - самый фундаментальный протокол из комплекта TCP/IP - передает IP-дейтаграммы по интрасети и выполняет важную функцию, называемую маршрутизацией, по сути дела это выбор маршрута, по которому дейтаграмма будет следовать из пункта А в пункт B, и использование маршрутизаторов для "прыжков" между сетями.
TCP - это протокол более высокого уровня, который позволяет прикладным программам, запущенным на различных главных компьютерах сети, обмениваться потоками данных. TCP делит потоки данных на цепочки, которые называются TCP-сегментами, и передает их с помощью IP. В большинстве случаев каждый TCP-сегмент пересылается в одной IP-дейтаграмме. Однако при необходимости TCP будет расщеплять сегменты на несколько IP-дейтаграмм, вмещающихся в физические кадры данных, которые используют для передачи информации между компьютерами в сети. Поскольку IP не гарантирует, что дейтаграммы будут получены в той же самой последовательности, в которой они были посланы, TCP осуществляет повторную "сборку" TCP-сегментов на другом конце маршрута, чтобы образовать непрерывный поток данных. FTP и telnet - это два примера популярных прикладных программ TCP/IP, которые опираются на использование TCP.
Другой важный член комплекта TCP/IP - User Datagram Protocol (UDP, протокол пользовательских дейтаграмм), который похож на TCP, но более примитивен. TCP - "надежный" протокол, потому что он обеспечивает проверку на наличие ошибок и обмен подтверждающими сообщениями чтобы данные достигали своего места назначения заведомо без искажений. UDP - "ненадежный" протокол, ибо не гарантирует, что дейтаграммы будут приходить в том порядке, в котором были посланы, и даже того, что они придут вообще.
Другие TCP/IP протоколы играют менее заметные, но в равной степени важные роли в работе сетей TCP/IP. Например, протокол определения адресов (Address Resolution Protocol, ARP) преобразует IP-адреса в физические сетевые адреса, такие, как идентификаторы Ethernet. Родственный протокол - протокол обратного преобразования адресов (Reverse Address Resolution Protocol, RARP) - выполняет обратное действие, преобразуя физические сетевые адреса в IP-адреса. Протокол управления сообщениями Internet (Internet Control Message Protocol, ICMP) представляет собой протокол сопровождения, который использует IP для обмена управляющей информацией и контроля над ошибками, относящимися к передаче пакетов IP. Например, если маршрутизатор не может передать IP-дейтаграмму, он использует ICMP, с тем чтобы информировать отправителя, что возникла проблема.»
Атаковать такие пакеты можно на самом разном уровне.
8.3 Эволюция данных и задач их анализа: текст, сигнал, изображение.
Первые машины: никаких данных, кроме коэффициентов – параметров программ, не предусматривали.
Затем – для статистических задач - данные табличного вида, для задач хранения и модификации данных – базы данных. Эти два подхода были интегрированы совсем недавно в концепциях разработки данных (datamining).
В настоящее время – переход к данным вида текстов, сигналов и изображений и адаптация или разработка новых подходов к возникающим задачам. Например, в задачах обработки изображений – узнать лицо – узнать лицо в толпе; показать, кто говорит в данное время; определить, кто где в движущейся толпе, и пр. На мой взгляд, нет необходимости в новых вычислительных идеях – просто комбинируй известные, на ближайшиегоды должно хватить.
8.4 Новые подходы к вычислениям; параллельные и квантовые вычисления.
Параллельные вычисления – вычисления, ведущиеся на многих машинах одновременно. Для некоторых задач это ничего принципиально нового не вносит – например, задача о вычислении среднего. Другие же задачи, как, например, вычисление медианы, могут существенно от этого зависеть (или медиана медиан и есть медиана?); но уж точно, обращение матрицы и связанные задачи – спектральный анализ, например, нуждаются в разработке соответствующих модификаций, в значительной степени зависящих от конфигурации связей между компютерами. Эти задачи получили новый импульс в связи с задачами о вычислениях на географически распределенных мобильных устройствах с небольшой памятью.
Квантовые вычисления: не биты,а кюбиты, т.е. векторы (a,b) с a соответствующим состоянию 0, b – состоянию 1, так что |a|2+|b|2=1.Алгоритм Deutsch-Jozsa решает NP-полную задачу различения между постоянной и сбалансированной булевыми функциями за один шаг. Некоторые считают, что они со временем так же решат остальные NP-полные задачи.
8.5 Эволюция языков программирования.
Алгоритмические языки – инструкций; декларативные языки; функциональные языки; сейчас наиболее популярны объектно-ориентированные языки – начатые С++ и Джава Гослинга. Я думаю, потому что они включают иерархию явлений, то как мы думаем о том, как устроены предметы. Например, тело животного включает голову, конечности, тело, и т.д. Голова включает рот, нос, глаза, и т.д. Глаза включают… Как говорил павший классик, электрон так же неисчерпаем, как и атом.
Странно, что специалисты по программированию отмечают совсем другие свойства объектно-ориентированных языков как характерные (базовые библиотеки и пр.)
Критика: Эти языки совсем не ориентированы на передачу отношений между разными аспектами явления и не очень хорошо ориентированы на отношения между классами. Это стало особенно чувствоваться в самое последнее время в связи, например, с необходимостью присваивания разных уровней доступа различным пользователям для различных задач.
Какие еще типы языков вы знаете? Согласно одному профессиональному сайту,
Описания интерфейсов Прототипные Объектно-ориентированные Рефлексивные Языки логического программирования Языки параллельного программирования Сценарные, или скриптовые Эзотерические
Функциональные Императивные Процедурные Языки векторного программирования Аспектно-ориентированные Декларативные Языки динамического программирования Учебные
Немного напоминает классификацию животных из рассказа-эссе «Аналитический язык Джона Уилкинса» Хорхе Луис Борхеса: согласно «некой китайской энциклопедии» под названием «Небесная империя благодетельных знаний», животные делятся на:
принадлежащих Императору,
набальзамированных,
прирученных,
молочных поросят,
сирен,
сказочных,
бродячих собак,
включённых в эту классификацию,
бегающих как сумасшедшие,
бесчисленных,
нарисованных тончайшей кистью из верблюжьей шерсти,
прочих,
разбивших цветочную вазу,
похожих издали на мух.
9 Развитие баз данных и знаний
9.1 Эволюция баз данных и систем управления.
9.2. Хранилища данных
9.3. Распределенные системы и электронные коллективы.
База данных – это собрание данных, организованное таким образом, чтобы данные было легко найти, изменить, и манипулировать. Непрофессионалы классифицируют базы данных по содержанию – библиотечные базы данных, текстовые базы данных, изображения, и пр.
В информатике, главное основание – организация данных. Где-то к 80-м программисты пришли к понятию реляционной базы и модели данных, которые стали стандартом.
Реляционная модель данных:
- Структурный аспект — данные в базе данных представляют собой набор отношений, то что в анализе данных называется таблица объект-аттрибут.
- Аспект целостности — отношения (таблицы) отвечают определенным условиям целостности уровня домена (типа данных), уровня отношения и уровня базы данных.
- Аспект манипулирования — реляционная алгебра: объединение, пересечение, разность и декартово произведение, а также селекция, проекция, соединение и деление (Кодд, 1970)
Кроме того, в состав реляционной модели данных обычно включают теорию нормализации.
Следует отметить, что
модель является логической, а не физической – все информационное наполнение базы данных представлено одним и только одним способом, а именно — явным заданием значений атрибутов в кортежах отношений; в частности, нет никаких указателей (адресов), связывающих одно значение с другим;
наличие реляционной алгебры позволяет реализовать декларативное программирование («что сделать», а не «как сделать» в процедурных языках) и декларативное описаний ограничений целостности, в дополнение к навигационному (процедурному) программированию и процедурной проверке условий.
Взаимосвязь таблиц является важнейшим элементом реляционной модели данных. Она поддерживается внешними ключами (foreign key). Рассмотрим пример, в котором база данных хранит информацию о рядовых сотрудниках (таблица Сотрудник) и руководителях (таблица Руководитель) в некоторой организации (рис.2). Первичный ключ таблицы Руководитель - столбец Номер (например, табельный номер). Столбец Фамилия не может выполнять роль первичного ключа, так как в одной организации могут работать два руководителя с одинаковыми фамилиями. Любой сотрудник подчинен единственному руководителю, что должно быть отражено в базе данных. Таблица Сотрудник содержит столбец Номер руководителя, и значения в этом столбце выбираются из столбца Номер таблицы Руководитель (см. рис.2). Столбец Номер Руководителя является внешним ключом в таблице Сотрудник.
Особенностью настоящего этапа является то, что реляционные базы данных принимают для пользователя вид базы данных для объектно-ориентированного программирования (аn object-oriented programming database), конгруэнтной со структурой данных в классах и подклассах программного обеспечения конкретной системы. Другой популярный вид баз данных – распределенные базы данных, которые рассредоточены в разных точках компютерной сети.
Базы данных содержат коллекции данных о тоговых транзакциях, каталогах продукции и складов, профили потребителей и пр. Они позволяют пользователю считывать и записывать данные, специфицировать формат отчетных таблиц и анализировать движение данных. Типично, их хранят в мэйнфреймах, созданные и поддерживаемые на допотопных языковых средствах, так что основная задача программистов, обслуживающих подобные системы, скажем, в каком-нибудь огромном международном банке, поддерживать возможности системы для постоянно обновляемых физических способов доставки информации – новые считывающие устройства, новые стандарты компьютерных спредшитов, и пр. Основные форматы баз данных - IBM's DB2, Microsoft's Access, Oracle, Sybase, and Computer Associates.
SQL (ˈɛsˈkjuˈɛl или ˈsiːkwəl) (англ. Structured Query Language — язык структурированных запросов) — универсальный компьютерный язык, применяемый для создания, модификации и управления данными в реляционных базах данных.
Язык SQL делится на три части:
операторы определения данных (англ. Data Definition Language, DDL)
операторы манипуляции данными (англ. Data Manipulation Language, DML)
операторы определения доступа к данным (англ. Data Control Language, DCL)
Типичный запрос (к базе данных Склад):
SELECT Название, Количество, Материал
FROM Деталь
WHERE Номер = "Т145-А8";
{ВЫБРАТЬ Название, Количество, Материал
ИЗ Деталь
ГДЕ Номер = "Т145-А8"}
Типичные команды:
| SELECT | Выбрать данные из базы данных | ВЫБРАТЬ |
| INSERT | Добавить данные в базу данных | ВКЛЮЧИТЬ |
| UPDATE | Обновить данные в базе данных | ОБНОВИТЬ |
| DELETE | Удалить данные из базы данных | УДАЛИТЬ |
| GRANT | Предоставить привилегии пользователю | РАЗРЕШИТЬ |
| REVOKE | Отменить привилегии пользователя | ОТМЕНИТЬ |
| COMMIT | Зафиксировать текущую транзакцию | ЗАФИКСИРОВАТЬ |
| ROLLBACK | Прервать текущую транзакцию | ПРЕРВАТЬ |
В начале 1970-х годов в одной из исследовательских лабораторий компании IBM была разработана экспериментальная реляционная СУБД System R (англ.), для которой затем был создан специальный язык SEQUEL, позволявший относительно просто управлять данными в этой СУБД. Аббревиатура SEQUEL расшифровывалась как англ. Structured English QUEry Language — «структурированный английский язык запросов». Позже по юридическим соображениям язык SEQUEL был переименован в SQL. Когда в 1986 году первый стандарт языка SQL был принят ANSI (American National Standards Institute), официальным произношением стало [,es kju:' el] — эс-кью-эл. Несмотря на это, даже англоязычные специалисты по прежнему часто называют SQL сиквел, вместо эс-кью-эл (по-русски также часто говорят «эс-ку-эль»).
Целью разработки было создание простого непроцедурного языка, которым мог воспользоваться любой пользователь, даже не имеющий навыков программирования. Собственно разработкой языка запросов занимались Дональд Чэмбэрлин (Donald D. Chamberlin) и Рэй Бойс (Ray Boyce). Пэт Селинджер (Pat Selinger) занималась разработкой стоимостного оптимизатора (англ. cost-based optimizer), Рэймонд Лори (Raymond Lorie) занимался компилятором запросов.
Первыми СУБД, поддерживающими новый язык, стали в 1979 году Oracle V2 для машин VAX от компании Relational Software Inc. (впоследствии ставшей компанией Oracle) и System/38 от IBM, основанная на System/R.
Первый официальный стандарт языка SQL был принят ANSI в 1986 и ISO (Международной организацией по стандартизации) в 1987 (так называемый SQL-86) и несколько уточнён в 1989 году. Дальнейшее развитие языка поставщиками СУБД потребовало принятия в 1992 г. нового расширенного стандарта (ANSI SQL-92 или просто SQL2). Следующим стандартом стал SQL:1999 (SQL3). В настоящее время действует стандарт, принятый в 2003 году (SQL:2003) с небольшими модификациями, внесёнными позже.Создатель реляционной модели данных Эдгар Кодд, Кристофер Дейт и их сторонники указывают на то, что SQL не является истинно реляционным языком. В частности они указывают на следующие проблемы SQL:
Повторяющиеся строки
Неопределённые значения (nulls)
Явное указание порядка колонок слева направо
Колонки без имени и дублирующиеся имена колонок
Использование указателей
Высокая избыточность
Хотя SQL и задумывался, как средство работы конечного пользователя, в конце концов он стал настолько сложным, что превратился в инструмент программиста.
Ранее SQL не предлагал стандартного способа манипуляции древовидными структурами. Некоторые поставщики СУБД предлагали свои решения. Например, Oracle использует выражение CONNECT BY. В настоящее время в качестве стандарта принята рекурсивная конструкция WITH.
SQL - язык запросов, а не универсальный алгоритмический язык. На нем нельзя написать сколько-нибудь сложную прикладную программу, которая работает с базой данных. Для этой цели в современных СУБД используется язык четвертого поколения (Forth Generation Language - 4GL), обладающий как основными возможностями процедурных языков третьего поколения (3GL), таких как СИ, Паскаль, Ада, так и возможностью встроить в текст программы операторы SQL, и средствами управления интерфейсом пользователя (меню, формами, вводом пользователя и т.д.).
Пример системы баз данных, разработанных в Национальном Центре Био-технологической Информации, пожалуй, самый продвинутый в мире среди общедоступных средств:
Состав системы баз
Пример взаимосвязанности: связи базы данных ГЕН
Список возможных запросов в базе данных ГЕН
9.2. Хранилища данных
Хранилище данных (Data warehouse) = собрание всех данных в электронной форме в данной организации.
Такое объединение позволяет руководству заниматься интегральными задачами по доступу, извлечению, преобразованию и анализу данных, включая словарь. В анализ данных часто включают интеллектуальные инструменты бизнеса, включая средства манипулирования метаданными, т.е. названиями атрибутов и отношений.
Два основных – не совсем взаимоисключающих - подхода к организации данных в хранилище – размерностный (dimensional) и нормализованный (normalized).
В размерностном подходе, данные делятся на «факты» (числовые данные о транзакциях) и «параметры» (контекст). Например, данные о конкретной продаже можно разделить на факты – число заказанных изделий и цены, и параметры – дата заказа, имя потребителя, адреса доставки и платежа, сотрудник, организовавший продажу, и пр. Преимущество – удобство использования. Недостатки – сложность организации взаимодействия разных баз, типично, в разных компютерах; трудность реорганизации при изменении бизнес-модели.
При нормализованном подходе используются правила нормализации реляционных данных. Данные сгруппированы по предметным областям – потребители, финансы, продукты и пр. Преимущество – легко манипулировать с данными – добавлять, менять и пр. Недостатки: из-за многочисленности таблиц трудно формировать сводные таблицы; для доступа к информации необходимо точно знать, где что находится.
9.3. Распределенные системы и электронные коллективы.
Распределенные системы полезны в ситуациях, когда пользователи в разных местах интересуются, в основном, локальной информацией, как например, расписание транспорта или банковские клиенты.
Преимущество – быстрый доступ к локальной информации. Проблема – поддержка целостности. Обычно – за счет так называемой двухступенчатой привязки (two-phase commit). Первый этап - запись, которую предлагается модифицировать, запирается во всех вершинах сети. По получении подтверждения от всех вершин, второй этап – модификация. Недостаток – когда много вершин, велика вероятность невозможности операции. В случаях, когда это важно, используют так называемые реплики – все базы – точные копии друг друга, и изменение делается в одной базе только с тем, чтобы провести его, скажем, раз в сутки, когда все спят.
10. Машинный интеллект
10.1 Адаптация: эволюция алгоритма - эволюция популяций - система взаимодействующих агентов.
10.2 Изменение формата данных: Размытые и грубые множества.
10.3. Классификация и вывод.
10.4. Принятие решений и планирование.
10.1 От эволюции популяций к системам взаимодействующих агентов.
Агенты – смесь деловых игр и децентрализованных моделей поведения. И то, и другое развивалось в СССР в 70-80 – не на Западе, но там не пригодилось, как почти все остальное.
10.2 Размытые и грубые множества.
Размытые множества введены Л. Заде в 60-е годы прошлого века. В отличие от твердых множеств, функция принадлежности может быть любым числом от 0 до 1, что сближает их с вероятностями, но позволяет значительно больше интерпретаций – и операций. В частности, рассматривают аналоги теоретико-множественных операций объединения, пересечения и дополнения. Такие множества могут количественно моделировать нечеткие языковые понятия как «молодой», «отличный» и пр., в том числе использоваться в количественных соотношениях. В частности, удачно работают «размытые регуляторы», основанные на представлении каждого показателя тремя размытыми множествами «высокое значение», «среднее значение», «малое значение», поскольку такое деление часто имеет физический смысл и освобождает от конкретных измерительных нюансов распределения.
Грубые множества введены в 1991 в монографии Зенона Павляка (Польша). Они имеют значительно более узкую область применимости, относясь, скорее к свойствам категорий, определенных на объектах.
Пример:
| Условная таблица данных | |||||
| Object | P1 | P2 | P3 | P4 | P5 |
| O1 | 1 | 2 | 0 | 1 | 1 |
| O2 | 1 | 2 | 0 | 1 | 1 |
| O3 | 2 | 0 | 0 | 1 | 0 |
| O4 | 0 | 0 | 1 | 2 | 1 |
| O5 | 2 | 1 | 0 | 2 | 1 |
| O6 | 0 | 0 | 1 | 2 | 2 |
| O7 | 2 | 0 | 0 | 1 | 0 |
| O8 | 0 | 1 | 2 | 2 | 1 |
| O9 | 2 | 1 | 0 | 2 | 2 |
| O10 | 2 | 0 | 0 | 1 | 0 |
Любое множество подмножество признаков P разбивает множество объектов на классы эквивалентности [x]P, состоящие из объектов, одинаковых на этом подмножестве. Например, для множества всех пяти признаков имеется 7 классов эквивалентности:
Для множества, состоящего из одного признака P1, разбиение имеет вид:
Всякому подмножеству объектов X всякое множество признаков P сопоставляет его нижнюю и верхнюю аппроксимации. Нижняя аппроксимация состоит из таких элементов из X, чьи [x]P классы целиком содержатся в Х. Верхняя аппроксимация состоит из таких элементов из X, чьи [x]P классы пересекаются с Х.
Пусть, например, X = {O1,O2,O3,O4}, и P = {P1,P2,P3,P4,P5}, все признаки.
Нижняя аппроксимация , верхняя аппроксимация - то, что можно сказать об Х по информации только о значениях признаков. Эта пара и образует грубое множество.
Понятие грубого множества полезно для выбора значимых множеств признаков и определения значимых связей между признаками.
11. Перспективы
11.1 Перспективные приложения.
11.2 Моделирование решений.
11.3 Моделирование знаний с наличием противоречий.
11.4 Моделирование понимания.
Использованная литература
1. Блехман И.И., Мышкис А.Д., Пановко, Я.Г. Прикладная математика: предмет, логика, особенности подходов. - М.: Издательство ЛКИ, 2007. - 376 с.
2. Кун Т., Структура научных революций, М., Прогресс, 1977. – 300 с.
3. Тутубалин В.Н. Границы применимости: вероятностно-статистические методы и их возможности, М.: Знание, 1977. – 64 с.
4. Уемов А.И. Аналогия в практике научного исследования. Из истории физико-математических наук, М.: Наука, 1970. – 264 с.
5. The history of computing: Web resource in Virginia Technology University, 2002, ei.cs.vt.edu/~history/.
6. Michelle A. Hoyle, The history of computing science, 2006, website http:// www.eingang.org/ Lecture/toc.html.
7. O’Regan Gerard, A Brief History of Computing, Springer, 2008.- 252 p.
8. Плошко Б.Г., Елисеева И.И. История статистики. – М: Финансы и статистика, 1990.
9. Манин Ю.И. Математика как метафора. – М.: МЦНМО, 2008.
10. Пуанкаре А. О науке. – М.: Наука, 1983.
11. U.M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, R. Uthurusamy, Advances in Knowledge Discovery and Data Mining, AAAI Press, 1996.
12. P. Buitelaar, P. Cimiano, B. Magnini, Eds., Ontology Learning from Text: Methods, Evaluation and Applications, IOS Press, 2005.
13. Бочаров В.А., Маркин В.И. Основы логики. - М.: ИНФРА-М, 1997. - 296 с.
14. Mirkin, B. Mathematical classification and clustering, - Dorderecht: Kluwer, 1996.- 448 p.
15. Mirkin, B. Core concepts in data analysis: summarization, correlation,visualization, Springer, 2011, 390 p.
16. Small world phenomenon, website: en.wikipedia.org/wiki/Small_world_phenomenon, 2008.
17. Good P.I. Resampling methods, - Birkhдuser Boston, 2005, 218 p.
18. Салий В.Н. Математические основы гуманитарных знаний. – Саратов: Изд-во СГУ, 2006.
19. Тутубалин В.Н. Теория вероятностей. М.: МГУ, 1972.
20. Клейн Ф. Элементарная математика с точки зрения высшей, тт. 1, 2. – М.: Наука, 1987 (изд. 4-е).
50