While all kinds of mixed data---from personal data, over panel and scientific data, to public and commercial data---are collected and stored, building probabilistic graphical models for these hybrid domains becomes more difficult. Users spend significant amounts of time in identifying the parametric form of the random variables (Gaussian, Poisson, Logit, etc.) involved and learning the mixed models. To make this difficult task easier, we propose the first trainable probabilistic deep architecture for hybrid domains that features tractable queries. It is based on Sum-Product Networks (SPNs) with piecewise polynomial leaf distributions together with novel nonparametric decomposition and conditioning steps using the Hirschfeld-Gebelein-Renyi Maximum Correlation Coefficient. This relieves the user from deciding a-priori the parametric form of the random variables but is still expressive enough to effectively approximate any distribution and permits efficient learning and inference.Our experiments show that the architecture, called Mixed SPNs, can indeed capture complex distributions across a wide range of hybrid domains.

Sum-Product Networks (SPNs) are a deep probabilistic architecture that up to now has been successfully employed for tractable inference. Here, we extend their scope towards unsupervised representation learning: we encode samples into continuous and categorical embeddings and show that they can also be decoded back into the original input space by leveraging MPE inference. We characterize when this Sum-Product Autoencoding (SPAE) leads to equivalent reconstructions and extend it towards dealing with missing embedding information. Our experimental results on several multi-label classification problems demonstrate that SPAE is competitive with state-of-the-art autoencoder architectures, even if the SPNs were never trained to reconstruct their inputs.

The availability on the Internet of huge amounts of blog posts, messages and comments allows to study the attitude of people on various topics. Sentiment Analysis, Opinion Mining and Emotion Analysis denote the area of research in Computer Science aimed at studying, analyzing and classifying text documents based on the underlying opinions expressed by their authors on various topics. While this is a tough task, because it is related to psychological aspects that are not always immediately evident in the lexical and syntactical aspects of the sentences, its importance may be paramount for several applications such as market analysis, political polls, etc. Fundamental pre-processing techniques for this task come from the area of Natural Language Processing, which may pose additional problems when the language of interest is different than English, and thus less (or less reliable) resources are available to extract the needed data from the text. This paper studies the performance of Sentiment Analysis, seen as a Text Categorization task, depending on the use of different classifiers and different features. While the approach is general, we focus on texts in Italian. The outcomes suggest which experimental settings can be most profitably used in this landscape, and show that significantly good results can be obtained.

Knowledge Graphs (KGs) are a widely used formalism for representing knowledge in the Web of Data. We focus on the problem of link prediction, i.e. predicting missing links in large knowledge graphs, so to discover new facts about the world. Representation learning models that embed entities and relation types in continuous vector spaces recently were used to achieve new state-of-the-art link prediction results. A limiting factor in these models is that the process of learning the optimal embedding vectors can be really time-consuming, and might even require days of computations for large KGs. In this work, we propose a principled method for sensibly reducing the learning time, while converging to more accurate link prediction models. Furthermore, we employ the proposed method for training and evaluating a set of novel and scalable models. Our extensive evaluations show significant improvements over state-of-the-art link prediction methods on several datasets.

Detecting the reading order among the layout components of a document's page is fundamental to ensure effectiveness or even applicability of subsequent content extraction steps. While in single-column documents the reading flow can be straightforwardly determined, in more complex documents the task may become very hard. This paper proposes an automatic strategy for identifying the correct reading order of a document page's components based on abstract argumentation. The technique is unsupervised, and works on any kind of document based only on general assumptions about how humans behave when reading documents. Experimental results show that it is effective in more complex cases, and requires less background knowledge, than previous solutions that have been proposed in the literature.

The current tools to create OWL-S annotations have been designed starting from the knowledge engineer’s point of view. Unfortunately, the formalisms underlying Semantic Web languages are often incomprehensible to the developers of Web services. To bridge this gap, it is desirable that developers are provided with suitable tools that do not necessarily require knowledge of these languages in order to create annotations on Web services. With reference to some characteristics of the involved technologies, this work addresses these issues, proposing guidelines that can improve the annotation activity of Web service developers. Following these guidelines, we also designed a tool that allows a Web service developer to annotate Web services without requiring him to have a deep knowledge of Semantic Web languages. A prototype of such a tool is presented and discussed in this paper.

We consider the problem of predicting missing class-memberships and property values of individual resources in Web ontologies. We first identify which relations tend to link similar individuals by means of a finite-set Gaussian Process regression model, and then efficiently propagate knowledge about individuals across their relations. Our experimental evaluation demonstrates the effectiveness of the proposed method.

