Транзитивное замыкание

@PinkPink · Регистрация: 10.05.2012

Author24 — интернет-сервис помощи студентам

Добрый вечер!
Разбираю транзитивное замыкание и насколько я поняла, выполняется перемножение матриц. Однако пример, который находится на изображении иллюстрирует результат возведения матрицы в 2 и 3 степень. При умножении матрицы самой на себя, т.е. при возведении в степень, я получила совсем другой результат, а именно
(0.8•0.8)+(1•0)+(0.1•0.3) (0.8•1)+(1•0.4)+(0.1•0) (0.8•0.1)+(1•0)+(0.1•0.2)
(0•0.8)+(0.4•0)+(0•0.3) (0•1)+(0.4•0.4)+(0•0) (0•0.1)+(0.4•0)+(0•0.2)
(0.3•0.8)+(0•0)+(0.2•0.3) (0.3•1)+(0•0.4)+(0.2•0) (0.3•0.1)+(0•0)+(0.2•0.2)
=
0.67 1.2 0.1
0 0.16 0
0.3 0.3 0.07

Скажите пожалуйста, каким методом там выполняется умножение и почему получается такой разный результат?

iifat · 11.02.2013, 05:56

Смотря что за матрицы, от этого зависит, что за сложение и что за умножение используются в формулах.

@Mysterious Light · 11.02.2013, 12:09

В данном случае ТС имеет в виду (хоть и не написала) следующее: http://www.sernam.ru/book_smn.php?id=24
$https://www.cyberforum.ru/cgi-bin/latex.cgi?R^2 \; :\; (x,z)\; \mapsto\; \max\limits_y \quad \min (\mu(x,y), \mu(y,z))$
То есть под (+) подразумевается взятие наибольшего числа, под (•) подразумевается взятие меншего числа.
С помощью Wolfram Math я подсчитал выписанное ТС выражение и оно сошлось с тем, что в ответе указано.
Действетильно, например, (0.8•0.8)+(1•0)+(0.1•0.3)=0.8+0+0.1=0.8

@PinkPink · 11.02.2013, 19:06 **[ТС]**

Спасибо большое за ответ!
Возможно, вы сможете развеять мои сомнения ещё по одному вопросу. Как видите вычисление матриц в степени k производится до R^k-1 = R^k, но существуют ситуации, когда такого равенства просто нет. Я не очень поняла как поступать в таком случае. Как мне известно, транзитивное замыкание используется для когнитивных карт, которые необходимы для прогнозирования систем. Может ли k быть выбрано вручную в зависимости от степени прогнозирования? т.е. насколько далеко мы хотим спрогнозировать результат? Или существует какое-то k, которое используется всегда в случае если последовательность вычислений не сходится?

@Mysterious Light · 12.02.2013, 10:22

Я больше привык работать с бинарными отношениями

Там транзитивное замыкание определяется как наименшее транзитивное множество, содержащее (как подмножество) рассматриваемое бин. отношение. Поэтому в матричном виде выполняется
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\tilde{R} = \bigcup\limits_{k=0}^\infty R^k$
Логика проста: R^k выражает бин. отношение между элементами (x,y), между которыми существует цепочка R-переходов длины ровно k, то есть если существует последовательность {a0,a1,a2,...,ak} такая, что a0=x, ak=y и любые два соседа входят в отношение R.
На моей памяти явно это понятие встречалось один раз, когда нужно было перейти от понятия одношаговой редукции к многошаговой, где количество шагов может быть любым. Поэтому если мы наперёд знаем, что можно ограничиться K шагами, то объединение в формуле становится конечным.

Здесь:
В статье указана подобная формула.

Можно не читать, это мысли вслух

