ݺߣ

ݺߣShare a Scribd company logo

온톨로지 추론 개요

•
•
S
Sang-Kyun Kim
1 of 17
온톨로지 추론 개요 2009. 4. 21 김상균 [email_address]
시맨틱 웹 웹에 존재하는 무한한 데이터를 처리하는데 한계 데이터를 쉽고 친숙하게 표현 웹을 통해 문서를 잘 교환할 수 있는 방법 데이터는 특정 어플리케이션에 의해서만 처리되고 보관됨 시맨틱 웹 (W3C Semantic Web Activity) 사람뿐만 아니라 기계가 이해하고 처리할 수 있도록 웹 상에 존재하는 정보에 시맨틱이 부여된 웹 데이터의 공유와 재사용을 위한 포맷 제공 데이터들간의 연관성을 표현하는 방법 제공
온톨로지 기계와 사람이 공유할 수 있는 지식을 명세 자동 프로세스를 구현하기 위한 선행 작업 어노테이션을 위한 어휘 (vocabulary) 제공 정형화된 명세 (formal specification) 을 기계가 이해할 수 있도록 함 기존 구조적 (syntactic) 마크업에 시맨틱을 부여 프리젠테이션 ( 예 , 폰트 크기 , 색깔등 ) 을 위한 기존 마크업뿐만 아니라 시맨틱 컨텐츠 마크업 추가 표준에 기반한 온톨로지 언어 필요
RDF 와 RDFS RDF : Resource Description Framework W3C Recommendation 그래프 기반으로 웹 자원을 표현할 수 있는 방법 제공 XML 표현 , 시맨틱 포함 메타데이터와 정보의 시맨틱을 기계가 이해할 수 있는 형태로 기술 RDFS : RDF Schema W3C Recommendation RDF 의 스키마 어휘를 추가 확장 Class, Property, type, subClassOf, subPropertyOf 등… 모델에 제약 조건 (constraint) 을 추가 ( 예 ) 8 x,y,z type(x,y) and subClassOf(y,z) ! type(x,z) 철수 사람 _:x rdf:type hasName 그래프의 Triple 표현 Subject _:x hasName Predicate rdf:type Object 사람 _:x 철수
RDF(S) 의 문제 RDF(S) 는 웹자원에 대한 관계 언어이며 또한 간단한 온톨로지 근본어휘 (primitive) 만을 제공 웹 자원에 대한 시맨틱을 기술하기에는 부족 Existence/cardinality 제약 조건이 없음 Transitive, inverse 또는 symmetrical 속성들이 없음 … 추론 (Reasoning) 을 지원하기 힘듬 RDF(S) 는 비표준 (Non-standard) 시맨틱을 지원하는데 이를 위한 기본적인 추론기가 없음 시맨틱 웹을 위한 새로운 온톨로지 언어가 필요
OWL (Web Ontology Language) W3C Web Ontology 워킹 그룹에 의해 개발 W3C Recommendation 이전에 발표된 DAML+OIL 과 OIL 언어에 기반 OWL 의 기반 구문 : RDF Schema 확장 ( 웹과 호환 ) 온톨로지 근본어휘 : Frame 언어 ( 사람이 이해하기 쉬움 ) 시맨틱 : 기술 로직 (Description Logic) 기반 OWL 의 3 종류 OWL Full : OWL 구문 + RDF OWL DL : SHOIN (D) 기술 언어와 동일 OWL Lite : OWL DL 의 간단한 서브셋
OWL(OWL DL) 의 장점 기술로직 기반의 잘 정의된 (well-defined) 시맨틱 제공 결정가능성 (decidability), 계산복잡도 (complexity) 등의 정형화된 로직 프로퍼티들이 잘 정립 결정가능한 추론 알고리즘이 고안되어 있음 최악의 경우 SHOIN 는 NExpTime-complete [S. Tobie, 2000] SHOIN 에 대한 결정가능한 알고리즘을 제안 [I. Horrock, 2006] 여러 구현된 시스템이 존재 추론기 : FaCT, Pellet, Racer 등 편집기 : Protégé, OilEd 등
기술 로직 (Description Logic) 로직 기반의 지식 표현을 위한 방법중의 하나 Semantic network 과 Frame 로직의 단점을 개선 개념 (Concept), 롤 (Role), 개체 (Individual) 를 사용해 도메인 기술 정형화된 시맨틱을 가짐 일차 로직 (First-order Logic) 의 일부분으로 결정 가능한 특징을 가짐 프레임 기반 시스템으로 확장 가능 ( 일차 로직의 일부분이 아님 ) 추론 서비스 제공 주요 추론 문제에 대해 결정 가능한 프로시저 제공 만족가능성 (satisfiability), 포함문제 (subsumption), 일관성 (consistency) 등
기술 로직의 구성 요소 개념 ( Concept : 단일 술어 / 하나의 자유 변수를 가지는 공식 ) 예 ) Person, Lawyer, HappyParent, (Student t Worker) 롤 ( Role : 이진 술어 / 두개의 자유 변수를 가지는 공식 ) 예 ) hasChild, loves, hasBrother  hasDaughter 개체 (Individual : 상수 ) 예 ) CheolSu, YeongHui, Korea 연산자 복잡한 개념과 롤을 만들기 위해 위해 사용 만족가능성 / 포함문제가 결정 가능하면서 가능한 낮은 복잡도를 가지게 해야 함
기술 로직 시맨틱 시맨틱은 일차 로직 모델을 사용한다 해석 도메인  I 해석 함수 I 개체 i I 2  I CheolSu YeongHui 개념 C I µ  I Student Worker Vehicle 롤 r I µ  I £  I hasChild owns (Student u Worker)
기술 로직의 종류 (1) ALC : 명제적으로 닫힌 ( propositionally closed ) 가장 작은 기술 로직 C, D ! A | 원자 개념 (atomic concept) > | 최상위 개념 (top concept) ? | 최하위 개념 (bottom concept) : A | 원자 부정 (atomic negation) C u D | 연언 (intersection) C t D | 선언 (disjunction) 8 R.C | 전체 정량자 (universal quantification) 9 R.C | 존재 정량자 (existential quantification) 예 ) 모든 자식이 변호사 또는 변호사인 아들을 가지는 사람 Person u 8 hasChild.(Lawyer t 9 hasChild.Lawyer)
기술 로직의 종류 (2) S : ALC + transitive roles ( R + ) 문자의 추가는 연산자 추가를 통해 언어의 표현력이 확장됨을 의미 H : role hierarchy ( 예 , hasDaughter v hasChild) O : nominals/singleton classes ( 예 , {Korea}) I : inverse roles ( 예 , isChildOf = hasChild – ) N : number restrictions ( 예 ,  2hasChild,  3hasChild) Q : qualified number restrictions ( 예 ,  2hasChild.Lawyer) F : functional number restrictions ( 예 ,  1hasMother) ALC + R + + role hierarchy ( H ) + inverse ( I ) + QNR ( Q ) = SHIQ SHIQ : OWL 의 기본이 되는 기술 로직 OWL DL ¼ SHIQ + nominals + XSD (i.e., SHOIQ (D)) OWL Lite ¼ SHIQ + functional restrictions + XSD (i.e., SHIF (D))
지식 베이스 ( 온톨로지 ) TBox 는 “스키마” 공리 (axiom) 의 집합 (sentences) {Lawyer v Person, HappyParent ´ Person u 8 hasChild.(Lawyer t 9 hasChild.Lawyer)} ABox 는 “데이터” 공리의 집합 (ground facts) {HappyParent(CheolSu), hasChild(CheolSu, YeongHui)} 지식 베이스 (KB) = TBox + ABox = 온톨로지
태블롵Ӛ즈 추론 (1) 온톨로지 추론 기술 로직의 태블롵Ӛ즈 ( Tableaux ) 추론 방법을 사용 지식 베이스 ( KB ) 만족가능성 문제 주요 온톨로지 추론 문제는 만족가능성 여부의 문제로 환원됨 예 ) KB K 에 관련해서 C v D iff K [ {x:(C u : D)} 가 만족가능하지 않음 태블롵Ӛ즈 알고리즘 일반적인 기술로직 시스템에서 지식 베이스의 만족가능성 또는 일관성을 결정하기 위해 사용 KB 의 공리 (axiom) 와 일관성을 가지는 하나의 모델을 구하는 알고리즘 ABox 공리들 (ground facts) 로부터 시작 Tableaux 확장 룰 (expansion rules) 을 더 이상 확장할 것이 없을 때까지 모든 연산자에 적용해 하나의 모델 (Tableau) 을 완성 충돌 (crash) 이 나타나면 만족 가능하지 않으며 없으면 만족가능
태블롵Ӛ즈 추론 (2) KB = { HappyParent = Person u 8 hasChild.( 9 hasChild.Lawyer t Lawyer) , HappyParent (Cheolsu), hasChild(Cheolsu,YeongHui), : Lawyer(YeongHui)} Cheolsu YeongHui hasChild HappyParent Person 8 hasChild.(Lawyer t 9 hasChild.Lawyer) Lawyer 1 2 3 Crash ABox 에 대한 그래프 생성 HappyParent TBox 공리에서 u 에 대한 확장 룰 적용 8 hasChild 에서 8 에 대한 확장 룰 적용 t 의 확장 룰 적용 후 9 hasChild.Lawyer 에 대한 확장 룰 적용 5 : Lawyer 1 2 3 4 9 hasChild.Lawyer t Lawyer 9 hasChild.Lawyer ? Laywer hasChild 4 t 룰의 오른쪽에서 지식 베이스의 충돌 발생 : 일관성이 없음 (Inconsistent KB) 5
태블롵Ӛ즈 추론 (3) 기술로직의 연산자에 대한 태블롵Ӛ즈 규칙 반복 적용 ( u , t , 8 , 9 등 현재 언어에서 지원하는 모든 연산자 ) 예 ) Student u Worker (CheolSu) ! Student(CheolSu) and Worker(CheolSu) 더 이상 적용할 규칙이 없거나 모순이 발생할 때까지 반복 적용 모순은 개념들간이 모순을 의미한다 ( 예 ) A(x) , : A(x) 어떤 룰은 결정적이지 않은 (nondeterministic) 특징을 가짐 이 경우 모든 경우를 탐색해야 함 예 ) t , 9 연산자 무한 루프의 경우 때문에 사이클 검사 ( 블로킹 ) 기능이 필요 예 ) { Person v 9 hasParent.Person, CheolSu:Person} Cheolsu ? hasParent Person 9 hasParent.Person Person ? Person hasParent BLOCK 9 hasParent.Person 9 hasParent.Person
결정 프로시저 ( Decision Procedure ) 태블롵Ӛ즈 알고리즘에서 룰을 적용한 후에 충돌 없는 그래프가 만들 어지는 것은 KB 의 만족가능성을 결정할 수 있는 것에 필요충분조건 사운드 (Sound) Tableaux 알고리즘을 적용해 완전히 확장된 그리고 충돌 없는 그래프가 만들어진다면 , KB 는 하나의 모델 (Tableau) 을 가질 수 있다 완전 (Complete) KB 에 대한 하나의 모델 (Tableau) 이 주어지면 , Tableaux 알고리즘을 적용해 완전히 확장된 그리고 충돌 없는 그래프를 만들 수 있다 중단 (Terminating) KB 의 모델 (Tableau) 에서 이름을 가지는 개체 , 트리의 외부차수 (out-degree), 트리의 깊이의 수가 한정된 개수를 가진다