In Artificial Intelligence with Coalition Structure Generation (CSG) one refers to those cooperative complex problems that require to find an optimal partition (maximizing a social welfare) of a set of entities involved in a system. The solution of the CSG problem finds applications in many fields such as Machine Learning (set covering machines, clustering), Data Mining (decision tree, discretization), Graph Theory, Natural Language Processing (aggregation), Semantic Web (service composition), and Bioinformatics. The problem of finding the optimal coalition structure is NP-complete. In this paper we present a greedy adaptive search procedure (GRASP) with path-relinking to efficiently search the space of coalition structures. Experiments and comparisons to other algorithms prove the validity of the proposed method in solving this hard combinatorial problem.

No abstract available.

Digital Libraries collect, organize and provide to end users large quantities of selected documents. While these documents come in a variety of formats, it is desirable that they are delivered to final users in a uniform way. Web formats are a suitable choice for this purpose. While Web documents are very flexible as to layout presentation, that is determined at runtime by the interpreter, documents coming from a library should preserve their original layout when displayed to final users. Using raster images would not allow the user to access the actual content of the document's components (text and images). This paper presents a technique to render in an HTML file the original layout of a document, preserving the peculiarity of its components (text, images, formulas, tables, algorithms). It builds on the DoMInUS framework, that can process documents in several source formats.

Tables are extremely important components of documents, because they bear very informative content in a compact and structured way. Being able to understand a table's internal organization would allow to extract and reuse the data they contain. This can be reduced to recognizing critical cells only. Since purely algorithmic approaches are unable to deal with the many different table layouts designed to represent particular kinds of information and/or particular perspectives on them, Machine Learning may represent an effective solution. On one hand, the spatial organization of tables puts a strong emphasis on the relationships among cells, on the other, the extreme variability in style, size, and aims of tables requires flexible approaches. This paper proposes the exploitation of a Statistical Relational Learning approach, that is able to model the complex spatial relationships involved in a table structure, by mixing the power of a relational representation formalism with the flexibility of a statistical learning tool. Experiments on a real-world dataset are reported both for single cell classification and for overall table structure recognition, whose results prove the validity of the proposed approach.

Standardized processes are important for correctly carrying out activities in an organization. Often the procedures they describe are already in operation, and the need is to understand and formalize them in a model that can support their analysis, replication and enforcement. Manually building these models is complex, costly and error-prone. Hence, the interest in automatically learning them from examples of actual procedures. Desirable options are incrementality in learning and adapting the models, and the ability to express triggers and conditions on the tasks that make up the workflow. This paper proposes a framework based on First-Order Logic that solves many shortcomings of previous approaches to this problem in the literature, allowing to deal with complex domains in a powerful and flexible way. Indeed, First-Order Logic provides a single, comprehensive and expressive representation and manipulation environment for supporting all of the above requirements. A purposely devised experimental evaluation confirms the effectiveness and efficiency of the proposed solution.

Metabolomics is increasingly becoming an important field. The fundamental task in this area is to measure and interpret complex time and condition dependent parameters such as the activity or flux of metabolites in cells, their concentration, tissues elements and other biosamples. The careful study of all these elements has led to important insights in the functioning of metabolism. Recently, however, there is a growing interest towards an intagrated approach to studying biological systems. This is the main goal in Systems Biology where a combined investigation of several components of a biological system is thought to produce a thorough understanding of such systems. Metabolic networks are not only structurally complex but behave also in a stochastic fashion. Therefore, it is necessary to express structure and handle uncertainty to construct complete dynamics of these networks. In this paper we describe how stochastic modeling and simulation can be performed in a symbolic-statistical machine learning (ML) framework. We show that symbolic ML deals with structural and relational complexity while statistical ML provides principled approaches to uncertainty modeling. Learning is used to analyze traces of biochemical reactions and model the dynamicity through parameter learning, while inference is used to produce stochastic simulation of the network.

