Functional Subsumption in Feature Description Logic
ions made in this view is in the assumption that the input to the learning algorithm is given in a form of feature vectors. With the maturity of these models, though, it has become (again) clear that a key issue that needs to be addressed is that of “what are the features”, namely, how should domain elements be represented in a way that learning algorithms can effectively use them. This work focuses on this stage – the problem of mapping domain elements into representations that are useful as inputs to a learning algorithm. The process of re-representing domain elements, in a way that takes into account what is known (or previously learned) about the domain and the problem, is necessary in order to facilitate learning in complex situations, when learning requires exploiting the structural and relational information within the domain elements. Indeed, researchers and practitioners spend a significant portion of their time on the problem of feature engineering and a significant amount of computing cycles goes into this stage in the process. This computation is typically left unreported in research papers, where the starting point is usually after features have already been extracted but, clearly, are significant in applications. Mapping domain elements into representations that can be processed by learning algorithms (e.g., feature vectors), that is, extracting the relevant substructures and properties of the domain elements – typically done today in ad-hoc ways – might be computationally expensive and should be studied as an integral part of the learning process. The benefits of this integration are numerous, one of them being the possibility for kernels directly over structured examples, as in [5]. We argue, following [4], that the process of converting a domain element into a feature based representation is best viewed as an inference process, and we formalize it this way. At the heart of our approach is a knowledge representation language – Feature Description Logic (FDL) – that we use in order to represent both domain elements and potentially expressive “types” of features – along with Feature Generation Functions (FGFs), a mechanism to convert domain elements, given the features, and re-represent them in a way that can be used by general purpose learning algorithms. FDL is a specific Description Logic (DL), a knowledge representation that has been found useful in describing sets of individuals, or concepts , by specifying constraints which all members of the set must obey, and in establishing taxonomies involving those sets. DLs strike a good balance between expressivity and tractability, achieved by a careful choice of the types of constraints allowed. This choice makes description logics less expressive than full First Order Logic but expressive enough to allow efficient inference in structured relational domains. Of particular use for us will be subsumption, a standard inference task in DLs. A description C is said to subsume a description D if and only if all the individuals described by D must also be described by C. Within the FDL framework, examples can be richly structured objects composed by many individuals with relations among them. As in [4], we view examples as concept graphs, where nodes represent individuals with primitive Functional Subsumption in Feature Description Logic 3 Text: Mohammed Atta met with an Iraqi intelligence agent in Prague in April 2001. before person name(“Mohammed Atta”) gender(male)