Une caractéristique contraignante de la complexité de Kolmogorov-Chaitin (dénotée dans ce chapitre par K) est qu'elle n'est pas calculable à cause du problème de l'arrêt, ce qui limite son domaine d'application. Une autre critique concerne la dépendance de K à un langage particulier ou une machine de Turing universelle particulière, surtout pour les suites assez courtes, par exemple, plus courtes que les longueurs typiques des compilateurs des langages de programmation. En pratique, on peut obtenir une approximation de K(s), grâce à des méthodes de compression. Mais les performances de ces méthodes de compression s'écroulent quand il s'agit des suites courtes. Pour les courtes suites, approcher K(s) par des méthodes de compression ne fonctionne pas. On présente dans cet thèse une approche empirique pour surmonter ce problème. Nous proposons une méthode "naturelle" qui permet d'envisager une définition plus stable de la complexité de Kolmogorov-Chaitin K(s) via la mesure de probabilité algorithmique m(s). L'idée est de faire fonctionner une machine universelle en lui donnant un programme au hasard pour calculer expérimentalement la probabilité m(s) (la probabilité de produire s), pour ensuite évaluer numériquement K(s) de manière alternative aux méthodes des algorithmes de compression. La méthode consiste à : (a) faire fonctionner des machines de calcul (machines de Turing, automates cellulaires) de façon systématique pour produire des suites (b) observer quelles sont les distributions de probabilité obtenues et puis (c) obtenir K(s) à partir de m(s) par moyen du théorème de codage de Levin-Chaitin. / In practice, it is a known problem that one cannot compress short strings, shorter, for example, than the length in bits of the compression program which is added to the compressed version of s, making the result (the program producing s) sensitive to the compressor choice and the parameters involved. However, short strings are quite often the kind of data encountered in many practical settings. While compressors' asymptotic behavior guarantees the eventual convergence to K(s) thanks to the invariance theorem, measurements differ considerably in the domain of short strings. We describe a method that combines several theoretical and experimental results to numerically approximate the algorithmic (Kolmogorov-Chaitin) complexity of short bit strings. This is done by an exhaustive execution of abstract machines for which the halting times are known thanks to the Busy Beaver problem. An output frequency distribution is then computed, from which the algorithmic probability is calculated and the algorithmic complexity evaluated by way of the (Levin-Chaitin) coding theorem. The approach we adopt here is different and independent of the machine size (small machines are used only because they allow us to calculate all of them up to a small size) and relies only on the concept of algorithmic probability. The result is a novel approach that we put forward for numerically calculate the complexity of short strings as an alternative to the indirect method using compression algorithms.

Proefschrift Universiteit van Amsterdam. / Met samenvatting in het Nederlands.

Kolmogorov complexity is a theory based on the premise that the complexity of a binary string can be measured by its compressibility; that is, a string’s complexity is the length of the shortest program that produces that string. We explore applications of this measure to graph theory.

Thèse de doctorat : Informatique : Lille 1 : 2000. / Résumé en français et en anglais. Bibliogr. f. 81-84.

Image similarity or distortion assessment is fundamental to a broad range of applications throughout the field of image processing and machine vision. These include image restoration, denoising, coding, communication, interpolation, registration, fusion, classification and retrieval, as well as object detection, recognition, and tracking. Many existing image similarity measures have been proposed to work with specific types of image distortions (e.g., JPEG compression). There are also methods such as the structural similarity (SSIM) index that are applicable to a wider range of applications. However, even these "general-purpose" methods offer limited scopes in their applications. For example, SSIM does not apply or work properly when significant geometric changes exist between the two images being compared. The theory of Kolmogorov complexity provides solid groundwork for a generic information distance metric between any objects that minorizes all metrics in the class. The Normalized Information Distance (NID) metric provides a more useful framework. While appealing, the challenge lies in the implementation, mainly due to the non-computable nature of Kolmogorov complexity. To overcome this, a Normalized Compression Distance (NCD) measure was proposed, which is an effective approximation of NID and has found successful applications in the fields of bioinformatics, pattern recognition, and natural language processing. Nevertheless, the application of NID for image similarity and distortion analysis is still in its early stage. Several authors have applied the NID framework and the NCD algorithm to image clustering, image distinguishability, content-based image retrieval and video classification problems, but most reporting only moderate success. Moreover, due to their focuses on ! specific applications, the generic property of NID was not fully exploited. In this work, we aim for developing practical solutions for image distortion analysis based on the information distance framework. In particular, we propose two practical approaches to approximate NID for image similarity and distortion analysis. In the first approach, the shortest program that converts one image to another is found from a list of available transformations and a generic image similarity measure is built on computing the length of this shortest program as an approximation of the conditional Kolmogorov complexity in NID. In the second method, the complexity of the objects is approximated using Shannon entropy. Specifically we transform the reference and distorted images into wavelet domain and assume local independence among image subbands. Inspired by the Visual Information Fidelity (VIF) approach, the Gaussian Scale Mixture (GSM) model is adopted for Natural Scene Statistics (NSS) of the images to simplify the entropy computation. When applying image information distance framework in real-world applications, we find information distance measures often lead to useful features in many image processing applications. In particular, we develop a photo retouching distortion measure based on training a Gaussian kernel Support Vector Regression (SVR) model using information theoretic features extracted from a database of original and edited images. It is shown that the proposed measure is well correlated with subjective ranking of the images. Moreover, we propose a tone mapping operator parameter selection scheme for High Dynamic Range (HDR) images. The scheme attempts to find tone mapping parameters that minimize the NID of the HDR image and the resulting Low Dynamic Range (LDR) image, and thereby minimize the information loss in HDR to LDR tone mapping. The resulting images created by minimizing NID exhibit enhanced image quality.

