Когнитивные сети

Размещено на http://www.allbest.ru/

19

Размещено на http://www.allbest.ru/

Введение

сеть программа граф

В 1999 году Альберт-Ласло Барабаши математически описал новый тип сетей, названный безмасштабные сети (scale-free networks), и высказал предположение, что развитие таких сетей лежит в основе процессов самоорганизации сложных нелинейных систем. И вот спустя 12 лет математическое описание свойств этих сетей претендует на то, чтобы стать открытием XXI века.

Безмасштабные сети можно изобразить в виде графа, в котором степени вершин (число примыкающих к вершине ребер) распределены по степенному закону. То есть график, у которого по одной оси отложено число связей, приходящихся на X узлов, а по другой - число узлов с количеством связей Х, - это степенная функция.

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

1. Анализ области применения

1.1 Определение когнитивной сети

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

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

В коллективной работе авторов из университета штата Вирджиния, США сформированы требования к когнитивной сети, где она призвана обеспечить в заданный промежуток времени, лучшую непрерывную производительность, чем не когнитивная сеть. Когнитивность (познание) должно использоваться для того, чтобы улучшить управление ресурсом, качеством сервиса (QoS), безопасностью, управлением доступом и много других сетевых целей. Наиболее актуальными кандидатами для реализации когнитивных сетей авторы считают: специализированные (ad-hoc) сети; беспроводные сети в режиме инфраструктуры; наземные проводные сети и гибридные сети. Идеально, когнитивная сеть должна быть дальновидной и предусмотрительной, а не реактивной, немедленно реагирующей на действия и должна пытаться корректировать проблемы прежде, чем они произойдут.

Когнитивные сети могут быть централизованными или распределенными. Централизованный подход обеспечивает существенную обработку данных, коммуникацию, время и преимущества памяти, но обладают классическими недостатками централизованной архитектуры (например, узкие места производительности и единственные пункты отказа). Распределенные когнитивные сети могут быть сформированы как коллекция когнитивных объектов, которые включают интеллектуальные функциональные возможности, имеют возможности логического вывода, характеризуются автономностью, социальной способностью, обучением из опыта, и адаптивностью, в то время когда они взаимодействуют с другими компонентами и действуют реактивным или проактивным способом для достижения своих целей.

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

1.2 Характеристики когнитивной сети

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

Расстояние между узлами определяется как количество шагов, которые необходимо сделать, чтобы по существующим ребрам добраться от одного узла до другого. Естественно, узлы могут быть соединены прямо или опосредованно, через другие узлы.

Кратчайшим путем (SP, shortest path) между узлами назовем минимальное расстояние между ними. Для всей сети можно ввести понятие среднего кратчайшего пути, как среднее по всем парам узлов минимальное расстояния между ними:

,

где - количество узлов, - кратчайшее расстояние между узлами i и j.

Коэффициент кластеризации характеризует тенденцию к образованию групп взаимосвязанных узлов, так называемых клик (Clique). Для конкретного узла коэффициент кластеризации показывает, сколько ближайших соседей данного узла являются также ближайшими соседями друг для друга.

Пусть из узла выходит k связей, которые соединяют его с k другими узлами, ближайшими соседями. Если предположить, что все ближайшие соседи соединены непосредственно друг с другом, то количество связей между ними составляло бы k(k-1)/2. То есть это число, которое соответствует максимально возможному количеству связей, которыми могли бы соединяться ближайшие соседи выбранного узла.

Коэффициент кластеризации может определяться как для каждого узла, так и для всей сети:

Посредничество (betweenness) - это параметр, показывающий, сколько кратчайших путей проходит через узел. Эта характеристика отражает роль данного узла в установлении связей в сети. Узлы с наибольшим посредничеством играют главную роль в установлении связей между другими узлами в сети. Посредничество b_m узла m определяется по формуле:

где B(i, j) - общее количество кратчайших путей между узлами i и j , B(i,m, j) - количество кратчайших путей между узлами i и j , проходящих через узел m.

Свойство эластичности сетей относится к распределению расстояний между узлами при изъятии отдельных узлов (толерантность к атакам).

Эластичность сети зависит от ее связности, т.е. существовании путей между парами узлов. Если узел будет изъят из сети, типичная длина этих путей увеличится.

2. Анализ способ решения задачи

2.1 Семантическая сеть

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

WordNet -- это электронная семантическая сеть для английского языка, разработанная в Принстонском университете. Словарь состоит из 4 сетей для основных знаменательных частей речи: существительных, глаголов, прилагательных и наречий. Базовой словарной единицей в WordNet является не отдельное слово, а так называемый синонимический ряд («синсеты»), объединяющий слова со схожим значением и по сути своей являющимися узлами сети (см. Рис. 2.1. Структура синсета).

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

