2011 Борис Григорьевич Миркин Профессор, Кафедра анализа данных и искусственного интеллекта опми ниу вшэ, Москва, РФ (стр. 9 из 13)
Интересное = необычное, очень редкое или аномальное. Смерть от огурцов логически правильна, но не интересна. Много методов выявления, описания и формирования аномальных паттернов.
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. Типичные структуры больших графов: линейная и циклическая.