We present high performing SLS algorithms for learning and inference in Markov Logic Networks (MLNs). MLNs are a state-of-the-art representation formalism that integrates first-order logic and probability. Learning MLNs structure is hard due to the combinatorial space of candidates caused by the expressive power of first-order logic. We present current work on the development of algorithms for learning MLNs, based on the Iterated Local Search (ILS) metaheuristic. Experiments in real-world domains show that the proposed approach improves accuracy and learning time over the existing state-of-the-art algorithms. Moreover, MAP and conditional inference in MLNs are hard computational tasks too. This paper presents two algorithms for these tasks based on the Iterated Robust Tabu Search (IRoTS) schema. The first algorithm performs MAP inference by performing a RoTS search within a ILS iteration. Extensive experiments show that it improves over the state-of the-art algorithm in terms of solution quality and inference times. The second algorithm combines IRoTS with simulated annealing for conditional inference and we show through experiments that it is faster than the current state-of-the-art algorithm maintaining the same inference quality.

Information Retrieval in large digital document repositories is at the same time a hard and crucial task. While the primary type of information available in documents is usually text, images play a very important role because they pictorially describe concepts that are dealt with in the document. Unfortunately, the semantic gap separating such a visual content from the underlying meaning is very wide. Additionally image processing techniques are usually very demanding in computational resources. Hence, only recently the area of Content-Based Image Retrieval has gained more attention. In this paper we describe a new technique to identify known objects in a picture based on a comparison of the shapes to known models. The comparison works by progressive approximations to save computational resources, and relies on novel algorithmic and representational solutions to improve preliminary shape extraction.

Document layout analysis is crucial in the automatic document processing workflow, because its outcome affects all subsequent processing steps. A first problem concerns the possibility of dealing not only with documents having easy layout, but with so-called non-Manhattan layout documents as well. Another problem is that most available techniques can be applied to scanned document, due to the emphasis in previous decades being put on legacy documents digitization. Conversely, nowadays most documents come directly in digital format, and thus new techniques must be developed. A famous approach proposed in the literature for layout analysis was the RLSA, suitable to scanned black&white images and based the application of Run Length Smoothing and the AND logical operator. A recent variant thereof is based on the application of the OR operator, for which reason has been called RLSO. It exploits a bottom-up approach that proved able to handle even non-Manhattan layouts, on both scanned and natively digital documents. Like RLSA, it is based on the definition of thresholds for the smoothing operator, but the different approach requires different criteria than those that work in RLSA to define proper values. Since this is a hard and unnatural task for an (even expert) user, this paper proposes a technique to automatically define such thresholds for each single document, based on the distribution of spacing therein. Application on selected samples of documents, that aimed at covering a significant landscape of real cases, revealed that the approach is satisfactory for documents characterized by the use of a uniform text font size. It can provide a useful basis also for handling more complex cases.

In the context of knowledge bases expressed in Description Logics, a method for learning functions that can predict the ranking of resources encoding some preference criteria implicitly encoded through examples of rated individuals. The method relies on a kernelized version of the PERCEPTRON RANKING algorithm which is suitable for batch but also online problem settings.

The recent explosion in Internet usage and the growing amount of digital images caused by the more and more ubiquitous presence of digital cameras has created a demand for effective and flexible techniques for automatic image retrieval. As the volume of the data increases, memory and processing requirements need to correspondingly increase at the same rapid pace, and this is often prohibitively expensive. Image collections on this scale make performing even the most common and simple image processing and machine learning tasks non trivial. In this paper we present a method to reduce the computational complexity of a widely known method for image indexing and retrieval based on a second order statistical measure. The aim of the paper is twofold: Q1) is it possible to efficiently extract an approximate distribution of the image features with a resulting low error? Q2) how the resulting approximate distribution affects the similarity-based accuracy? In particular, we propose a sampling method to approximate the distribution of correlograms, adopting a Monte Carlo approach to compute the distribution on a subset of pixels uniformly sampled from the original image. A further variant is to sample the neighborhood of each pixel too. Validation on the Caltech 101 dataset proved that the proposed approximate distribution, obtained with a considerable decrease of the computational time, has an error very low when compared to the exact distribution. Result obtained in the second experiment on a similarity-based ranking task are encouraging.

This work focusses on the problem of clustering resources contained in knowledge bases represented throughmulti-relational standard languages that are typical for the context of the Semantic Web, and ultimately founded in Description Logics. The proposed solution relies on effective and language-independent dissimilarity measures that are based on a finite number of dimensions corresponding to a committee of discriminating features, that stands for a context, represented by concept descriptions in Description Logics. The proposed clustering algorithm expresses the possible clusterings in tuples of central elements: in this categorical setting, we resort to the notion of medoid, w.r.t. the given metric. These centers are iteratively adjusted following the rationale of fuzzy clustering approach, i.e. one where the membership to each cluster is not deterministic but graded, ranging in the unit interval. This better copes with the inherent uncertainty of the knowledge bases expressed in Description Logics which adopt an open-world semantics. An extensive experimentation with a number of ontologies proves the feasibility of our method and its effectiveness in terms of major clustering validity indices.