Рис. 2.1. Структура синсета.

2.2 Литература и поэзия как сложные сети

Мазуччи и Роджерс построили сеть семантических связей слов в романе Дж.Оруэла «1984» по мере их появления в тексте. Этот роман рассматривался как конечные, направленные сети, в которых слова являются вершинами и две вершины связаны, если они являются соседними. Знаки препинания тоже учитываются в качестве вершин. Сеть состоит из 8992 вершин, представляющих различные слова и 117687 направленных ребер, степень которых < k >= 13.1.

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

Чтобы учесть ритмическую структуру стихотворения и наличие в нем рифмы мы, соответственно, соединяем два ближайших слова связью, если эти слова содержат ударные слоги, а также соединяем связью два слова на концах двух ближайших строк, если у этих слов имеется рифма. Рис. 2.3. показывает образовавшуюся сеть для стихотворения А.С.Пушкина ”Брожу ли я вдоль улиц шумных…”.

Статистические показатели этой сети следующие: L=8.215, C=0.079, г=1.442, r=0.0629.

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

Рис.2.2. Ориентированная сеть первых шестидесяти слов романа Дж.Оруэлла Ѓб1984Ѓв

Рис. 2.3. Мультиграф стихотворении А.С. Пушкина “Брожу ли я вдоль улиц шумных…” с учетом ритмических и рифмических связей между словами.

2.3 Безмасштабные сети музыкальных произведений

Партитура музыкального произведения легко преобразуется в сетевую структуру, если в качестве узлов такой сети взять музыкальные ноты всех возможных длительностей. Нетрудно подсчитать, что число узлов для одного голоса в такой сети не будет превышать 1800. В самом деле, число клавишей у рояля равно 88 и, умножая это число на 20 - число длительностей ноты (половинные, четверти, восьмые и т.д.), получаем 1760. Связи между узлами (нотами) в сети устанавливаются по хронологическому принципу: если нота I начинает звучать в момент времени T , а нота J в этот момент заканчивает свое звучание, то между соответствующими узлами сети имеет место связь.

Ли (Xiaofan Liu), Тсе (Chi K. Tse) и Смол (Michael Small) из политехнического университета Гонконга проанализировали статистические свойства сетей, построенных по описанному выше принципу, для произведений Баха, Моцарта, Шопена и современных китайских композитов, работающих в жанре поп музыки. Все эти сети оказались безмасштабными. Среднее число шагов между узлами в этих сетях варьируют в диапазоне от 2.8 до 4.2. Другие параметры сетей также изменялись довольно значительно для различных произведений.

Партитуры, или даже исполнение конкретного музыканта может быть представлено в виде MIDI (Musical Instrument Digital Interface) файла. MIDI-файл кодирует музыкальные композиции серии событий, где каждое событие включает в себя информацию, описывающую, как высоту и длительность ноты. С помощью этой информации можно построить сложную сеть. Каждое MIDI-событие (одна музыкальная нота) соответствует узлу сетевого комплекса. Узлы сети соединены ребрами, если они следуют друг за другом в музыкальной партитуре. Вес приписывается данному краю на основе относительной частоты, с которой две вершины соединены.

Рис. 2.4. Секция сонаты Моцарта

Рис.2. 5. Сгенерированная сеть секции сонаты Моцарта

2.4 О сетевой структуре некоторых произведений кубизма

При случайном разбиении плоскости на непересекающиеся смежные блоки, можно построить безмасштабную сеть, в которой узлами будут сами блоки, а связями - общая граница между блоками. В живописи кубистов (Пикассо, Брак, Мондриан и др.) такими блоками чаще всего являются треугольники, квадраты и прямоугольники, но можно найти и другие геометрические и негеометрические формы. На Рис. 2. 6 представлена картина П.Пикассо «Портрет» и ее сетевая модель.

Закон распределения узлов по числу связей можно записать в виде: P ~ q-2.43, коэффициент кластеризации С=0.343, среднее межузловое расстояние 4.53

Рассмотрим одну из картин голландского художника-кубиста Пита Мондриана (1892-1944).

Распределение узлов по степеням для сети этой картины подчиняется степенному закону, показатель степени для сети этой картины равен г ? 3.2. Коэффициент кластеризации этой сети C ? 0.2, а среднее межузловое расстояние ‹l› ? 3.2 .

Картина русского художника Казимира Малевича (1878-1935) “Лесоруб” принадлежащая к живописному стилю “кубофутуризм”, также легко разбивается на непересекающиеся блоки.

Соответствующая сетевая структура также является безмасштабной сетью г ? 1.94, коэффициентом кластеризации C ? 0.37 , и ‹l› ? 4.1.

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

