推移律とは
Transitivity
「甲が乙と関係し、乙が丙と関係するならば、甲も丙と関係する」という、関係の連鎖を保証する論理的性質
ひとことで言うと
「AとBが関係し、BとCが関係するなら、AとCも関係する」という論理のつながりの性質。
概要
推移律とは、ある関係Rについて「aRbかつbRcならば、aRcも成り立つ」という性質を指す論理学・数学の基本概念。 数値の大小関係(a<b かつ b<c ならば a<c)や、集合の包含関係、階層構造における上位・下位関係(is-a関係)など、多くの関係が推移律を満たす。 知識表現やオントロジーの分野では、推移律を満たす関係を利用して、明示的に記述されていない関係を推論によって導く「推移的閉包」を計算する。
背景
知識ベースや分類体系では、全ての関係を1つ1つ明示的に記述するのは非効率であり、一部の関係から芋づる式に新たな関係を導出できないかという要求があった。 推移律は、ある関係が「aRbかつbRcならばaRc」という性質を満たすことを保証することで、明示された関係から新たな関係を機械的に導出する基盤となる。
コード例
推移的閉包を計算する簡易的な例
def transitive_closure(pairs: set) -> set:
closure = set(pairs)
while True:
new_pairs = {
(a, d)
for a, b in closure
for c, d in closure
if b == c and (a, d) not in closure
}
if not new_pairs:
return closure
closure |= new_pairs
print(transitive_closure({("a", "b"), ("b", "c")}))利点
- 明示的に記述されていない関係を、既知の関係から機械的に導出できる
- 階層構造やオントロジーにおける包含関係・分類関係の整合性を検証する基準として使える
- 関係が推移律を満たすかどうかを確認するだけで、その関係の連鎖的な性質を保証できる
欠点
- 全ての関係が推移律を満たすわけではなく(例:「友人関係」は必ずしも推移的とならない)、適用できる関係かどうかの見極めが必要
- 大規模な知識ベースで推移的閉包を網羅的に計算すると、関係の組み合わせ数が急激に増加し計算コストが高くなる
- 推移律を誤って適用すると、実際には成り立たない関係を誤って導出してしまうリスクがある
比較
- オントロジー — オントロジーにおける概念の上位・下位関係(is-a関係)は、多くの場合推移律を満たす関係として設計される
関連用語
よくある質問
推移律を満たさない関係の例は？
「友人関係」は代表的な例で、太郎と花子が友人、花子と次郎が友人であっても、太郎と次郎が必ずしも友人とは限らない。関係の性質ごとに推移律が成り立つかを個別に確認する必要がある。
推移的閉包とは何？
ある関係について、推移律を適用して導出できる全ての関係を網羅的に求めたものを指す。 例えば「人間は哺乳類の一種である」「哺乳類は動物の一種である」という関係から「人間は動物の一種である」という関係を導出し、これを繰り返して得られる関係の集合が推移的閉包にあたる。