More Related Content

온톨로지 추론 개요

  • 1. 온톨로지 추론 개요 2009. 4. 21 김상균 [email_address]
  • 2. 시맨틱 웹 웹에 존재하는 무한한 데이터를 처리하는데 한계 데이터를 쉽고 친숙하게 표현 웹을 통해 문서를 잘 교환할 수 있는 방법 데이터는 특정 어플리케이션에 의해서만 처리되고 보관됨 시맨틱 웹 (W3C Semantic Web Activity) 사람뿐만 아니라 기계가 이해하고 처리할 수 있도록 웹 상에 존재하는 정보에 시맨틱이 부여된 웹 데이터의 공유와 재사용을 위한 포맷 제공 데이터들간의 연관성을 표현하는 방법 제공
  • 3. 온톨로지 기계와 사람이 공유할 수 있는 지식을 명세 자동 프로세스를 구현하기 위한 선행 작업 어노테이션을 위한 어휘 (vocabulary) 제공 정형화된 명세 (formal specification) 을 기계가 이해할 수 있도록 함 기존 구조적 (syntactic) 마크업에 시맨틱을 부여 프리젠테이션 ( 예 , 폰트 크기 , 색깔등 ) 을 위한 기존 마크업뿐만 아니라 시맨틱 컨텐츠 마크업 추가 표준에 기반한 온톨로지 언어 필요
  • 4. RDF 와 RDFS RDF : Resource Description Framework W3C Recommendation 그래프 기반으로 웹 자원을 표현할 수 있는 방법 제공 XML 표현 , 시맨틱 포함 메타데이터와 정보의 시맨틱을 기계가 이해할 수 있는 형태로 기술 RDFS : RDF Schema W3C Recommendation RDF 의 스키마 어휘를 추가 확장 Class, Property, type, subClassOf, subPropertyOf 등… 모델에 제약 조건 (constraint) 을 추가 ( 예 ) 8 x,y,z type(x,y) and subClassOf(y,z) ! type(x,z) 철수 사람 _:x rdf:type hasName 그래프의 Triple 표현 Subject _:x hasName Predicate rdf:type Object 사람 _:x 철수
  • 5. RDF(S) 의 문제 RDF(S) 는 웹자원에 대한 관계 언어이며 또한 간단한 온톨로지 근본어휘 (primitive) 만을 제공 웹 자원에 대한 시맨틱을 기술하기에는 부족 Existence/cardinality 제약 조건이 없음 Transitive, inverse 또는 symmetrical 속성들이 없음 … 추론 (Reasoning) 을 지원하기 힘듬 RDF(S) 는 비표준 (Non-standard) 시맨틱을 지원하는데 이를 위한 기본적인 추론기가 없음 시맨틱 웹을 위한 새로운 온톨로지 언어가 필요
  • 6. OWL (Web Ontology Language) W3C Web Ontology 워킹 그룹에 의해 개발 W3C Recommendation 이전에 발표된 DAML+OIL 과 OIL 언어에 기반 OWL 의 기반 구문 : RDF Schema 확장 ( 웹과 호환 ) 온톨로지 근본어휘 : Frame 언어 ( 사람이 이해하기 쉬움 ) 시맨틱 : 기술 로직 (Description Logic) 기반 OWL 의 3 종류 OWL Full : OWL 구문 + RDF OWL DL : SHOIN (D) 기술 언어와 동일 OWL Lite : OWL DL 의 간단한 서브셋
  • 7. OWL(OWL DL) 의 장점 기술로직 기반의 잘 정의된 (well-defined) 시맨틱 제공 결정가능성 (decidability), 계산복잡도 (complexity) 등의 정형화된 로직 프로퍼티들이 잘 정립 결정가능한 추론 알고리즘이 고안되어 있음 최악의 경우 SHOIN 는 NExpTime-complete [S. Tobie, 2000] SHOIN 에 대한 결정가능한 알고리즘을 제안 [I. Horrock, 2006] 여러 구현된 시스템이 존재 추론기 : FaCT, Pellet, Racer 등 편집기 : Protégé, OilEd 등
  • 8. 기술 로직 (Description Logic) 로직 기반의 지식 표현을 위한 방법중의 하나 Semantic network 과 Frame 로직의 단점을 개선 개념 (Concept), 롤 (Role), 개체 (Individual) 를 사용해 도메인 기술 정형화된 시맨틱을 가짐 일차 로직 (First-order Logic) 의 일부분으로 결정 가능한 특징을 가짐 프레임 기반 시스템으로 확장 가능 ( 일차 로직의 일부분이 아님 ) 추론 서비스 제공 주요 추론 문제에 대해 결정 가능한 프로시저 제공 만족가능성 (satisfiability), 포함문제 (subsumption), 일관성 (consistency) 등
  • 9. 기술 로직의 구성 요소 개념 ( Concept : 단일 술어 / 하나의 자유 변수를 가지는 공식 ) 예 ) Person, Lawyer, HappyParent, (Student t Worker) 롤 ( Role : 이진 술어 / 두개의 자유 변수를 가지는 공식 ) 예 ) hasChild, loves, hasBrother  hasDaughter 개체 (Individual : 상수 ) 예 ) CheolSu, YeongHui, Korea 연산자 복잡한 개념과 롤을 만들기 위해 위해 사용 만족가능성 / 포함문제가 결정 가능하면서 가능한 낮은 복잡도를 가지게 해야 함
  • 10. 기술 로직 시맨틱 시맨틱은 일차 로직 모델을 사용한다 해석 도메인  I 해석 함수 I 개체 i I 2  I CheolSu YeongHui 개념 C I µ  I Student Worker Vehicle 롤 r I µ  I £  I hasChild owns (Student u Worker)
  • 11. 기술 로직의 종류 (1) ALC : 명제적으로 닫힌 ( propositionally closed ) 가장 작은 기술 로직 C, D ! A | 원자 개념 (atomic concept) > | 최상위 개념 (top concept) ? | 최하위 개념 (bottom concept) : A | 원자 부정 (atomic negation) C u D | 연언 (intersection) C t D | 선언 (disjunction) 8 R.C | 전체 정량자 (universal quantification) 9 R.C | 존재 정량자 (existential quantification) 예 ) 모든 자식이 변호사 또는 변호사인 아들을 가지는 사람 Person u 8 hasChild.(Lawyer t 9 hasChild.Lawyer)
  • 12. 기술 로직의 종류 (2) S : ALC + transitive roles ( R + ) 문자의 추가는 연산자 추가를 통해 언어의 표현력이 확장됨을 의미 H : role hierarchy ( 예 , hasDaughter v hasChild) O : nominals/singleton classes ( 예 , {Korea}) I : inverse roles ( 예 , isChildOf = hasChild – ) N : number restrictions ( 예 ,  2hasChild,  3hasChild) Q : qualified number restrictions ( 예 ,  2hasChild.Lawyer) F : functional number restrictions ( 예 ,  1hasMother) ALC + R + + role hierarchy ( H ) + inverse ( I ) + QNR ( Q ) = SHIQ SHIQ : OWL 의 기본이 되는 기술 로직 OWL DL ¼ SHIQ + nominals + XSD (i.e., SHOIQ (D)) OWL Lite ¼ SHIQ + functional restrictions + XSD (i.e., SHIF (D))
  • 13. 지식 베이스 ( 온톨로지 ) TBox 는 “스키마” 공리 (axiom) 의 집합 (sentences) {Lawyer v Person, HappyParent ´ Person u 8 hasChild.(Lawyer t 9 hasChild.Lawyer)} ABox 는 “데이터” 공리의 집합 (ground facts) {HappyParent(CheolSu), hasChild(CheolSu, YeongHui)} 지식 베이스 (KB) = TBox + ABox = 온톨로지
  • 14. 태블롵Ӛ즈 추론 (1) 온톨로지 추론 기술 로직의 태블롵Ӛ즈 ( Tableaux ) 추론 방법을 사용 지식 베이스 ( KB ) 만족가능성 문제 주요 온톨로지 추론 문제는 만족가능성 여부의 문제로 환원됨 예 ) KB K 에 관련해서 C v D iff K [ {x:(C u : D)} 가 만족가능하지 않음 태블롵Ӛ즈 알고리즘 일반적인 기술로직 시스템에서 지식 베이스의 만족가능성 또는 일관성을 결정하기 위해 사용 KB 의 공리 (axiom) 와 일관성을 가지는 하나의 모델을 구하는 알고리즘 ABox 공리들 (ground facts) 로부터 시작 Tableaux 확장 룰 (expansion rules) 을 더 이상 확장할 것이 없을 때까지 모든 연산자에 적용해 하나의 모델 (Tableau) 을 완성 충돌 (crash) 이 나타나면 만족 가능하지 않으며 없으면 만족가능
  • 15. 태블롵Ӛ즈 추론 (2) KB = { HappyParent = Person u 8 hasChild.( 9 hasChild.Lawyer t Lawyer) , HappyParent (Cheolsu), hasChild(Cheolsu,YeongHui), : Lawyer(YeongHui)} Cheolsu YeongHui hasChild HappyParent Person 8 hasChild.(Lawyer t 9 hasChild.Lawyer) Lawyer 1 2 3 Crash ABox 에 대한 그래프 생성 HappyParent TBox 공리에서 u 에 대한 확장 룰 적용 8 hasChild 에서 8 에 대한 확장 룰 적용 t 의 확장 룰 적용 후 9 hasChild.Lawyer 에 대한 확장 룰 적용 5 : Lawyer 1 2 3 4 9 hasChild.Lawyer t Lawyer 9 hasChild.Lawyer ? Laywer hasChild 4 t 룰의 오른쪽에서 지식 베이스의 충돌 발생 : 일관성이 없음 (Inconsistent KB) 5
  • 16. 태블롵Ӛ즈 추론 (3) 기술로직의 연산자에 대한 태블롵Ӛ즈 규칙 반복 적용 ( u , t , 8 , 9 등 현재 언어에서 지원하는 모든 연산자 ) 예 ) Student u Worker (CheolSu) ! Student(CheolSu) and Worker(CheolSu) 더 이상 적용할 규칙이 없거나 모순이 발생할 때까지 반복 적용 모순은 개념들간이 모순을 의미한다 ( 예 ) A(x) , : A(x) 어떤 룰은 결정적이지 않은 (nondeterministic) 특징을 가짐 이 경우 모든 경우를 탐색해야 함 예 ) t , 9 연산자 무한 루프의 경우 때문에 사이클 검사 ( 블로킹 ) 기능이 필요 예 ) { Person v 9 hasParent.Person, CheolSu:Person} Cheolsu ? hasParent Person 9 hasParent.Person Person ? Person hasParent BLOCK 9 hasParent.Person 9 hasParent.Person
  • 17. 결정 프로시저 ( Decision Procedure ) 태블롵Ӛ즈 알고리즘에서 룰을 적용한 후에 충돌 없는 그래프가 만들 어지는 것은 KB 의 만족가능성을 결정할 수 있는 것에 필요충분조건 사운드 (Sound) Tableaux 알고리즘을 적용해 완전히 확장된 그리고 충돌 없는 그래프가 만들어진다면 , KB 는 하나의 모델 (Tableau) 을 가질 수 있다 완전 (Complete) KB 에 대한 하나의 모델 (Tableau) 이 주어지면 , Tableaux 알고리즘을 적용해 완전히 확장된 그리고 충돌 없는 그래프를 만들 수 있다 중단 (Terminating) KB 의 모델 (Tableau) 에서 이름을 가지는 개체 , 트리의 외부차수 (out-degree), 트리의 깊이의 수가 한정된 개수를 가진다