Layout analysis is a fundamental step in automatic document processing. Many different techniques have been proposed to perform this task. Some follow a top-down approach: they start by identifying the high level components of the page structure and then recursively split them until basic blocks are found. On the other hand, bottom-up approaches start with the smallest elements (e.g., the pixels in case of digitized document) and then recursively merge them into higher level components. A first limitation of such methods is that most of them are designed to deal only with digitized documents and hence are not applicable to native digital documents which are nowadays pervasive. Furthermore, top-down and most of bottom-up methods are able to process Manhattan layout documents only. In this work, we propose a general bottom-up strategy to tackle the layout analysis of (possibly) non-Manhattan documents, and two specializations of it to handle both bitmap and PS/PDF sources. It was successfully embedded and tested in the DOMINUS document management system.

We present a classification method, founded in the instance-based learning and the disjunctive version space approach, for performing approximate retrieval from knowledge bases expressed in Description Logics. It is able to supply answers, even though they are not logically entailed by the knowledge base (e.g. because of its incompleteness or when there are inconsistent assertions). Moreover, the method may also induce new knowledge that can be employed to make the ontology population task semiautomatic. The method has been experimentally tested showing that it is sound and effective.

We present a classification method, founded in the instance-based learning and the disjunctive version space approach, for performing approximate retrieval from knowledge bases expressed in Description Logics. The method supplies answers even if the knowledge base of reference is inconsistent or incomplete. Moreover, the method may also induce new knowledge that can be suggested to the knowledge engineer, thus making the ontology population task semi-automatic.

First-Order Logic formulæ are a powerful representation formalism characterized by the use of relations, that cause serious computational problems due to the phenomenon of indeterminacy (various portions of one description are possibly mapped in different ways onto another description). Being able to identify the correct corresponding parts of two descriptions would help to tackle the problem: hence, the need for a framework for the comparison and similarity assessment. This could have many applications in Artificial Intelligence: guiding subsumption procedures and theory revision systems, implementing flexible matching, supporting instance-based learning and conceptual clustering. Unfortunately, few works on this subject are available in the literature. This paper focuses on Horn clauses, which are the basis for the Logic Programming paradigm, and proposes a novel similarity formula and evaluation criteria for identifying the descriptions components that are more similar and hence more likely to correspond to each other, based only on their syntactic structure. Experiments on real-world datasets prove the effectiveness of the proposal, and the efficiency of the corresponding implementation in the above tasks.

The tasks of resource classification and retrieval from knowledge bases in the Semantic Web are the basis for a lot of important applications. In order to overcome the limitations of purely deductive approaches to deal with these tasks, inductive (instance-based) methods have been introduced as efficient and noise-tolerant alternatives. In this paper we propose an original method based on a non-parametric learning scheme: the Reduced Coulomb Energy (RCE) Network. The method requires a limited training effort but it turns out to be very effective during the classification phase. Casting retrieval as the problem of assessing the classmembership of individuals w.r.t. the query concepts, we propose an extension of a classification algorithm using RCE networks based on an entropic similarity measure for OWL. Experimentally we show that the performance of the resulting inductive classifier is comparable with the one of a standard reasoner and often more efficient than with other inductive approaches. Moreover, we show that new knowledge (not logically derivable) is induced and the likelihood of the answers may be provided.

Many real-world applications of AI require both probability and first-order logic to deal with uncertainty and structural complexity. Logical AI has focused mainly on handling complexity, and statistical AI on handling uncertainty. Markov Logic Networks (MLNs) are a powerful representation that combine Markov Networks (MNs) and first-order logic by attaching weights to first-order formulas and viewing these as templates for features of MNs. State-of-the-art structure learning algorithms of MLNs maximize the likelihood of a relational database by performing a greedy search in the space of candidates. This can lead to suboptimal results because of the incapability of these approaches to escape local optima. Moreover, due to the combinatorially explosive space of potential candidates these methods are computationally prohibitive. We propose a novel algorithm for learning MLNs structure, based on the Iterated Local Search (ILS) metaheuristic that explores the space of structures through a biased sampling of the set of local optima. The algorithm focuses the search not on the full space of solutions but on a smaller subspace defined by the solutions that are locally optimal for the optimization engine. We show through experiments in two real-world domains that the proposed approach improves accuracy and learning time over the existing state-of-the-art algorithms.

