Search

Semantic labeling of large volumes of image and video archives is difficult, if not impossible, with the traditional methods due to the huge amount of human effort required for manual labeling used in a supervised setting. Recently, semi-supervised techniques which make use of annotated image and video collections are proposed as an alternative to reduce the human effort. In this direction, different techniques, which are mostly adapted from information retrieval literature, are applied to learn the unknown one-to-one associations between visual structures and semantic descriptions. When the links are learned, the range of application areas is wide including better retrieval and automatic annotation of images and videos, labeling of image regions as a way of large-scale object recognition and association of names with faces as a way of large-scale face recognition. In this chapter, after reviewing and discussing a variety of related studies, we present two methods in detail, namely, the so called "translation approach" which translates the visual structures to semantic descriptors using the idea of statistical machine translation techniques, and another approach which finds the densest component of a graph corresponding to the largest group of similar visual structures associated with a semantic description. [ABSTRACT FROM AUTHOR]

In comparison with the classic query-by-example paradigm, the "mental image search" paradigm lifts the strong assumption that the user has a relevant example at hand to start the search. In this chapter, we review different methods that implement this paradigm, originating from both the content-based image retrieval and the object recognition fields. In particular, we present two complementary methods. The first one allows the user to reach the target mental image by relevance feedback, using a Bayesian inference. The second one lets the user specify the mental image visual composition from an automatically generated visual thesaurus of segmented regions. In this scenario, the user formulates the query with an explicit representation of the image content, as opposed to the first scenario which accommodates an implicit representation. In terms of usage, we will show that the second approach is particularly suitable when the mental image has a well-defined visual composition. On the other hand, the Bayesian approach can handle more "semantic" queries, such as emotions for which the visual characterization is more implicit. [ABSTRACT FROM AUTHOR]

In recent years there has been a growing interest in improving all aspects of the interaction between humans and computers with the clear goal of achieving a natural interaction, similar to the way human-human interaction takes place. The most expressive way humans display emotions is through facial expressions. Humans detect and interpret faces and facial expressions in a scene with little or no effort. Still, development of an automated system that accomplishes this task is rather difficult. There are several related problems: detection of an image segment as a face, extraction of the facial expression information, and classification of the expression (e.g., in emotion categories). A system that performs these operations accurately and in real time would be a major step forward in achieving a human-like interaction between the man and machine. In this chapter, we present several machine learning algorithms applied to face analysis and stress the importance of learning the structure of Bayesian network classifiers when they are applied to face and facial expression analysis. [ABSTRACT FROM AUTHOR]

Content-based image retrieval (CBIR) has attracted a lot of interest in recent years. When considering visual information retrieval in image databases, many difficulties arise. Learning is definitively considered as a very interesting issue to boost the efficiency of information retrieval systems. Different strategies, such as offline supervised learning or semi-supervised learning, have been proposed. Active learning methods have been considered with an increased interest in the statistical learning community. Initially developed in a classification framework, a lot of extensions are now proposed to handle multimedia applications. The purpose of this chapter is to present an overview of the online image retrieval systems based on supervised classification techniques. This chapter also provides algorithms in a statistical framework to extend active learning strategies for online content-based image retrieval. [ABSTRACT FROM AUTHOR]

In this chapter we will introduce a new effective framework for learning an object detector. The main idea is to minimize the manual effort when learning a classifier and to combine the power of a discriminative classifier with the robustness of a generative model. Starting with motion detection an initial set of positive examples is obtained by analyzing the geometry (aspect ratio) of the motion blobs. Using these samples a discriminative classifier is trained using an online version of AdaBoost. In fact, applying this classifier nearly all objects are detected but there is a great number of false positives. Thus, we apply a generative classifier to verify the obtained detections and to decide if a detected patch represents the object of interest or not. As we have a huge amount of data (video stream) we can be very conservative and use only patches for (positive or negative) updates if we are very confident about our decision. Applying this update rules, an incrementally better classifier is obtained without any user interaction. Moreover, an already trained classifier can be retrained online and can therefore easily be adapted to a completely different scene. We demonstrate the framework on different scenarios including pedestrian and car detection. [ABSTRACT FROM AUTHOR]

