With the advent of pervasive computing, particularly in a resource-limited environment where electrical devices such as alarm clocks, coffee makers, vehicles, and refrigerators search and reason over data generated by their operation, it is important that data is described in a form suitable for the machines to interpret and understand in a consistent manner. Semantic Web technologies could play a key role in bringing about the vision of a semantic-oriented pervasive computing environment. Nowadays various computer systems and applications use Semantic Web languages such as Web Ontology Language (OWL) as a foundation for representing and sharing information data of interest.
Automatic reasoning is the major benefit of using the data, i.e., Semantic Web ontologies, expressed by Semantic Web languages. The reasoning is a process of drawing an inference from the asserted information (i.e., axioms) in an ontology based on the well-known logical procedures, and this facilitates the machine-driven interpretation, integration, and validation of data. However, the resources necessary for reasoning increase exponentially with the size of ontologies under consideration. For an environment, where only limited computational resources are available, this exponential growth of processing requirements causes a scalability problem.
Real-time reasoning of semantic information with limited resources is a very important challenge in the pursuit of pervasive computing, particularly in resource-limited environments. For reasoning within some time bounds, it makes sense for the reasoner to trade correctness for computational efficiency by reducing the number of axioms initially considered. Given an ontology, the key problem we have investigated in this context is the choice of the fragment of given an ontology in order to maximize the reasoning correctness and, at the same time, the reasoning computation will finish within a given period of time.
In this dissertation, we study on a range of methods related to the problem of real-time ontology reasoning. This is the problem whereby the reasoner automatically trades correctness for a gain in computational efficiency in order to meet some time bounds.
With regard to the problem, we propose a method for choosing the ontology fragments of arbitrary size, most relevant to the given reasoning tasks (i.e., entailment), and develop an algorithm that determines the maximum fragment size that can be used to determine entailment within given time bounds.
We demonstrate that a description logic reasoner using our proposed methods exhibits excellent results in terms of both reasoning correctness and response time for various ontologies of different expressivities and sizes.
알람시계, 커피메이커, 자동차, 냉장고와 같은 기기들이 만들어낸 데이터를 찾고 추론하는 퍼베이시브 컴퓨팅 환경에서는 기계가 정보를 일관성 있게 해석하고 이해할 수 있는 형태로 기술하는 것이 중요하다. 온톨로지 랭귀지 및 추론기와 같은 시맨틱 웹 기술은 이러한 비전을 달성하는데 핵심적인 역할을 할 수 있다. 데이터를 Web Ontology Language (OWL)과 같은 시맨틱 웹 랭귀지로 표현하는 중요한 이유는 그 데이터 상에서 자동화된 추론을 수행할 수 있기 때문이다. 온톨로지 O에서 Axiom은 명확한 사실로 간주되는 전제이며 따라서 추론의 시작점이다. 하나의 Axiom 집합 O로부터 관심의 대상인 하나의 결론 q이 논리적으로 도출될 수 있는지를 확인(Entailment라 하며 $O\models q$라 표기함)하는 것은 주요한 추론작업이다.
Entailment 추론에 필요한 리소스는 추론에 고려되는 Axiom 수에 지수적으로 증가한다. 추론에 요구되는 계산량의 지수적 증가는 제한된 컴퓨팅 리소스를 가진 IoT가 추론을 할 수 없도록 한다. 이 경우 추론기가 추론에 고려할 Axiom의 수를 줄여 추론의 정확함을 계산상의 효율성과 맞바꿈 하는 것은 문제 해결을 위한 가능한 방법이 된다. 논문에서 연구하고자 하는 핵심 문제는 관심 있는 결론 q가 도출될 확률이 가장 높고 추론을 주어진 시간내에 완료할 수 있는 온톨로지 부분 $O^{’}\subseteq O$를 선택하는 것이다. 주어진 Entailment를 도출하는데 충분한 최소크기의 부분(i.e., Justification)를 찾는 방법 및 알고리즘이 제안되어 있지만 이를 계산하는 것은 최소한 Entailment 계산만큼 복잡하다. 온톨로지 재사용과 큰 규모의 온톨로지를 빠르게 처리하기 위한 목적으로 주어진 Signature에 관계된 부분을 추출하는 문제에 대한 방법이 연구되었다. 하나의 Axiom이 주어진 Signature에 관련이 있는 것인가를 결정하는데 있어 몇몇은 Axiom과 Signature의 구문적 중복이나 연결구조와 같은 직관적인 휴리스틱에 의존하는 반면 몇몇은 Modularity와 같은 논리적으로 기술된 개념에 의거하여 관련성을 결정한다.
휴리스틱에 의존하는 알고리즘들은 관계된 부분을 빠른 속도로 추출하지만 추출된 결과에 대한 논리적 보장을 하지 못한다. 즉, 추출한 결과가 Entailment 추론에 실제로는 관련이 없는 Axiom을 포함할 수 있으며 (False positive case) 반대로 관련된 Axiom을 빠뜨릴 수도 있다 (False negative case). Modularity 개념에 따라 추출된 부분은 크기도 작을 뿐만 아니라 추출된 결과에 대해 유용한 논리적 특성을 보장한다. 예를 들면, 주어진 Signature를 기반으로 추출된 부분 (모듈이라 불림)은 Signature에 관련된 어떠한 논리적 결과도 잃지 않는다는 것을 보장한다. 하지만 추출된 모듈이 False positive 혹은 Negative를 포함하고 있는지, 있다면 어느 정도가 일반적으로 예상되는지에 대한 사실은 모듈이 보장하는 특성의 정의들로부터 쉽게 유추되지 않는다. 임의의 크기의 부분을 추출하는데 중요함에도 불구하고 어떠한 관련 연구도 추출된 부분에 속하는 Axiom들에 대해서 우선 순위화 하지는 않는다.
우리가 온톨로지 부분 선택 문제에 대해 제안하는 방식은 주어진 시간내 추론계산이 가능한 부분의 최대크기 (Maximum Fragment Size)를 예측하여 그만큼의 가장 관련된 Axiom들로 구성된 부분를 선택하는 것이다. 가능한 최대크기를 예측하는 이유는 더 큰 부분으로 추론할수록 Entailment가 성립될 확률이 높아지기 때문이다. 주어진 Entailment를 성립시키는데 가장 관련된 임의 크기의 부분을 추출하는 방법으로 MOSS를 제안한다. 우선 추론에 관련이 없다는 것이 보장되는 대부분의 Axiom을 모듈을 추출함으로써 걸러내고 추론문제와 Axiom 사이의 Signature에 기반한 관련성을 사용하여 관련된 정도에 따라 Axiom들을 우선순위화 하고 가장 관련된 임의 개수의 Axiom들을 선택하는 방식을 제안한다. 이와더불어, 추론에 사용할 부분의 최대크기를 결정하는 알고리즘으로 TiMax를 제안한다. TiMax는 추론시간은 사용할 부분의 크기가 클수록 크다는 가정하에 이전의 추론 기록을 바탕으로 이진 검색(Binary search) 증가방식을 사용하여 최대크기를 빠르게 결정하고 추적한다.
다양한 실험을 통해 아주 작은 온톨로지 부분만으로도 높은 정확함을 보이는 추론이 가능하다는 결론을 내렸다. 이것은 추론 계산복잡도를 낮춰 추론에 필요한 리소스를 획기적으로 줄여 추론의 확장성을 높인다는 것을 확인했다. 이 결과는 추론의 정확함을 추론의 확장성과 맞교환하는 방식이 높은 효과를 보일 수 있음을 시사한다. 또한 추론 시간은 온톨로지 크기에 비례한다는 단순한 가정이 시간내에 추론계산 가능한 부분 크기를 결정하는데 유효하다는 결론을 내릴 수 있다.