Если логика та же, то можно ограничиться достаточно большим числом первых членов последовательности. Но это может не сработать в особо специфичиских вариантах (которые мы не рассматриваем) определения (+) и (*), потому что нет гарантии, что сумма
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\bigcup\limits_{k=0}^K R^k$
быстро сходится с ростом K. Но это нас не должно волновать, думаю.
Что всё-таки подразумевается под формулой (17.8), которая написана первой в посте, если сумма бесконечная?
Для «чётких» бин.отношений она означает сумму по счётной коллекции множеств {I,R,R²,...}. Иными словами, что ожидаемо, это означает, что xRy т.и т.т., когда найдётся k, что xR^ky, что эквивалентно рассуждениям выше по последовательность.
Для нечётких множеств это может означать по (12.25) и (12.26)
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\mu_{\tilde{R}}(x,y) = \max_k \; \mu_{R^k}(x,y)$
здесь ищется максимум или наибольшее число среди счётной последовательности, или
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\mu_{\tilde{R}}(x,y) = \sup_k \; \mu_{R^k}(x,y)$
здесь ищется супремум.
Как трактовать это я не знаю. В случае конечных (в частности, двучлена) сумм наибольший элемент/максимум и супремум совпадает, потому что (0,1) линейно упорядочена, т.е. любые два числа сравнимы. А вот для бесконечных множеств они разнятся, что выражается в таком примере:
Пусть случилось так, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mu_{R^k}(x,y)$ — строго возрастающая последовательность по k для каких-то (x,y) и пусть R не содержала 1 в себе. Но она к тому же ограничена 1, которая не может быть достигнута (ведь постоянно идёт min-max, единице неоткуда взяться). Тогда эта последовательность имеет супремум, но не имеет максимума, потому что супремум не достигается, то есть нет его в последовательности.
Ну так как будем трактовать формулу (17.8)?

(17.16) утверждает, что для конечного носителя E сумма всегда конечна.
В остальных случаях либо читать в литературе, что нужно делать строго, либо ограничиться очень большим K. ИМХО, Вы правильно говорите по поводу дальновидности прогноза.

@PinkPink · 17.02.2013, 23:37 **[ТС]**

Возникли сложно с составлением матрицы взаимовлияния.
Вкратце:
есть граф, вес на рёбрах между вершинами это влияние. Соответственно можно составить матрицу этих весов. Но! Влияние может быть не прямое т.е. ребро от одной вершины к другой, а просто, если существует путь от одной вершины к другой. А влияет на Б, Б влияет на В, а В влияет на Г. Соответственно необходимо найти как А влияет на Г.

Все вычисления этих значений происходят на основе каузальной алгебры. На картинках, которые я прикрепила видно, какие операции, что в ней значат.
Для определения влияния всех вершин друг на друга используется транзитивное замыкание. Но вместо операции умножения (при возведении в степень) используется операция макстриангулярной композиции, которую мы разобрали выше. И к полученным степеням матриц применяется операция max как указано в книге. Напрашивается вывод, что если у нас везде только операции min и max новых значений мы не получим. Однако, в примере, приведённом в этой же книге чотко видна изначальная матрица, а потом результирующая матрица, со значениями, которые по моему мнению могли быть получены только благодаря умножению (вопрос тогда каким образом).
Вообщем, не могу придти к такому же результату как в примере в книге, даже чисто логически.

26.05.2013, 20:04

Здравствуйте!
Подскажите, пожалуйста, источник, фотографии из которого здесь вывешены.

Правильно ли я понимаю по примеру, что транзитивное влияние А на Г рассчитывается, как произведение сил влияния и выбора наибольшего из них (в случае положительных влияний)?

@PinkPink · 27.05.2013, 11:09 **[ТС]**

Сообщение от Igor_Gercog

Здравствуйте!
Подскажите, пожалуйста, источник, фотографии из которого здесь вывешены.

Правильно ли я понимаю по примеру, что транзитивное влияние А на Г рассчитывается, как произведение сил влияния и выбора наибольшего из них (в случае положительных влияний)?

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

27.05.2013, 12:42

Спасибо большое! Буду ждать!