When data objects that are the subject of analysis using machine learning techniques are described by a large number of features (i.e. the data are high dimension) it is often beneficial to reduce the dimension of the data. Dimension reduction can be beneficial not only for reasons of computational efficiency but also because it can improve the accuracy of the analysis. The set of techniques that can be employed for dimension reduction can be partitioned in two important ways; they can be separated into techniques that apply to supervised or unsupervised learning and into techniques that either entail feature selection or feature extraction. In this chapter an overview of dimension reduction techniques based on this organization is presented and the important techniques in each category are described. [ABSTRACT FROM AUTHOR]

Supervised learning accounts for a lot of research activity in machine learning and many supervised learning techniques have found application in the processing of multimedia content. The defining characteristic of supervised learning is the availability of annotated training data. The name invokes the idea of a ‘supervisor' that instructs the learning system on the labels to associate with training examples. Typically these labels are class labels in classification problems. Supervised learning algorithms induce models from these training data and these models can be used to classify other unlabelled data. In this chapter we ground or analysis of supervised learning on the theory of risk minimization. We provide an overview of support vector machines and nearest neighbour classifiers~- probably the two most popular supervised learning techniques employed in multimedia research. [ABSTRACT FROM AUTHOR]

Unsupervised learning is very important in the processing of multimedia content as clustering or partitioning of data in the absence of class labels is often a requirement. This chapter begins with a review of the classic clustering techniques of k-means clustering and hierarchical clustering. Modern advances in clustering are covered with an analysis of kernel-based clustering and spectral clustering. One of the most popular unsupervised learning techniques for processing multimedia content is the self-organizing map, so a review of self-organizing maps and variants is presented in this chapter. The absence of class labels in unsupervised learning makes the question of evaluation and cluster quality assessment more complicated than in supervised learning. So this chapter also includes a comprehensive analysis of cluster validity assessment techniques. [ABSTRACT FROM AUTHOR]

Bayesian methods are a class of statistical methods that have some appealing properties for solving problems in machine learning, particularly when the process being modelled has uncertain or random aspects. In this chapter we look at the mathematical and philosophical basis for Bayesian methods and how they relate to machine learning problems in multimedia. We also discuss the notion of decision theory, for making decisions under uncertainty, that is closely related to Bayesian methods. The numerical methods needed to implement Bayesian solutions are also discussed. Two specific applications of the Bayesian approach that are often used in machine learning - naïve Bayes and Bayesian networks - are then described in more detail. [ABSTRACT FROM AUTHOR]

Finding hidden temporal structures from event sequences is a difficult task, particularly when events occur irregularly over time and temporal dependencies may exist in a long time horizon. The tasks involved are not only to find event patterns represented in the form of temporal orders, but more importantly to find patterns that are described with precise time conditions and rules that can be applied to predict when a future event will occur. Recent study has shown that a new approach based on learning temporal regions is a good solution for this problem. This paper investigates this approach in a greater depth and makes several improvements. It introduces multiple rule selection methods to better uncover hidden relations. It also introduces heuristic rule pruning methods to speed up search to solve large-scale problems. Experimental results are presented which show the effectiveness of the new methods. [ABSTRACT FROM AUTHOR]

Data clustering and association rules discovery are two related problems in data mining. In this paper, we propose to integrate these two techniques using the frequent concept lattice data structure — a formal conceptual model that can be used to identify similarities among a set of objects based on their frequent attributes (frequent items). Experimental results show that clusterings and association rules are generated efficiently from the frequent concept lattice, since response time after lattice construction is measured almost in seconds. [ABSTRACT FROM AUTHOR]