In real-world digital libraries, artificial intelligence techniques are essential for tackling the automatic document processing task with sufficient flexibility. The great variability in document kind, content and shape requires powerful representation formalisms to catch all the domain complexity. The continuous flow of new documents requires adaptable techniques that can progressively adjust the acquired knowledge on documents as long as new evidence becomes available, even extending if needed the set of recognized document types. Both these issues have not yet been thoroughly studied. This paper presents an incremental first-order logic learning framework for automatically dealing with various kinds of evolution in digital repositories content: evolution in the definition of class definitions, evolution in the set of known classes and evolution by addition of new unknown classes. Experiments show that the approach can be applied to real-world.

We present a method based on clustering techniques to detect possible/probable novel concepts or concept drift in a Description Logics knowledge base. The method exploits a semi-distance measure defined for individuals, that is based on a finite number of dimensions corresponding to a committee of discriminating features (concept descriptions). A maximally discriminating group of features is obtained with a randomized optimization method. In the algorithm, the possible clusterings are represented as medoids (w.r.t. the given metric) of variable length. The number of clusters is not required as a parameter, the method is able to find an optimal choice by means of evolutionary operators and a proper fitness function. An experimentation proves the feasibility of our method and its effectiveness in terms of clustering validity indices. With a supervised learning phase, each cluster can be assigned with a refined or newly constructed intensional definition expressed in the adopted language.

We present an evolutionary clustering method which can be applied to multi-relational knowledge bases storing semantic resource annotations expressed in the standard languages for the Semantic Web. The method exploits an effective and language-independent semi-distance measure defined for the space of individual resources, that is based on a finite number of dimensions corresponding to a committee of features represented by a group of concept descriptions (discriminating features). We show how to obtain a maximally discriminating group of features through a feature construction method based on genetic programming. The algorithm represents the possible clusterings as strings of central elements (medoids, w.r.t. the given metric) of variable length. Hence, the number of clusters is not needed as a parameter since the method can optimize it by means of the mutation operators and of a proper fitness function. We also show how to assign each cluster with a newly constructed intensional definition in the employed concept language. An experimentation with some ontologies proves the feasibility of our method and its effectiveness in terms of clustering validity indices.

Organizing large repositories spread throughout the most diverse Web sites rises the problem of effective storage and efficient retrieval of documents. This can be obtained by selectively extracting from them the significant textual information, contained in peculiar layout components, that in turn depend on the identification of the correct document class. The continuous flow of new and different documents in a weakly structured environment like the Web calls for in- crementality, as the ability to continuously update or revise a faulty knowledge previously acquired, while the need to express structural relations among layout components suggest the exploitation of a powerful and symbolic representation language. This paper proposes the application of incremental first-order logic learning techniques in the document layout preprocessing steps, supported by good results obtained in experiments on a real dataset.

Digital repositories raise the need for an effective and efficient retrieval of the stored material. In this paper, we propose the intensive application of intelligent techniques to the steps of document layout analysis, document image classification and understanding on digital documents. Specifically, the complex interrelation existing among layout components, that are fundamental to assign them the proper semantic role, suggest the exploitation of first-order representations in some learning steps. Results obtained in a prototypical system for scientific conference management prove that the proposed approach can be beneficial both for the layout recognition and for the selection of interesting components of the document, from which extracting the text for categorizing the document according to its topic.

Model trees are an extension of regression trees that associate leaves with multiple regression models. In this paper, a method for the data-driven construction of model trees is presented, namely, the Stepwise Model Tree Induction (SMOTI) method. Its main characteristic is the induction of trees with two types of nodes: regression nodes, which perform only straight-line regression, and splitting nodes, which partition the feature space. The multiple linear model associated with each leaf is then built stepwise by combining straight-line regressions reported along the path from the root to the leaf. In this way, internal regression nodes contribute to the definition of multiple models and have a "global" effect, while straight-line regressions at leaves have only "local" effects. Experimental results on artificially generated data sets show that SMOTI outperforms two model tree induction systems, M5' and RETIS, in accuracy. Results on benchmark data sets used for studies on both regression and model trees show that SMOTI performs better than RETIS in accuracy, while it is not possible to draw statistically significant conclusions on the comparison with M5'. Model trees induced by SMOTI are generally simple and easily interpretable and their analysis often reveals interesting patterns.

