Abstract We introduce a new method for finding network motifs . Subgraphs are motifs when their frequency in the data is high compared to the expected frequency under a null model . To compute this expectation, a full or approximate count of the occurrences of a motif is normally repeated on as many as 1000 random graphs sampled from the null model; a prohibitively expensive step. We use ideas from the minimum description length literature to define a new measure of motif relevance. With our method, samples from the null model are not required. Instead we compute the probability of the data under the null model and compare this to the probability under a specially designed alternative model. With this new relevance test, we can search for motifs by random sampling, rather than requiring an accurate count of all instances of a motif. This allows motif analysis to scale to networks with billions of links.

We discuss algorithms for combining sequential prediction strategies, a task which can be viewed as a natural generalization of the concept of universal coding. We describe a graphical language based on hidden Markov models for defining prediction strategies, and we provide both existing and new models as examples. The models include efficient, parameterless models for switching between the input strategies over time, including a model for the case where switches tend to occur in clusters, and finally a new model for the scenario where the prediction strategies have a known relationship, and where jumps are typically between strongly related ones. This last model is relevant for coding time series data where parameter drift is expected. As theoretical contributions, we introduce an interpolation construction that is useful in the development and analysis of new algorithms, and we establish a new sophisticated lemma for analyzing the individual sequence regret of parameterized models.

Classical rate-distortion theory requires specifying a source distribution. Instead, we analyze rate-distortion properties of individual objects using the recently developed algorithmic rate-distortion theory. The latter is based on the noncomputable notion of Kolmogorov complexity. To apply the theory we approximate the Kolmogorov complexity by standard data compression techniques, and perform a number of experiments with lossy compression and denoising of objects from different domains. We also introduce a natural generalization to lossy compression with side information. To maintain full generality we need to address a difficult searching problem. While our solutions are therefore not time efficient, we do observe good denoising and compression performance.

Most methods for decision-theoretic online learning are based on the Hedge algorithm, which takes a parameter called the learning rate. In most previous analyses the learning rate was carefully tuned to obtain optimal worst-case performance, leading to suboptimal performance on easy instances, for example when there exists an action that is significantly better than all others. We propose a new way of setting the learning rate, which adapts to the difficulty of the learning problem: in the worst case our procedure still guarantees optimal performance, but on easy instances it achieves much smaller regret. In particular, our adaptive method achieves constant regret in a probabilistic setting, when there exists an action that on average obtains strictly smaller loss than all other actions. We also provide a simulation study comparing our approach to existing methods.

We consider inference based on a countable set of models (sets of probability distributions), focusing on two tasks: model selection and model averaging. In model selection tasks, the goal is to select the model that best explains the given data. In model averaging, the goal is to find the weighted combination of models that leads to the best prediction of future data from the same source.

Bayesian model averaging, model selection and their approximations such as BIC are generally statistically consistent, but sometimes achieve slower rates of con- vergence than other methods such as AIC and leave-one-out cross-validation. On the other hand, these other methods can be inconsistent. We identify the catch-up phenomenon as a novel explanation for the slow convergence of Bayesian meth- ods. Based on this analysis we define the switch-distribution, a modification of the Bayesian model averaging distribution. We prove that in many situations model selection and prediction based on the switch-distribution is both consistent and achieves optimal convergence rates, thereby resolving the AIC-BIC dilemma. The method is practical; we give an efficient algorithm.

We analyse the behaviour of the ML plug-in code, also known as the Rissanen-Dawid prequential ML code, relative to single parameter exponential families M. If the data are i.i.d. according to an (essentially) arbitrary P, then the redundancy grows at 1/2c log n. We find that, in contrast to other important universal codes such as the 2-part MDL, Shtarkov and Bayesian codes where c = 1, here c equals the ratio between the variance of P and the variance of the element of M that is closest to P in KL-divergence. We show how this behaviour can impair model selection performance in a simple setting in which we select between the Poisson and geometric models

This paper extend Ukkonen's online suffix tree construction algorithm to support substring frequency queries, by adding count fields to the internal nodes of the tree. This has applications in the field of sequential data compression. One major problem is that Ukkonen's online construction algorithm does not maintain explicit end of string markers in the tree. The major part of our work concerns quickly determining where the end markers for a particular edge would be, so that frequencies can be correctly obtained. So a complete characterization of all end markers on leaf edges is given. Furthermore we found that edges between two internal nodes can contain at most one end marker. Using these results, the algorithms are given to update the count fields and do frequency queries correctly. All algorithms have been implemented and tested correct in practice.