This paper presents a new method that deals with a supervised learning task usually known as multivariate regression. The main distinguishing feature of this new technique is the use of a clustering method to obtain sub-sets of the training data before the learning phase. After this "resampling" process a different regression model is fitted to each found cluster. We call the resulting method clustered partial linear regression. Predictions using this technique are preceded by a cluster membership query for each test case. The cluster membership probability of a test case is used as a weight in an averaging process that calculates the final prediction. This averaging process involves the predictions of the regression models associated to the clusters for which the test case may belong. We have tested this general multi-strategy approach using several regression techniques and we have observed significant accuracy gains in several data sets. We have also compared our method to bagging that also uses an averaging process to obtain predictions. This experiment showed that the two methods are significantly different. Finally, we present a comparison of our method with several state-of-the-art regression methods. [ABSTRACT FROM AUTHOR]

MetaCost is a recently proposed procedure that converts an error-based learning algorithm into a cost-sensitive algorithm. This paper investigates two important issues centered on the procedure which were ignored in the paper proposing MetaCost. First, no comparison was made between MetaCost's final model and the internal cost-sensitive classifier on which MetaCost depends. It is credible that the internal cost-sensitive classifier may outperform the final model without the additional computation required to derive the final model. Second, MetaCost assumes its internal cost-sensitive classifier is obtained by applying a minimum expected cost criterion. It is unclear whether violation of the assumption has an impact on MetaCost's performance. We study these issues using two boosting procedures, and compare with the performance of the original form of MetaCost which employs bagging. [ABSTRACT FROM AUTHOR]

Feature selection has received a lot of attention in the machine learning community, but mainly under the supervised paradigm. In this work we study the potential benefits of feature selection in hierarchical clustering tasks. Particularly we address this problem in the context of incremental clustering, following the basic ideas of Gennari [8]. By using a simple implementation, we show that a feature selection scheme running in parallel with the learning process can improve the clustering task under the dimensions of accuracy, efficiency in learning, efficiency in prediction and comprehensibility. [ABSTRACT FROM AUTHOR]

Boosting is a powerful method for improving the predictive accuracy of classifiers. The AdaBoost algorithm of Freund and Schapire has been successfully applied to many domains [2, 10, 12] and the combination of AdaBoost with the C4.5 decision tree algorithm has been called the best off-the-shelf learning algorithm in practice. Unfortunately, in some applications, the number of decision trees required by AdaBoost to achieve a reasonable accuracy is enormously large and hence is very space consuming. This problem was first studied by Margineantu and Dietterich [7], where they proposed an empirical method called Kappa pruning to prune the boosting ensemble of decision trees. The Kappa method did this without sacrificing too much accuracy. In this work-in-progress we propose a potential improvement to the Kappa pruning method and also study the boosting pruning problem from a theoretical perspective. We point out that the boosting pruning problem is intractable even to approximate. Finally, we suggest a margin-based theoretical heuristic for this problem. [ABSTRACT FROM AUTHOR]

In behavioural cloning of the human operator's skill, a controller is usually induced directly as a classifier from system's states into actions. Experience shows that this often results in brittle controllers. In this paper we explore a decomposition of the cloning problem into two learning problems: the learning of operator's control trajectories and the learning of the system's dynamics separately. We analyse advantages of such indirect controllers. We give characterization of the learner's error that is plausible explanation of why this decomposition approach has empirically proved to be usually superior to direct cloning. [ABSTRACT FROM AUTHOR]

This paper presents layered learning, a hierarchical machine learning paradigm. Layered learning applies to tasks for which learning a direct mapping from inputs to outputs is intractable with existing learning algorithms. Given a hierarchical task decomposition into subtasks, layered learning seamlessly integrates separate learning at each subtask layer. The learning of each subtask directly facilitates the learning of the next higher subtask layer by determining at least one of three of its components: (i) the set of training examples; (ii) the input representation; and/or (iii) the output representation. We introduce layered learning in its domain-independent general form. We then present a full implementation in a complex domain, namely simulated robotic soccer. [ABSTRACT FROM AUTHOR]