@PinkPink 9 / 9 / 5 Регистрация: 10.05.2012 Сообщений: 292
		1
	Транзитивное замыкание 10.02.2013, 21:00. Показов 9012. Ответов 8 Метки нет (Все метки) Добрый вечер! Разбираю транзитивное замыкание и насколько я поняла, выполняется перемножение матриц. Однако пример, который находится на изображении иллюстрирует результат возведения матрицы в 2 и 3 степень. При умножении матрицы самой на себя, т.е. при возведении в степень, я получила совсем другой результат, а именно (0.8•0.8)+(1•0)+(0.1•0.3) (0.8•1)+(1•0.4)+(0.1•0) (0.8•0.1)+(1•0)+(0.1•0.2) (0•0.8)+(0.4•0)+(0•0.3) (0•1)+(0.4•0.4)+(0•0) (0•0.1)+(0.4•0)+(0•0.2) (0.3•0.8)+(0•0)+(0.2•0.3) (0.3•1)+(0•0.4)+(0.2•0) (0.3•0.1)+(0•0)+(0.2•0.2) = 0.67 1.2 0.1 0 0.16 0 0.3 0.3 0.07 Скажите пожалуйста, каким методом там выполняется умножение и почему получается такой разный результат? Миниатюры 0

iifat 2731 / 1812 / 197 Регистрация: 05.06.2011 Сообщений: 5,236
	11.02.2013, 05:56	2
	Смотря что за матрицы, от этого зависит, что за сложение и что за умножение используются в формулах. 0

@Mysterious Light $Эксперт по математике/физике$ 4300 / 2091 / 431 Регистрация: 19.07.2009 Сообщений: 3,163 Записей в блоге: 24
	11.02.2013, 12:09	3
	В данном случае ТС имеет в виду (хоть и не написала) следующее: http://www.sernam.ru/book_smn.php?id=24 $https://www.cyberforum.ru/cgi-bin/latex.cgi?R^2 \; :\; (x,z)\; \mapsto\; \max\limits_y \quad \min (\mu(x,y), \mu(y,z))$ То есть под (+) подразумевается взятие наибольшего числа, под (•) подразумевается взятие меншего числа. С помощью Wolfram Math я подсчитал выписанное ТС выражение и оно сошлось с тем, что в ответе указано. Действетильно, например, (0.8•0.8)+(1•0)+(0.1•0.3)=0.8+0+0.1=0.8 Миниатюры 1

@PinkPink 9 / 9 / 5 Регистрация: 10.05.2012 Сообщений: 292
	11.02.2013, 19:06 [ТС]	4
	Спасибо большое за ответ! Возможно, вы сможете развеять мои сомнения ещё по одному вопросу. Как видите вычисление матриц в степени k производится до R^k-1 = R^k, но существуют ситуации, когда такого равенства просто нет. Я не очень поняла как поступать в таком случае. Как мне известно, транзитивное замыкание используется для когнитивных карт, которые необходимы для прогнозирования систем. Может ли k быть выбрано вручную в зависимости от степени прогнозирования? т.е. насколько далеко мы хотим спрогнозировать результат? Или существует какое-то k, которое используется всегда в случае если последовательность вычислений не сходится? 0