Thesis (Ph.D.)--University of Central Florida, 2008. / Advisers: Xin Li, Mubarak Shah. Includes bibliographical references (p. 127-130).

Cette thèse s’interroge sur les notions d’aléa et de régularité des variations boursières. Nous démontrons sur le plan théorique, la compatibilité des principales théories financières (cf. efficience informationnelle, finance comportementale et approche conventionnaliste) avec l'impossibilité de battre la stratégie «buy and hold». Cette impossibilité est confirmée par les études statistiques dans la mesure où les régularités identifiées dans les séries financières ne permettent pas de prédire le sens des variations futures. Les modèles économétriques disponibles à présent offrent souvent un «hit score» insuffisant (<60%) pour réussir des tentatives fructueuses de «market timing». Une contribution de ce travail se trouve dans l'introduction du concept de complexité algorithmique en finance. Une approche générale est proposée pour estimer la «complexité de Kolmogorov» des séries de rentabilités: après un processus «discrétisation-effacement», des algorithmes de compression sans perte sont utilisés pour détecter des structures régulières qui ne sont pas toujours visibles aux yeux des tests statistiques. En étudiant le degré d'aléa des principaux marchés internationaux à une fréquence «tick-by-tick», on constate une complexité plus élevée pour Euronext-Paris que pour le NYSE et le NASDAQ. Nous expliquons ce résultat par une auto-corrélation plus élevée des volatilités inter-journalières aux Etats-Unis qu'en France. L'inefficacité de «market timing» étant soutenue aussi bien par les théories financières que par les observations empiriques, nous définissons la notion de «battre le marché» dans ce sens spécifique avec un modèle mathématique qui s'inscrit dans le cadre de la calculabilité. / This doctoral dissertation examines different notions of financial randomness and regularity. We show that main financial theories (i.e. market efficiency, behavioral finance and the so-called ``conventionalist approach'') support the impossibility of outperforming the ``buy and hold'' strategy. This point is confirmed by statistical works since regularities identified in financial time series do not help to predict the direction of future returns. To the best of our knowledge, available econometric models often provide too low ``hit scores'' (< 60%) to become successful trading rules. A conceptuel contribution of this work lies in the introduction of algorithmic complexity to finance. A general approach is proposed to estimate the ``Kolmogorov complexity'' of financial returns: lossless compression tools are used to detect regular patterns which could be overlooked by statistical tests. By studying tick-by-tick data from major stock markets, we find a higher complexity for the Euronext-Paris data than for the NYSE and the NASDAQ ones. This result can be explained by their intraday volatility autocorrelations. Supported both by financial theories and by empirical observations, impossibility to outperform the ``buy and hold'' strategy is linked to the common expression ``to outperform the market'' by a new definition for ``unbeatable strings''. With computable functions modeling effective trading rules, a price sequence is said to be ``unbeatable'' if no effective trading rule can generate indefinitely more profits than the ``buy and hold'' alternative.

In this dissertation, we analyze Kolmogorov's superposition theorem for high dimensions. Our main goal is to explore and demonstrate the feasibility of an accurate implementation of Kolmogorov's theorem. First, based on Lorentz's ideas, we provide a thorough discussion on the proof and its numerical implementation of the theorem in dimension two. We present computational experiments which prove the feasibility of the theorem in applications of low dimensions (namely, dimensions two and three). Next, we present high dimensional extensions with complete and detailed proofs and provide the implementation that aims at applications with high dimensionality. The amalgamation of these ideas is evidenced by applications in image (two dimensional) and video (three dimensional) representations, the content based image retrieval, video retrieval, de-noising and in-painting, and Bayesian prior estimation of high dimensional data from the fields of computer vision and image processing.