Case-based reasoning systems solve new problems by reusing previous problem solving experience stored as cases in a case-base. In recent years the maintenance problem has become an increasingly important research issue for the case-based reasoning community. In short, the goal is to develop strategies for effectively maintaining the efficiency and competence of case-based reasoning systems as they evolve. Our research has focused on the development of a model of competence for case-based reasoning systems, a model that measures the contributions of individual cases to overall system competence, and which forms the computational basis for a variety of maintenance strategies. However, while this model offers many potential advantages its upkeep adds an additional cost to the CBR cycle. In this paper we evaluate a new method for more efficiently updating the model at run-time. [ABSTRACT FROM AUTHOR]

Many learning algorithms make an implicit assumption that all the attributes present in the data are relevant to a learning task. However, several studies have demonstrated that this assumption rarely holds; for many supervised learning algorithms, the inclusion of irrelevant or redundant attributes can result in a degradation in classification accuracy. While a variety of different methods for dimensionality reduction exist, many of these are only appropriate for datasets which contain a small number of attributes (e.g. < 20). This paper presents an alternative approach to dimensionality reduction, and demonstrates how it can be combined with a Nearest Neighbour learning algorithm. We present an empirical evaluation of this approach, and contrast its performance with two related techniques; a Monte-Carlo wrapper and an Information Gain-based filter approach. [ABSTRACT FROM AUTHOR]

We discuss the problem of choosing the complexity of a decision tree (measured in the number of leaf nodes) that gives us highest generalization performance. We first discuss an analysis of the generalization error of decision trees that gives us a new perspective on the regularization parameter that is inherent to any regularization (e.g., pruning) algorithm. There is an optimal setting of this parameter for every learning problem; a setting that does well for one problem will inevitably do poorly for others. We will see that the optimal setting can in fact be estimated from the sample, without "trying out" various settings on holdout data. This leads us to a nonparametric decision tree regularization algorithm that can, in principle, work well for all learning problems. [ABSTRACT FROM AUTHOR]

The proposed algorithm (BPL) induces behavior patterns from events taking into account characteristics of observed systems and their environment. The main strategy of this method consists on building summaries of the behaviour of a system as events arrive, and take these summaries as training examples. BPL constructs summaries with new features from events, like duration of current event values, repetitions of an event in a period of time, amongst others. This algorithm has been tested in learning faulty behavior of networks with the purpose of continuously predicting alarms. [ABSTRACT FROM AUTHOR]

This paper presents a new method of measuring performance when positives are rare and investigates whether Chomsky-like grammar representations are useful for learning accurate comprehensible predictors of members of biological sequence families. The positive-only learning framework of the Inductive Logic Programming (ILP) system CProgol is used to generate a grammar for recognising a class of proteins known as human neuropeptide precursors (NPPs). Performance is measured using both predictive accuracy and a new cost function, Relative Advantage (RA). The RA results show that searching for NPPs by using our best NPP predictor as a filter is more than 100 times more efficient than randomly selecting proteins for synthesis and testing them for biological activity. Predictive accuracy is not a good measure of performance for this domain because it does not discriminate well between NPP recognition models: despite covering varying numbers of (the rare) positives, all the models are awarded a similar (high) score by predictive accuracy because they all exclude most of the abundant negatives. [ABSTRACT FROM AUTHOR]

The detection of intrusions over computer networks (i.e., network access by non-authorized users)c an be cast to the task of detecting anomalous patterns of network traffic. In this case, models of normal traffic have to be determined and compared against the current network traffic. Data mining systems based on Genetic Algorithms can contribute powerful search techniques for the acquisition of patterns of the network traffic from the large amount of data made available by audit tools. We compare models of network traffic acquired by a system based on a distributed genetic algorithm with the ones acquired by a system based on greedy heuristics. Also we discuss representation change of the network data and its impact over the performances of the traffic models. Network data made available from the Information Exploration Shootout project and the 1998 DARPA Intrusion Detection Evaluation have been chosen as experimental testbed. [ABSTRACT FROM AUTHOR]

