1,721,055 research outputs found
Learning with Pairwise Constraints
No full textIn many application fields, ranging from bioinformatics to computer vision, prior knowledge on pairwise relationships among a given set of objects is available. Even if the information that they describe has different semantic meanings among a variety of problems, it specifically indicates that two entities are expected to fulfill a certain property, such as, for example, belonging to the same, but unknown, class. These relationships can be formalized as a set of constraints on the learning problem, and, for this reason, they are commonly referred to as pairwise constraints in the scientific literature.
Given a set of pairwise constraints that are provided by a supervisor or that are intrinsically available from problem-specific assumptions and prior knowledge, how can we efficiently tackle a learning task that involves them? This is the main point that we investigate in this dissertation, focusing on many instances of this problem.
We analyze the “learning with pairwise constraints framework” in a hierarchical manner, progressively increasing the abstraction level of the constraints and of the entities that they include. In particular, we focus on: binary relationships between data points; relationships between values of a function evaluated on them; relationships between functions defined in different domains. The nature of the pairwise constraints changes among these three settings. Sometimes they are the only information supporting the learning task, whereas in some situations we have the use of additional supervision.At first, we investigate the popular scenario of similarity learning, where the back- ground information on the problem is expressed by binary relationships between data points. A set of similarity and dissimilarity links is available, and the goal is to learn a function that predicts the similarity score between two patterns. Since class labels are not provided, the learned measure is used to appropriately group data in a semi- supervised clustering setting. We propose a neural model, Similarity Neural Network (SNN), that is guaranteed to learn symmetric and non negative functions from pairwise supervisions. Moreover, it can compute the representative of a group of data coher- ently with the learned measure, allowing the user to define a hierarchical organization to speedup data access.
Second, we consider pairwise constraints that involve values of a function evaluated on the data points. In particular, constraints do not come from a supervisor but from specific assumptions on the proximity of each data point. We focus on semi-supervised classification, where the information supporting the learning task is constituted by class labels of a few training points, while constraints also involve a wider set of unlabeled data. The classification function is constrained to change smoothly its value when evaluated on two nearby points, leading to an instance of the geometrical framework of manifold regularization. We investigate the Laplacian Support Vector Machine (LapSVM) algorithm, showing how we can efficiently solve the primal formulation of the regularized learning problem. The effect of the pairwise constraints becomes intangible when the decision of the classifier is stable, so that we can significantly speedup the training algorithm by a stability-based early stop that leads to approximate solutions with equivalent quality to the optimal one.
Finally we consider a higher level of representation where the constraints involve functions defined on different domains. In this setting, the structure of the problem itself suggests the pairwise relationships. Following the previously described scenario, we keep focusing on semi-supervised kernel machines, and we investigate the problem of multi-view object recognition, where pictures of an input object are acquired from different view points. Given a set of single view classifiers, pairwise constraints define relationships that must hold between the corresponding views of the same object. Each classification function operates in its own domain, and an interaction is established within the training stage of the classifiers. Thanks to the pairwise constraints, the shape of each function is adjusted accordingly to the shape of the other ones, even in those space regions where class labels are not available
Unsupervised Learning by Minimal Entropy Encoding
No full textFollowing basic principles of information-theoretic learning, in this paper, we propose a novel approach to data clustering, referred to as minimal entropy encoding (MEE), which is based on a set of functions (features) projecting each input onto a minimum entropy configuration (code). Inspired by traditional parsimony principles, we seek solutions in reproducing kernel Hilbert spaces and then we prove that the encoding functions are expressed in terms of kernel expansion. In order to avoid trivial solutions, the developed features must be as different as possible by means of a soft constraint on the empirical estimation of the entropy associated with the encoding functions. This leads to an unconstrained optimization problem that can be efficiently solved by conjugate gradient. We also investigate an optimization strategy based on concave-convex algorithms. The relationships with maximum margin clustering are studied, showing that MEE overcomes some of its critical issues, such as the lack of a multiclass extension and the need to face problems with a large number of constraints. A massive evaluation on several benchmarks of the proposed approach shows improvements over state-of-the-art techniques, both in terms of accuracy and computational complexity
Laplacian support vector machines trained in the primal
No full textIn the last few years, due to the growing ubiquity of unlabeled data, much effort has been spent by the machine learning community to develop better understanding and improve the quality of classifiers exploiting unlabeled data. Following the manifold regularization approach, Laplacian Support Vector Machines (LapSVMs) have shown the state of the art performance in semi-supervised classification. In this paper we present two strategies to solve the primal LapSVM problem, in order to overcome some issues of the original dual formulation. In particular, training a LapSVM in the primal can be efficiently performed with preconditioned conjugate gradient. We speed up training by using an early stopping strategy based on the prediction on unlabeled data or, if available, on labeled validation examples. This allows the algorithm to quickly compute approximate solutions with roughly the same classification accuracy as the optimal ones, considerably reducing the training time. The computational complexity of the training algorithm is reduced from 0(n^3) to 0(kn^2), where n is the combined number of labeled and unlabeled examples and k is empirically evaluated to be significantly smaller than n. Due to its simplicity, training LapSVM in the primal can be the starting point for additional enhancements of the original LapSVM formulation, such as those for dealing with large data sets. We present an extensive experimental evaluation on real world data showing the benefits of the proposed approach
Learning with Box Kernels
No full textSupervised examples and prior knowledge on regions of the input space have been profitably integrated in kernel machines to improve the performance of classifiers in different real-world contexts. The proposed solutions, which rely on the unified supervision of points and sets, have been mostly based on specific optimization schemes in which, as usual, the kernel function operates on points only. In this paper, arguments from variational calculus are used to support the choice of a special class of kernels, referred to as box kernels, which emerges directly from the choice of the kernel function associated with a regularization operator. It is proven that there is no need to search for kernels to incorporate the structure deriving from the supervision of regions of the input space, because the optimal kernel arises as a consequence of the chosen regularization operator. Although most of the given results hold for sets, we focus attention on boxes, whose labeling is associated with their propositional description. Based on different assumptions, some representer theorems are given that dictate the structure of the solution in terms of box kernel expansion. Successful results are given for problems of medical diagnosis, image, and text categorizatio
Constraint Verification With Kernel Machines
No full textBased on a recently proposed framework of learning from constraints using kernel-based representations, in this brief, we naturally extend its application to the case of inferences on new constraints. We give examples for polynomials and first-order logic by showing how new constraints can be checked on the basis of given premises and data samples. Interestingly, this gives rise to a perceptual logic scheme in which the inference mechanisms do not rely only on formal schemes, but also on the data probability distribution. It is claimed that when using a properly relaxed computational checking approach, the complementary role of data samples makes it possible to break the complexity barriers of related formal checking mechanisms
Cognitive Action Laws: The Case of Visual Features
No full textThis paper proposes a theory for understanding perceptual learning processes within the general framework of laws of nature. Artificial neural networks are regarded as systems whose connections are Lagrangian variables, namely, functions depending on time. They are used to minimize the cognitive action, an appropriate functional index that measures the agent interactions with the environment. The cognitive action contains a potential and a kinetic term that nicely resemble the classic formulation of regularization in machine learning. A special choice of the functional index, which leads to the fourth-order differential equations--Cognitive Action Laws (CAL)--exhibits a structure that mirrors classic formulation of machine learning. In particular, unlike the action of mechanics, the stationarity condition corresponds with the global minimum. Moreover, it is proven that typical asymptotic learning conditions on the weights can coexist with the initialization provided that the system dynamics is driven under a policy referred to as information overloading control. Finally, the theory is experimented for the problem of feature extraction in computer vision
The KANDY benchmark: Incremental neuro-symbolic learning and reasoning with Kandinsky patterns
No full textArtificial intelligence is continuously seeking novel challenges and benchmarks to effectively measure performance and to advance the state-of-the-art. In this paper we introduce KANDY, a benchmarking framework that can be used to generate a variety of learning and reasoning tasks inspired by Kandinsky patterns. By creating curricula of binary classification tasks with increasing complexity and with sparse supervisions, KANDY can be used to implement benchmarks for continual and semi-supervised learning, with a specific focus on symbol compositionality. The ground truth is also augmented with classification rules to enable analysis of interpretable solutions. Together with the benchmark generation pipeline, we release two curricula, an easier and a harder one, that we propose as new challenges for the research community. With a thorough experimental evaluation, we show how state-of-the-art neural models, purely symbolic approaches, and vision language models struggle with solving most of the tasks, thus calling for the application of advanced neuro-symbolic methods trained over time
Gravitational laws of focus of attention
No full textThe understanding of the mechanisms behind focus of attention in a visual scene is a problem of great interest in visual perception and computer vision. In this paper, we describe a model of scanpath as a dynamic process which can be interpreted as a variational law somehow related to mechanics, where the focus of attention is subject to a gravitational field. The distributed virtual mass that drives eye movements is associated with the presence of details and motion in the video. Unlike most current models, the proposed approach does not estimate directly the saliency map, but the prediction of eye movements allows us to integrate over time the positions of interest. The process of inhibition-of-return is also supported in the same dynamic model with the purpose of simulating fixations and saccades. The differential equations of motion of the proposed model are numerically integrated to simulate scanpaths on both images and videos. Experimental results for the tasks of saliency and scanpath prediction on a wide collection of datasets are presented to support the theory. Top level performances are achieved especially in the prediction of scanpaths, which is the primary purpose of the proposed model
Kernel methods for minimum entropy encoding
No full textFollowing the basic principles of Information-Theoretic Learning (ITL), in this paper we propose Minimum Entropy Encoders (MEEs), a novel approach to data clustering. We consider a set of functions that project each input point onto a minimum entropy configuration (code). The encoding functions are modeled by kernel machines and the resulting code collects the cluster membership probabilities. Two regularizers are included to balance the distribution of the output features and favor smooth solutions, respectively, thus leading to an unconstrained optimization problem that can be efficiently solved by conjugate gradient or concave-convex procedures. The relationships with Maximum Margin Clustering algorithms are investigated, which show that MEEs overcomes some of the critical issues, such as the lack of a multi-class extension and the need to face problems with a large number of constraints. A massive evaluation on several benchmarks of the proposed approach shows improvements over state-of-the-art techniques, both in terms of accuracy and computational complexity
Continual learning of conjugated visual representations through higher-order motion flows
Full text linkLearning with neural networks from a continuous stream of visual information presents several challenges due to the non-i.i.d. nature of the data. However, it also offers novel opportunities to develop representations that are consistent with the information flow. In this paper we investigate the case of unsupervised continual learning of pixel-wise features subject to multiple motion-induced constraints, therefore named motion-conjugated feature representations. Differently from existing approaches, motion is not a given signal (either ground-truth or estimated by external modules), but is the outcome of a progressive and autonomous learning process, occurring at various levels of the feature hierarchy. Multiple motion flows are estimated with neural networks and characterized by different levels of abstractions, spanning from traditional optical flow to other latent signals originating from higher-level features, hence called higher-order motions. Continuously learning to develop consistent multi-order flows and representations is prone to trivial solutions, which we counteract by introducing a self-supervised contrastive loss, spatially-aware and based on flow-induced similarity. We assess our model on photorealistic synthetic streams and real-world videos, comparing to pre-trained state-of-the art feature extractors (also based on Transformers) and to recent unsupervised learning models, significantly outperforming these alternatives
- …