@Mysterious Light $Эксперт по математике/физике$ 4300 / 2091 / 431 Регистрация: 19.07.2009 Сообщений: 3,163 Записей в блоге: 24
	12.02.2013, 10:22	5
	Я больше привык работать с бинарными отношениями Там транзитивное замыкание определяется как наименшее транзитивное множество, содержащее (как подмножество) рассматриваемое бин. отношение. Поэтому в матричном виде выполняется $https://www.cyberforum.ru/cgi-bin/latex.cgi?\tilde{R} = \bigcup\limits_{k=0}^\infty R^k$ Логика проста: R^k выражает бин. отношение между элементами (x,y), между которыми существует цепочка R-переходов длины ровно k, то есть если существует последовательность {a0,a1,a2,...,ak} такая, что a0=x, ak=y и любые два соседа входят в отношение R. На моей памяти явно это понятие встречалось один раз, когда нужно было перейти от понятия одношаговой редукции к многошаговой, где количество шагов может быть любым. Поэтому если мы наперёд знаем, что можно ограничиться K шагами, то объединение в формуле становится конечным. Здесь: В статье указана подобная формула. Можно не читать, это мысли вслух Если логика та же, то можно ограничиться достаточно большим числом первых членов последовательности. Но это может не сработать в особо специфичиских вариантах (которые мы не рассматриваем) определения (+) и (), потому что нет гарантии, что сумма $https://www.cyberforum.ru/cgi-bin/latex.cgi?\bigcup\limits_{k=0}^K R^k$ быстро сходится с ростом K. Но это нас не должно волновать, думаю. Что всё-таки подразумевается под формулой (17.8), которая написана первой в посте, если сумма бесконечная? Для «чётких» бин.отношений она означает сумму по счётной коллекции множеств {I,R,R²,...}. Иными словами, что ожидаемо, это означает, что xRy т.и т.т., когда найдётся k, что xR^ky, что эквивалентно рассуждениям выше по последовательность. Для нечётких множеств это может означать по (12.25) и (12.26) $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mu_{\tilde{R}}(x,y) = \max_k \; \mu_{R^k}(x,y)$ здесь ищется максимум или наибольшее число среди счётной последовательности, или $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mu_{\tilde{R}}(x,y) = \sup_k \; \mu_{R^k}(x,y)$ здесь ищется супремум. Как трактовать это я не знаю. В случае конечных (в частности, двучлена) сумм наибольший элемент/максимум и супремум совпадает, потому что (0,1) линейно* упорядочена, т.е. любые два числа сравнимы. А вот для бесконечных множеств они разнятся, что выражается в таком примере: Пусть случилось так, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mu_{R^k}(x,y)$ — строго возрастающая последовательность по k для каких-то (x,y) и пусть R не содержала 1 в себе. Но она к тому же ограничена 1, которая не может быть достигнута (ведь постоянно идёт min-max, единице неоткуда взяться). Тогда эта последовательность имеет супремум, но не имеет максимума, потому что супремум не достигается, то есть нет его в последовательности. Ну так как будем трактовать формулу (17.8)? (17.16) утверждает, что для конечного носителя E сумма всегда конечна. В остальных случаях либо читать в литературе, что нужно делать строго, либо ограничиться очень большим K. ИМХО, Вы правильно говорите по поводу дальновидности прогноза. 0

@PinkPink 9 / 9 / 5 Регистрация: 10.05.2012 Сообщений: 292
	17.02.2013, 23:37 [ТС]	6
	Возникли сложно с составлением матрицы взаимовлияния. Вкратце: есть граф, вес на рёбрах между вершинами это влияние. Соответственно можно составить матрицу этих весов. Но! Влияние может быть не прямое т.е. ребро от одной вершины к другой, а просто, если существует путь от одной вершины к другой. А влияет на Б, Б влияет на В, а В влияет на Г. Соответственно необходимо найти как А влияет на Г. Все вычисления этих значений происходят на основе каузальной алгебры. На картинках, которые я прикрепила видно, какие операции, что в ней значат. Для определения влияния всех вершин друг на друга используется транзитивное замыкание. Но вместо операции умножения (при возведении в степень) используется операция макстриангулярной композиции, которую мы разобрали выше. И к полученным степеням матриц применяется операция max как указано в книге. Напрашивается вывод, что если у нас везде только операции min и max новых значений мы не получим. Однако, в примере, приведённом в этой же книге чотко видна изначальная матрица, а потом результирующая матрица, со значениями, которые по моему мнению могли быть получены только благодаря умножению (вопрос тогда каким образом). Вообщем, не могу придти к такому же результату как в примере в книге, даже чисто логически. Миниатюры 0

Igor_Gercog
	26.05.2013, 20:04	7
	Здравствуйте! Подскажите, пожалуйста, источник, фотографии из которого здесь вывешены. Правильно ли я понимаю по примеру, что транзитивное влияние А на Г рассчитывается, как произведение сил влияния и выбора наибольшего из них (в случае положительных влияний)?

@PinkPink 9 / 9 / 5 Регистрация: 10.05.2012 Сообщений: 292
	27.05.2013, 11:09 [ТС]	8
	Сообщение от Igor_Gercog Здравствуйте! Подскажите, пожалуйста, источник, фотографии из которого здесь вывешены. Правильно ли я понимаю по примеру, что транзитивное влияние А на Г рассчитывается, как произведение сил влияния и выбора наибольшего из них (в случае положительных влияний)? Да, вы правильно понимаете. На данный момент не могу вам точно сказать всех авторов, один из них как мне помнится Круглов. Возможно позже я смогу сказать более точно 1

Igor_Gercog
	27.05.2013, 12:42	9
	Спасибо большое! Буду ждать!