close

Вход

Забыли?

вход по аккаунту

?

Аксиоматический подход к определению знаний в системах принятия решений.

код для вставкиСкачать
Подставив (2),(3) в (1), получим общий вид:
G(l,q) = G(lс,qс)? G(lп,qс) ? G(lм,qс)?
? G(lн,qс) ? G(lч,qс)? G(lс,qгл) ?
? G(lп,qгл) ? G(lм,qгл)?
? G(lн,qгл) ? G(lч,qгл).
(4)
В формуле (4) используется целое семейство предикатов общего вида G(l,q), каждый из которых
будет истинен (равен 1), если грамматический класс
первой основы S1 сочетается с грамматическим классом S2.
Второй компонент обобщенной синтагматической модели ? семантическая сочетаемость основ в
сложнословной конструкции. Пусть Т(LS1i,LS2j) ?
обобщенный семантический предикат синтагматики, с помощью которого можно определить способность ЛСГ LS1 и LS2 быть семантически сочетаемыми друг с другом. Введем семейство предикатов
T(LS1i, LS2j), каждый из которых: Т(LS1i,LS2j) = 1,
если ЛСГ LS1i и LS2j ? семантически сочетаются;
0 ? в противном случае.
Проанализировав все значения предикатов данного семейства ? обобщенных семантических предикатов синтагматики для множества лексических
групп LS1i и LS2j, можно сделать определенные
выводы о продуктивности тех или иных групп, о
тенденциях в развитии деривационного процесса в
рамках применения неологизмов. А это очень важная область использования сложных слов, поскольку с появлением новых научных отраслей знаний и
освоением космического пространства все больше и
больше новых слов входит в лексику украинского
и русского языков. В общем случае ? это обозначения новых терминов, описывающие современные
научные достижения и процессы в таких областях
научной деятельности как биофизика, лазерные
технологии, компьютерная техника.
Можно выделить 43 продуктивных семантических пересечений первой и второй ЛСГ, посредУДК 681.324
АКСИОМАТИЧЕСКИЙ ПОДХОД К
ОПРЕДЕЛЕНИЮ ЗНАНИЙ В
СИСТЕМАХ ПРИНЯТИЯ РЕШЕНИЙ
РЕЗНИЧЕНКО О.В.
Предложен общий подход и основные аксиоматические определения для создания теории представления и обработки знаний в системах управления с использованием искусственного интеллекта.
В современных автоматизированных системах
управления (АСУ) эффективность и надежность
работы во многом определяются способностью действовать в условиях, когда часть входной информации неопределена либо измерена с непренебрежимо высокой погрешностью. Особенно важным
это свойство представляется для компьютерных систем поддержки принятия решений (СППР) с элементами искусственного интеллекта, поскольку требования к ним, как правило, выше, чем к традиционным АСУ.
РИ, 1998, № 2
ством которых получаются разнообразные варианты сложнословных формантов. При анализе всех
семантических связей заметно, что самые продуктивные в плане деривации для LS1i ? 25, 20, 23
группы , а для LS2j ? 8, 23 и 9 группы. Вернемся к
математической модели семантической сочетаемости основ ? ее второму компоненту: частной семантической модели синтагматики. Введем предикат
Z(S1p, S2q) ? частный семантический предикат существования, который Z(S1p, S2q)= 1, если в лексике существует слово L; 0 ? в противном случае.
Этот предикат можно применять, когда заранее
(с помощью предиката Т(LS1i, LS2j)) известно,
сочетаются или нет первая и вторая ЛСГ.
Тогда запишем полностью условие семантической сочетаемости парадигмативных групп:
Q(S1,S2) = T(LS1i,LS2j ) ? Z(S1p,S2q).
(5)
И, наконец, обобщая все изложенные выше результаты и базируясь на том, что синтагматическое
отношение между двумя основами в сложном слове
имеет и грамматические (1.1), и семантические (1.5)
ограничения сочетаемости, получаем:
W (S1, S2) = G(l,q ) ? Q(S1,S2)= (G (l,q c) ? G(l,q гл ))?
? T (LS1i, LS2j ) ? Z(S1p, S2q),
где W(S1, S2) ? синтагматическое отношение между
двумя производящими основами в сложном слове L.
Литература: 1. Шабанов- Кушнаренко Ю.П. Теория интеллекта. Математические средства. Х.: Вища шк.,1984.
144 с. 2. Шабанов- Кушнаренко Ю.П. Теория интеллекта.
Проблемы и перспективы. Х.: Вища шк., 1987. 160 с. 3.
Краткая русская грамматика / Белоусов В.Н. и др./ Под
ред.Шведовой Н.Ю. М.: Рус. яз., 1989.639 с.
Поступила в редколлегию 12.06.98
Рецензент: д-р физ.-мат. наук, проф. Яковлев С.В.
Стороженко Александра Владимировна: ассистент кафедры экономики и менеджмента ХТУРЭ. Адрес: 310022,
Украина, Харьков, пр. Правды, 5, кв. 166, тел. 43-49-02.
Именно поэтому проблема представления и обработки неопределенности в различных ее проявлениях привлекает внимание большого количества
исследователей [1-5].
Важной особенностью современных СППР в
АСУ является способность к автоматизированному
обучению в специальном цикле либо непосредственно в процессе работы. Для построения СППР,
работающей в условиях неопределенности, необходимо решить следующие задачи.
1. Определить способ представления входной
информации (в том числе и обучающей) в виде как
простых, так и сложных событий.
2. Определить способ представления универсального закона.
3. Сформулировать принцип построения процедуры автоматизированного обучения I.
4. Сформулировать принцип построения процедуры принятия решения D.Универсальный закон
можно представить в виде множества пар ?входвыход?:
{
}
S = SX Ч SY = xi , yi ,
каждой из которых поставлен в соответствие элемент из некоторого частично упорядоченного множества Z, т.е. как
109
?
?
? x i , y j , z t ?.
?
?
Входное частное утверждение с учетом недетерминированности также можно представить в виде
отображения множества S во множество Z.
При этом в обоих случаях значение z t индуцирует отношение предпочтения на множестве событий S. Если Z есть множество действительных
чисел, то отображение T : S ? Z является мерой.
Введем ненормированную счетно-аддитивную
меру истинности (trustworthy measure) u(s i ) некоторого события s i из универсального множества событий S, удовлетворяющую следующим аксиомам.
1. Обычные аксиомы счетно-аддитивной меры [6]:
u(?) =0;
=
u( s i ) w ,
w ?[ 0, + ?);
?s i , s j ?S : s i ? s j =
?,
u(s i ? s j )= u(s i ) + u(s j ).
2. Мера истинности индуцирует отношение предпочтения на множестве событий S:
?s i , s j ? S
u( s i ) > u ( s j ) ? s i ? s j .
Определив s k ? S , мы одновременно указываем
на событие s k = S \ s k . Таким образом, отдельное
событие s k и его мера истинности u( s k ) фактически не существуют сами по себе, т.е. характеризуя
явление или событие, мы всегда задаем распределе-
ние меры истинности Q(S) = {u(s k )} , ?k : s k ?S .
В отличие от вероятности, мера истинности,
вообще, является недетерминированной величиной,
степень достоверности которой будем называть уровнем значимости распределения меры истинности.
3. Уровень значимости есть счетно-аддитивная
ненормированная функция:
V(?) =0;
V=
(Q i ) q , q ?[0,+?);
?Q i , Q j ? G: Q i ? Q j =
?,
V( Q i ? Q j )= V( Q i ) + V(Q j ).
4. Уровень значимости индуцирует отношение
предпочтения на множестве распределений меры
истинности G:
?Q i , Q j ? G: V(Q i ) > V(Q j ) ? Q i ? Q j .
Истинностью события t (s i ) назовем пару
< u( si ), q > .
Распределением истинности T(S) назовем множество пар
{ u(si ), q } =
Q(S), V( Q) .
F(Ti ) ? F(T j ),
где F ? некоторый функционал.
6. Уровень значимости определенности сложного события
?s i , s j , s k : ? ( s i ) =
< u1 ( si ), q 1 > ,
< u 2 (s j ), q 2 > ,
? (s j ) =
s k= si ? s j ,
?(s k ) =
< u(s k ), q 3 >:
u(s k ) = f ( u 1 (s i ), u 2 ( s j ), q 1 , q 2 ),
q 3 = min(q 1 , q 2 ),
где f ? некоторая функция;  ? ? произвольная
операция.
Распределение меры определенности (certitude
measure) C(S) = {u(s i )} задается аксиомами 1-6.
Все множество возможных пар t (s i ) образует положительный конус в некотором евклидовом пространстве ( Пространство Возможных Событий )
? + , так как никакие операции над ними не выводят результат за пределы конуса (согласно аксиомам ). Задав метрику на ? + , например вида ? 1 ,
можно определить с ее помощью отношение эквивалентности, т.е. задать основу разбиения на классы. С использованием метрики ? 1 вводится также
отношение толерантности, характеризующее подобие различных событий в ? + . Совокупность точек
Пространства Возможных Событий вместе с операцией сложения, согласно аксиоме 1, образует абелеву полугруппу с нулем.
Далее для решения задач 3 и 4 введем аксиомы
индуктивного построения (I) меры возможности
(possibility measure) ( P(S) = {u(si )} ) и дедуктивного
вывода (D) с использованием частного утверждения и универсального закона.
7. Мера возможности определяется на основании наблюдений:
1. P(S) = I(O);
2. I(?) =? ;
3. I(O t ) = O t ;
где O t ? состояние объекта в момент времени t,
O t ? (S Ч R + );
O ? множество {O t } состояний
объекта, O ? (S Ч R + ) .
8. Принятие решений основано на следующих
принципах:
1. D(s* , ?) ? не определено.
j
При отсутствии универсального закона результат принятия решений не определен.
2. D(?, P) =
sK :
Для представления определенности сложного события помимо указанных выше аксиом введем
также аксиомы следования (5) и минимального
=
s K arg max({u( s i )}), i: s i ?S ;.
уровня значимости (6):
Это означает, что при отсутствии частного ут5. Аксиома следования:
верждения об объекте исследования принятие решений сводится к функции выбора из множества
?Ti , T j : ? k u i ( s k ) = ?? u j (s k ),
=
? const , ? ? 1 ,
110
РИ, 1998, № 2
всех возможных состояний sK по критерию максимума значения меры возможности u(si).
? s K , u(s K ) > 0;
*
3. D( s j , P) = ? ? , u(s ) = 0;
K
?
u( s K ) = max({u( s m )}),
?m : s*m ? s m ,s*i ? s i ,
{
}
?
?
min?? s*i ? s*j ?? , i: s i ?S.
Если же присутствует частное утверждение, содержащее значения некоторых характеристик объекта исследования, то аргументом функции выбора
s*m
?=
s *j
выступает такое подмножество sm множества всех
возможных состояний, которое включает в себя
множество значений
s*m , наиболее близких задан-
ным, а выбор также осуществляется по критерию
максимума меры возможности u(si).
Таким образом, на основе введенной меры истинности предложены средства представления знаний в условиях недетерминированности.
Заданы основные принципы построения процедуры автоматизированного обучения, сущность коУДК 519.715.1
ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ
ОПРЕДЕЛЕНИЯ ИЗОМОРФИЗМА
ГРАФОВ
ЛИСТРОВОЙ С.В., ПЕВНЕВ В.Я., ТЯЖЛОВ А.Г.
Разработан алгоритм для определения изоморфизма
произвольных графов. В качестве сравниваемых характеристик предложена кодовая матрица, при использовании которой возможно распараллеливание процесса определения изоморфизма. Реализация подобного алгоритма на параллельной структуре позволяет решать поставленную задачу в реальном масштабе времени.
Задачи определения изоморфизма графов охватывают довольно широкий круг проблем. В их
числе автоматизация контроля в САПРБИС, синтаксическое распознавание образов, построение и
исследование на оптимальность по структурной надёжности, живучести, связности однородных структур вычислительных систем [1-3].
Алгоритмов, распознающих изоморфизм произвольных графов, известно более 40, однако все они
экспоненциальные. Существует гипотеза, что проблема изоморфизма графов близка к NP-полным
задачам. Известны и полиномиальные алгоритмы,
но только для специальных классов графов. Например, алгоритм Юнгера-Суссенгаза [4], полиномиально работающий с планарными графами.
Для установления факта изоморфизма графов G
и G? важно выяснить, какие их характеристики
инвариантны. Инвариантом графа называется параметр, имеющий одно и то же значение для всех
графов, изоморфных G. Примерами инвариант могут быть число вершин, ребер, список степеней
вершин, заданный в убывающем или возрастающем
РИ, 1998, № 2
торого заключается в формировании меры истинности с учетом меры определенности исходной информации.
И, наконец, определены принципы дедуктивного
вывода, представляющего собой формирование меры
истинности целевых событий с учетом меры истинности исходной информации об объекте распознавания и меры истинности универсального закона.
Литература: 1.Нечеткие множества и теория возможностей. Последние достижения / Под ред. Р.Р.Ягера//
Пер. с англ. М.:Радио и связь,1986. 408 С. 2.Schalkoff,
Robert J. Artificial intelligence : an engineering approach. McGraw Hill,Inc., 1990. 646 P. 3.Dempster, A.P. Upper and
lower probabilities induced by multi-valued mapping.
Ann.Math.Statist., 1967, Vol.69. P.469-474. 4. Shafer G.
A mahematical theory of evidence. Princeton, New York:
Princeton University Press, 1976. 218 P. 5. Shortliff, E.H.
Computer-based Medical Consultation MYCIN, American
Elsevier, New York, 1976. 192 P. 6. Cohn, Donald L. Measure
theory. Boston, Basel, Stuttgart: Birkhausen, 1980. 373 P.
Поступила в редколлегию 22.05.98
Рецензент: д-р техн. наук, проф. Воробьев Ю.С.
Резниченко Олег Вячеславович, канд. техн. наук, старший научный сотрудник ХАИ. Научные интересы: принятие решений в условиях неопределенности, экспертные системы, представление знаний. Увлечения и хобби: история. Адрес: 310070, Украина, Харьков, ул.Чкалова, 17, тел. 44-23-14.
порядке. В принципе, инвариантом может являться
матрица смежности. Очевидно, что разной нумерации вершин графа соответствуют определённые перестановки строк и столбцов матрицы смежности.
При наличии в графе N вершин поиск нужной
последовательности перестановок строк и столбцов
матрицы потребует O(N!) операций, т.е. определить
изоморфизм двух произвольных графов в этом
случае оказывается достаточно трудно.
Нашей целью является разработка алгоритма определения изоморфизма графов, основанного на
определении инвариантов дерева путей, и его параллельная реализация.
Для решения поставленной задачи было введено
понятие кодовой матрицы K=||kij||, которая содержит p столбцов (p=<N) и N строк, где N - количество вершин в графе. Элемент матрицы kij представлен парой чисел, соответствующих степени захода ?
j-(i) и исхода ?j+(i) вершины i в j-м ярусе
стянутого дерева путей, находящегося на i-й линейке этого дерева. Под стянутым деревом путей[5]
понимаем такое дерево, в котором i-е вершины j-го
яруса объединены без нарушения связей.
Рассмотрим два произвольных графа G и G?,
имеющих одинаковое число вершин N и рёбер с
матрицами смежностей C и C? соответственно. Построим для всех вершин обоих графов кодовые
матрицы K(i) и K?(i), i=1,?N.
Предположим, что в рассматриваемых двух подмножествах нашлись две равные матрицы K(x)=K?(y)
для вершины x графа G и вершины у графа G?.
Поскольку номера строк в матрицах K(x) и
K?(y) соответствуют номерам вершин в графах G и
G?, построим двудольный граф соответствия
G*(X,Y). В одной доле разместим 1,2,..., N вершин,
что соответствуют номерам строк кодовой матрицы
K(x), во второй ? 1?,2?,..., N? вершин, соответствующих номерам строк матрицы K?(y). Соединим
рёбрами в различных долях те вершины, для кото111
Документ
Категория
Без категории
Просмотров
33
Размер файла
301 Кб
Теги
знание, решение, система, подход, принятие, определение, аксиоматически
1/--страниц
Пожаловаться на содержимое документа