Notre travail sur le partage de secret se base sur les points de vue théoriques de la Théorie de l'Information de Shannon et de la Complexité de Kolmogorov. Nous allons expliquer comment ces trois sujets intimement liés.Les inégalité d'information jouent un rôle centrale dans ce manuscrit. Ce sont les inégalités pour l'entropie de Shannon, mais correspondent aussi aux inégalités pour la complexité de Kolmogorov.La complexité de Kolmogorov formalise l'idée d'aléatoire pour les chaînes de caractère. Ce sont là deux raisons qui justifient à elles seules la notion de partage de secret algorithmique dans le cadre de la Théorie Algorithmique de l'information (si l'on sait partager un secret aléatoire, on peut partager n'importe quel secret).Originalement étudié par sa définition combinatoire, le partage de secret a été plus tard généralisé par sa formulation par les quantités définies dans la théorie de l'information. Cette étape a permis l'utilisation des inégalités d'information et s'est révélée très importante dans la caractérisation desschémas de partage de secret efficaces.L'étude des inégalités d'information n'en est qu'à ses débuts. Nous y contribuons en introduisant la notion d'inégalité essentiellement conditionnelles, qui montre une fois de plus que ces inégalités ne sont pas encore complètement comprises. / Our work deals with secret sharing in the theoretical point of views of Shannon's Information Theory and Kolmogorov's Algorithmic Information Theory. We are going to explain how these three subjects are naturally deeply intertwined.Information inequalities play a central role in this text. They are the inequalities for Shannon entropy, but also they are in exact correspondence with the inequalities for Kolmogorov complexity. Kolmogorov complexity formalizes the idea of randomness for strings.These two reasons alone justify to consider the notion of secret sharing in the Algorithmic framework (if one can share a random secret one can share anything).Originally, secret sharing was first studied under the combinatorial lens, only later was it more generally formalized using information-theoretic measures. This step allowed the use of information inequalities which revealed to bevery important to understand the existence of secret-sharing schemes with respect to efficiency.The investigation of information inequalities is at its debut. We contribute to the subject by introducing the notion of essentially conditional inequalities, which shows once again that information inequalities are yet not fully understood.

Les méthodes classiques d'apprentissage automatique reposent souvent sur une hypothèse simple mais restrictive: les données du passé et du présent sont générées selon une même distribution. Cette hypothèse permet de développer directement des garanties théoriques sur la précision de l'apprentissage. Cependant, elle n'est pas réaliste dans un grand nombre de domaines applicatifs qui ont émergé au cours des dernières années.Dans cette thèse, nous nous intéressons à quatre problèmes différents en intelligence artificielle, unis par un point commun: tous impliquent un transfer de connaissance d'un domaine vers un autre. Le premier problème est le raisonnement par analogie et s'intéresse à des assertions de la forme "A est à B ce que C est à D". Le second est l'apprentissage par transfert et se concentre sur des problèmes de classification dans des contextes où les données d'entraînement et de test ne sont pas de même distribution (ou n'appartiennent même pas au même espace). Le troisième est l'apprentissage sur flux de données, qui prend en compte des données apparaissant continument une à une à haute fréquence, avec des changements de distribution. Le dernier est le clustering collaboratif et consiste à faire échanger de l'information entre algorithmes de clusterings pour améliorer la qualité de leurs prédictions.La principale contribution de cette thèse est un cadre général pour traiter les problèmes de transfer. Ce cadre s'appuie sur la notion de complexité de Kolmogorov, qui mesure l'information continue dans un objet. Cet outil est particulièrement adapté au problème de transfert, du fait qu'il ne repose pas sur la notion de probabilité tout en étant capable de modéliser les changements de distributions.En plus de cet effort de modélisation, nous proposons dans cette thèse diverses discussions sur d'autres aspects ou applications de ces problèmes. Ces discussions s'articulent autour de la possibilité de transfert dans différents domaines et peuvent s'appuyer sur d'autres outils que la complexité. / Classical learning methods are often based on a simple but restrictive assumption: The present and future data are generated according to the same distributions. This hypothesis is particularly convenient when it comes to developing theoretical guarantees that the learning is accurate. However, it is not realistic from the point of view of applicative domains that have emerged in the last years.In this thesis, we focus on four distinct problems in artificial intelligence, that have mainly one common point: All of them imply knowledge transfer from one domain to the other. The first problem is analogical reasoning and concerns statements of the form "A is to B as C is to D". The second one is transfer learning and involves classification problem in situations where the training data and test data do not have the same distribution (nor even belong to the same space). The third one is data stream mining, ie. managing data that arrive one by one in a continuous and high-frequency stream with changes in the distributions. The last one is collaborative clustering and focuses on exchange of information between clustering algorithms to improve the quality of their predictions.The main contribution of this thesis is to present a general framework to deal with these transfer problems. This framework is based on the notion of Kolmogorov complexity, which measures the inner information of an object. This tool is particularly adapted to the problem of transfer, since it does not rely on probability distributions while being able to model the changes in the distributions.Apart from this modeling effort, we propose, in this thesis, various discussions on aspects and applications of the different problems of interest. These discussions all concern the possibility of transfer in multiple domains and are not based on complexity only.