In machine learning pure applications of MDL are rare, partially because of the difficulties one encounters trying to define an adequate model code and data-to-model code, and partially because of the operational difficulties that are poorly understood. We analyze aspects of both the power and the perils of MDL precisely and formally. Let us first resurrect a familiar problem from our childhood to illustrate some of the issues involved. The process of solving a jigsaw puzzle involves an incremental reduction of entropy, and this serves to illustrate the analogous features of the learning problems which are the main issues of this work. Initially, when the pieces come out of the box they have a completely random ordering. Gradually we combine pieces, thus reducing the entropy and increasing the order until the puzzle is solved. In this last stage we have found a maximal ordering. Suppose that Alice and Bob both start to solve two versions of the same puzzle, but that they follow different strategies. Initially, Alice sorts all pieces according to color, and Bob starts by sorting the pieces according to shape.

The normalized information distance is a universal distance measure for objects of all kinds. It is based on Kolmogorov complexity and thus uncomputable, but there are ways to utilize it. First, compression algorithms can be used to approximate the Kolmogorov complexity if the objects have a string representation. Second, for names and abstract concepts, page count statistics from the World Wide Web can be used. These practical realizations of the normalized information distance can then be applied to machine learning tasks, expecially clustering, to perform feature-free and parameter-free data mining. This chapter discusses the theoretical foundations of the normalized information distance and both practical realizations. It presents numerous examples of successful real-world applications based on these distance measures, ranging from bioinformatics to music clustering to machine translation.

Distributed configuration management is imperative for wireless infrastructureless networks where each node adjusts locally its physical and logical configuration through information exchange with neighbors. Two issues remain open. The first is the optimality. The second is the complexity. We study these issues through modeling, analysis, and randomized distributed algorithms. Modeling defines the optimality. We first derive a global probabilistic model for a network configuration which characterizes jointly the statistical spatial dependence of a physical- and a logical-configuration. We then show that a local model which approximates the global model is a two-layer Markov Random Field or a random bond model. The complexity of the local model is the communication range among nodes. The local model is near-optimal when the approximation error to the global model is within a given error bound. We analyze the trade-off between an approximation error and complexity, and derive sufficient conditions on the near-optimality of the local model. We validate the model, the analysis and the randomized distributed algorithms also through simulation.

Semantic networks qualify the meaning of an edge relating any two vertices. Determining which vertices are most "central" in a semantic network is difficult because one relationship type may be deemed subjectively more important than another. For this reason, research into semantic network metrics has focused primarily on context-based rankings (i.e. user prescribed contexts). Moreover, many of the current semantic network metrics rank semantic associations (i.e. directed paths between two vertices) and not the vertices themselves. This article presents a framework for calculating semantically meaningful primary eigenvector-based metrics such as eigenvector centrality and PageRank in semantic networks using a modified version of the random walker model of Markov chain analysis. Random walkers, in the context of this article, are constrained by a grammar, where the grammar is a user defined data structure that determines the meaning of the final vertex ranking. The ideas in this article are presented within the context of the Resource Description Framework (RDF) of the Semantic Web initiative.

For supervised and unsupervised learning, positive definite kernels allow to use large and potentially infinite dimensional feature spaces with a computational cost that only depends on the number of observations. This is usually done through the penalization of predictor functions by Euclidean or Hilbertian norms. In this paper, we explore penalizing by sparsity-inducing norms such as the l1-norm or the block l1-norm. We assume that the kernel decomposes into a large sum of individual basis kernels which can be embedded in a directed acyclic graph; we show that it is then possible to perform kernel selection through a hierarchical multiple kernel learning framework, in polynomial time in the number of selected kernels. This framework is naturally applied to non linear variable selection; our extensive simulations on synthetic datasets and datasets from the UCI repository show that efficiently exploring the large feature space through sparsity-inducing norms leads to state-of-the-art predictive performance.

- In every mathematical model, parameters regulate the behaviour of equations describing temporal and spatial changes of model state variables and their interactions. Generally, there is some uncertainty associated with each parameter. Model calibration is performed by comparing observed with predicted data and it is a crucial phase in the modelling process. It's an iterative and interactive task in which, after each simulation, the "modeller" analyses the results and performs changes on one or more equation's parameters trying to tune the model. This "tuning" procedure is a hard and "tedious" work requiring a good understanding of the effects of different parameters over the available variables. Automatic calibration procedures, based on systematic and exhaustive generation of parameter vectors and using several convergence methods, are available but they require a large number of model runs and are, therefore, not applicable to very complex ecosystem models demanding large computational times.

This document ("ECOLANG_v_1_3c_Eng.doc") describes the communication language used in one multi-agent systems environment for ecological simulations, based on the EcoDynamo simulator application (Pereira and Duarte 2005) linked with several intelligent agents and visualisation applications and extends the initial definition of the language (Pereira et al. 2005). The agents' actions and perceptions are translated into messages exchanged with the simulator application and other agents. The concepts' definitions used follow the BNF notation (Backus et al. 1960) and it's inspired in the Coach Unilang language (Reis and Lau 2002). ECOLANG notation is an extension to the original BNF formalism adding the following meta-symbols: { } used for repetitive items (one or more times); [ ] encloses types of values; Terminal symbols use bold face letters.

Multiagent systems ([10], [31], [33], [26]) are an increasingly important and active area of interdisciplinary research on the border of computer science, artificial intelligence, and game theory, as they model a wide variety of phenomena in these fields, including open and interactive systems, distributed computations, security protocols, knowledge and information exchange, coalitional abilities in games, etc. Not surprisingly, a number of logical formalisms have been proposed for specification, verification, and reasoning about multiagent systems.

While statistics focusses on hypothesis testing and on estimating (properties of) the true sampling distribution, in machine learning the performance of learning algorithms on future data is the primary issue. In this paper we bridge the gap with a general principle (PHI) that identifies hypotheses with best predictive performance. This includes predictive point and interval estimation, simple and composite hypothesis testing, (mixture) model selection, and others as special cases. For concrete instantiations we will recover well-known methods, variations thereof, and new ones. PHI nicely justifies, reconciles, and blends (a reparametrization invariant variation of) MAP, ML, MDL, and moment estimation. One particular feature of PHI is that it can genuinely deal with nested hypotheses.

Minimizing the rank of a matrix subject to constraints is a challenging problem that arises in many applications in control theory, machine learning, and discrete geometry. This class of optimization problems, known as rank minimization, is NP-HARD, and for most practical problems there are no efficient algorithms that yield exact solutions. A popular heuristic algorithm replaces the rank function with the nuclear norm--equal to the sum of the singular values--of the decision variable. In this paper, we provide a necessary and sufficient condition that quantifies when this heuristic successfully finds the minimum rank solution of a linear constraint set. We additionally provide a probability distribution over instances of the affine rank minimization problem such that instances sampled from this distribution satisfy our conditions for success with overwhelming probability provided the number of constraints is appropriately large. Finally, we give empirical evidence that these probabilistic bounds provide accurate predictions of the heuristic's performance in non-asymptotic scenarios.