Рис.2.6. Портрет П.Пикассо и его сетевая структура.

Рис. 2.7. Пит Мондриан. Композиция.

Рис. 2.8. К.Малевич. Дровосек.

3. Разработка программной модели

3.1 Обзор программ для визуализации графов

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

Рисовать графы, пользуясь графическими редакторами широкого профиля, не всегда удобно. Гораздо эффективнее воспользоваться специализированными приложениями. Одной из подобных специализированных программ является uDraw (Graph), автоматизирующая процесс построения графов и диаграмм (рис. 3.1). Весьма удобной функцией программы является возможность деформирования графа, когда при перемещении одной из вершин графа все остальные деформируются автоматически. Поэтому если нужно выделить место под новые вершины, то вам не придется заново перерисовывать сетку. Программа позволяет не только генерировать боксы разной формы, но и вставлять растровые картинки в качестве вершин графа.

Весьма удобным инструментом для ручного построения графов является программа Visio 2003 (рис.3.2), которая содержит средства построения графов и диаграмм, необходимые широкому кругу пользователей. Имеется возможность легко передвигать отдельные боксы так, что при этом деформируются линии, связывающие данный бокс с другими. Программа позволяет сохранить Visio-диаграмму в web-формате. Интерфейс создаваемых в Visio web-страниц отличается привлекательностью, предоставляет широкие возможности для совместной работы с данными как в организации, так и за ее пределами.

Рис. 3.1. Пример построения диаграммы в uDraw (Graph)

Рис. 3.2. Построение графа в Visio 2003

KBE (англ. Knowledge Base Editor) - редактор исходных текстов баз знаний на языке SCg с открытым исходным кодом, разрабатываемый в рамках проект OSTIS. Разработка ведется на языке программирования C++ с использованием фреймворка Qt.

Visual Graph Editor - это легкий кроссплатформенный визуальный редактор графов на Qt, предназначен для быстрого и удобного создания, редактирования и сохранения графов и анализа проблем, связанных с графами. Предоставляет возможность изменить граф в трех основных плоскостях (сверху, спереди, сбоку) и просмотреть его в трехмерном режиме.Для анализа представлены методы для расширения функциональности программы через JavaScript-подобный язык и RPC (передача данных через XML по протоколу HTTP).

Graphviz - пакет утилит по автоматической визуализации графов, заданных в виде описания на языке DOT, а также дополнительных TUI и GUI программ, виджетов и библиотек, используемых при разработке ПО для визуализации структурированных данных. Пакет Graphviz разработан специалистами лаборатории AT&T и распространяется с открытыми исходными файлами по лицензии EPL (Eclipse Public License) и работает на многих операционных системах, включая Linux, Mac OS, Unix-подобные, Microsoft Windows. yEd Graph Editor - простое, но в тоже время достаточно мощное приложение, предназначенное для быстрого и добного создания, редактирования и сохранения графов, диаграмм, блок-схем и графиков. YED находится в свободном бесплатном доступе и работает на всех основных платформах: Windows, Unix / Linux и Mac OS X. Программа построена на базе java-библиотеки для отрисовки графов под названием yFiles. Есть экспорт в форматы SVG, WMF, BMP, JPG и GIF. Поддерживает различные алгоритмы отрисовки.

Рис. 3.3. Главное окно Visual Graph Editor

Рис. 3.4. Пример визуализации графа с помощью Graphviz

Рис. 3.5. Главное окно yEd Graph Editor

Рис. 3.6. Главное окно KBE

3.2 Разработка семантической сети

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

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

В данной работе был проанализирована сказка «Иван Царевич и принцесса-лягушка» и была создана информационная модель в виде графа. Вершины этого графа - персонажи и предметы из сказки, дуги - связи между ними (Приложение 1 Рис. 1 Семантический граф «Иван Царевич и принцесса-лягушка»). В качестве программы для визуализации графа была использована yEd Graph Editor.

Также была сгенерирована сеть фрагмента 4мм слоя почвы, которая была импортирована в виде 2D графика. Узлы представляют собой поры. Размеры пор в диапазоне от 10 до 100 мкм. Сеть содержит узлы из 13,500 и 26,000 занесенных в единый взаимосвязанный домен (Приложение 1 Рис. 2 Граф, отображающий соединение микропор почвы).

Заключение

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

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

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

Приложение

Размещено на http://www.allbest.ru/

19

Размещено на http://www.allbest.ru/

Рис. 1 Семантический граф «Иван Царевич и принцесса-лягушка».

Рис. 2 Граф, отображающий соединение микропор почвы

Размещено на Allbest.ru