In this paper, a machine learning approach to support the user during the correction of the layout analysis is proposed. Layout analysis is the process of extracting a hierarchical structure describing the layout of a page. In our approach, the layout analysis is performed in two steps: firstly, the global analysis determines possible areas containing paragraphs, sections, columns, figures and tables, and secondly, the local analysis groups together blocks that possibly fall within the same area. The result of the local analysis process strongly depends on the quality of the results of the first step. We investigate the possibility of supporting the user during the correction of the results of the global analysis. This is done by allowing the user to correct the results of the global analysis and then by learning rules for layout correction from the sequence of user actions. Experimental results on a set of multi-page documents are reported and commented.

Document image understanding denotes the recognition of semantically relevant components in the layout extracted from a document image. This recognition process is based on some visual models, whose manual specification can be a highly demanding task. In order to automatically acquire these models, we propose the application of machine learning techniques. Problems raised by possible dependencies between concepts to be learned are illustrated and solved with a computational strategy based on the separate-and-parallel-conquer search. The approach is tested on a set of real multi-page documents processed by the system WISDOM++. New results confirm the validity of the proposed strategy and show some limits of the learning system used in this work.

WISDOM++ is a document analysis system whose main design requirements are real-time user interaction and adaptivity. This paper presents the two-phased skew estimation algorithm and the adaptive document block segmentation and classification techniques. An evaluation of the performance of some of these tasks is also conducted according to a benchmarking procedure.

This paper presents a prototypical digital library service. It integrates machine learning tools and techniques in order to make effective, efficient and economically feasible the process of capturing the information that should be stored and indexed by content in the digital library. Infact, information capture is one of the main bottleneck when building a digital library, since it involves complex pattern recognition problems, such as document analysis, classification and understanding. Experimental results show that learning systems can solve effectively and efficiently these problems.

In this paper, we address the problem of retrospectively pruning decision trees induced from data, according to a top-down approach. This problem has received considerable attention in the areas of pattern recognition and machine learning, and many distinct methods have been proposed in literature. We make a comparative study of six well-known pruning methods with the aim of understanding their theoretical foundations, their computational complexity, and the strengths and weaknesses of their formulation. Comments on the characteristics of each method are empirically supported. In particular, a wide experimentation performed on several data sets leads us to opposite conclusions on the predictive accuracy of simplified trees from some drawn in the literature. We attribute this divergence to differences in experimental designs. Finally, we prove and make use of a property of the reduced error pruning method to obtain an objective evaluation of the tendency to overprune/underprune observed in each method.

In this paper, we present a hybrid approach to the problem of the document analysis in which the document image is segmented by means of a top-down technique and then basic blocks are grouped bottom-up in order to form complex layout components. In this latter process, called layout analysis, only generic knowledge on typesetting conventions is exploited. Such knowledge is independent of the particular class of processed documents and turns out to be valuable for a wide range of documents. Preliminary results of the layout analysis system LEX (Layout EXpert) show the methodological validity of this approach.

A study on the possibility of adopting a supervised inductive learning approach to the problem of document understanding is presented. A representation language used to describe a page layout is introduced and the opportunity of extending such a language by means of intentionally defined predicates is discussed. Experimental results obtained by using a well-known learning system, FOCL, are presented. They confirm the exigency of redefining the problem of document understanding in terms of a new strategy of supervised inductive learning, called contextual learning. Some experiments in which a dependence hierarchy between concepts is defined show that contextual rules increase predictive accuracy and decrease learning time for labeling problems like document understanding.>

A definition of distance measure between structural descriptions that is based on a probabilistic interpretation of the matching predicate is proposed. It aims at coping with the problem of classification when noise causes both local and structural deformations. The distance measure is defined according to a top-down evaluation scheme: distance between disjunctions of conjuncts, conjunctions, and literals. At the lowest level, the similarity between a feature value in the pattern model (G) and the corresponding value in the observation (Ex) is defined as the probability of observing a greater distortion. The classification problem is approached by means of a multilayered framework in which the cases of single perfect match, no perfect match, and multiple perfect match are treated differently. A plausible solution for the problem of completing the attribute and structure spaces, based on the probabilistic approach, is also given. A comparison with other related works and an application in the domain of layout-based document recognition are presented.>

A novel approach to automatic classification of digitized office documents based on the inductive generalization of their layout style, is presented. It is supported by the observation that for a number of printed documents it is possible to find a set of relevant and invariant layout features. These are geometrical characteristics automatically detected through a segmentation and layout analysis process. The learning step, in which significant examples of document classes are used to train the classification system, involves the novel idea of integrating parametric (numerical) and conceptual (symbolic) learning methods.>