Acquisition of patterns for information extraction systems is a common task in Natural Language Processing, mostly based on manual analysis of text corpora. We have developed a system called Prométhée, which incrementally extracts lexico-syntactic patterns for a specific conceptual relation from a technical corpus. However, these patterns are often too general and need to be manually validated. In this paper, we demonstrate how Prométhée has been interfaced with the machine learning system Eagle in order to automatically refine the patterns it produces. The empirical results obtained with this technique show that the refined patterns allows to decrease the need for the human validation. [ABSTRACT FROM AUTHOR]

Two methods to assign discrete values to continuous values from time series, using dynamic information about the series, are proposed. The first method is based on a particular statistic which allows us to select a discrete value for a new continuous value from the series. The second one is based on a concept of significant distance between consecutive values from time series which is defined. This definition is based on qualitative changes in the time series values. In both methods, the conversion process of continuous values into discrete values is dynamic in opposition to static classical methods used in machine learning. Finally, we use the proposed methods in a practical case. We transform the daily clearness index time series into discrete values. The results display that the series with discrete values obtained from the dynamic process captures better the sequential properties of the original continuous series. [ABSTRACT FROM AUTHOR]

Large Bayes (LB) is a recently introduced classifier built from frequent and interesting itemsets. LB uses itemsets to create context-specific probabilistic models of the data and estimate the conditional probability P(ciA) of each class ci given a case A. In this paper we use chi-square tests to address several drawbacks of the originally proposed interestingness metric, namely: (i) the inability to capture certain really interesting patterns, (ii) the need for a user-defined and data dependent interestingness threshold, and (iii) the need to set a minimum support threshold. We also introduce some pruning criteria which allow for a trade-off between complexity and speed on one side and classification accuracy on the other. Our experimental results show that the modified LB outperforms the original LB, Naïve Bayes, C4.5 and TAN. [ABSTRACT FROM AUTHOR]

In the present paper we propose a consistent way to integrate syntactical least general generalizations (lgg's) with semantic evaluation of the hypotheses. For this purpose we use two different relations on the hypothesis space — a constructive one, used to generate lgg's and a semantic one giving the coverage-based evaluation of the lgg. These two relations jointly implement a semantic distance measure. The formal background for this is a height-based definition of a semi-distance in a join semi-lattice. We use some basic results from lattice theory and introduce a family of language independent coverage-based height functions. The theoretical results are illustrated by examples of solving some basic inductive learning tasks. [ABSTRACT FROM AUTHOR]

This paper describes an experiment performed using the Principal Direction Divisive Partitioning algorithm (Boley, 1998) in order to extract linguistic word error regularities from several sets of medical dictation data. For each of six physicians, two hundred finished medical dictations aligned with their corresponding automatic speech recognition output were clustered and the results analyzed for linguistic regularities between and within clusters. Sparsity measures indicated a good fit between the algorithm and the input data. Linguistic analysis of the output clusters showed evidence of systematic word recognition error for short words, function words, words with destressed vowels, and phonological confusion errors due to telephony (recording) bandwidth interference. No qualitatively significant distinctions between clusters could be made by examining word errors alone, but the results confirmed several informally held hypotheses and suggested several avenues of further investigation, such as the examination of word error contexts. [ABSTRACT FROM AUTHOR]

The paper describes a new, context-sensitive discretization algorithm that combines aspects of unsupervised (class-blind) and supervised methods. The algorithm is applicable to a wide range of machine learning and data mining problems where continuous attributes need to be discretized. In this paper, we evaluate its utility in a regression-by-classification setting. Preliminary experimental results indicate that the decision trees induced using this discretization strategy are significantly smaller and thus more comprehensible than those learned with standard discretization methods, while losing only minimally in numerical prediction accuracy. This may be a considerable advantage in machine learning and data mining applications where comprehensibility is an issue. [ABSTRACT FROM AUTHOR]