一种小样本集可信向量机3S—CSVM

利用支持向量机中的拉格朗日系数,从系数所表达的意义出发,根据Kolmogorov算法随机性理论,定义了可信度和可靠性,提出了一种小样本集可信向量机,该向量机在预测对象类别的同时,给出本次预测的可信程度和可靠性,丰富了支持向量机的输出信息。同时通过在预测的过程中有限增加训练集中的有用特征信息,提高了预测的准确率,在只有少量训练样本的情况下具有较好的性能。     

Depth as Randomness Deficiency

Depth of an object concerns a tradeoff between computation time and excess of program length over the shortest program length required to obtain the object. It gives an unconditional lower bound on the computation time from a given program in absence of auxiliary information. Variants known as logical depth and computational depth are expressed in Kolmogorov complexity theory. We derive quantitative relation between logical depth and computational depth and unify the different depth notions by relating them to A. Kolmogorov and L. Levin’s fruitful notion of randomness deficiency. Subsequently, we revisit the computational depth of infinite strings, study the notion of super deep sequences and relate it with other approaches.     

Two Sources Are Better than One for Increasing the Kolmogorov Complexity of Infinite Sequences

The randomness rate of an infinite binary sequence is characterized by the sequence of ratios between the Kolmogorov complexity and the length of the initial segments of the sequence. It is known that there is no effective procedure that transforms one input sequence into another sequence with higher randomness rate. By contrast, we display such a uniform effective procedure having as input two independent sequences with positive but arbitrarily small constant randomness rate. Moreover the transformation is a truth-table reduction and the output has randomness rate arbitrarily close to 1.     

COINCIDENCES ARE NOT ACCIDENTAL: A THEOREM

In this paper, we formalize and prove the statement that coincidences cannot be accidental, a statement that underlies many useful heuristics in mathematics and physics. Our proof uses a version of Kolmogorov complexity, a technique originally developed to describe randomness and "accidentalness."     

Kolmogorov's Contributions to the Foundations of Probability

Andrei Nikolaevich Kolmogorov was the foremost contributor to the mathematical and philosophical foundations of probability in the twentieth century, and his thinking on the topic is still potent today. In this article we first review the three stages of Kolmogorov's work on the foundations of probability: (1) his formulation of measure-theoretic probability, 1933; (2) his frequentist theory of probability, 1963; and (3) his algorithmic theory of randomness, 1965–1987. We also discuss another approach to the foundations of probability, based on martingales, which Kolmogorov did not consider.     

Prequential randomness and probability

This paper studies Dawid’s prequential framework from the point of view of the algorithmic theory of randomness. Our first main result is that two natural notions of randomness coincide. One notion is the prequential version of the measure-theoretic definition due to Martin-Löf, and the other is the prequential version of the game-theoretic definition due to Schnorr and Levin. This is another manifestation of the close relation between the two main paradigms of randomness. The algorithmic theory of randomness can be stripped of its algorithmic aspect and still give meaningful results; the measure-theoretic paradigm then corresponds to Kolmogorov’s measure-theoretic probability and the game-theoretic paradigm corresponds to game-theoretic probability. Our second main result is that measure-theoretic probability coincides with game-theoretic probability on all analytic (in particular, Borel) sets.     

A Tight Upper Bound on Kolmogorov Complexity and Uniformly Optimal Prediction

This paper links the concepts of Kolmogorov complexity (in complexity theory) and Hausdorff dimension (in fractal geometry) for a class of recursive (computable) ω -languages. It is shown that the complexity of an infinite string contained in a Σ ₂ -definable set of strings is upper bounded by the Hausdorff dimension of this set and that this upper bound is tight. Moreover, we show that there are computable gambling strategies guaranteeing a uniform prediction quality arbitrarily close to the optimal one estimated by Hausdorff dimension and Kolmogorov complexity provided the gambler's adversary plays according to a sequence chosen from a Σ ₂ -definable set of strings. We provide also examples which give evidence that our results do not extend further in the arithmetical hierarchy. Received February 1995, and in revised form February 1997, and in final form October 1997.     

Time complexity and model complexity of fast identification ofcontinuous-time LTI systems

The problem of fast identification of continuous-time systems is formulated in the metric complexity theory setting. It is shown that the two key steps to achieving fast identification, i.e., optimal input design and optimal model selection, can be carried out independently when the true system belongs to a general a priori set. These two optimization problems can be reduced to standard Gel'fand and Kolmogorov n-width problems in metric complexity theory. It is shown that although arbitrarily accurate identification can be achieved on a small time interval by reducing the noise-signal ratio and designing the input carefully, identification speed is limited by the metric complexity of the a priori uncertainty set when the noise/signal ratio is fixed     

Extracting Kolmogorov complexity with applications to dimension zero-one laws

We apply results on extracting randomness from independent sources to “extract” Kolmogorov complexity. For any α,?>0, given a string x with K(x)>α|x|, we show how to use a constant number of advice bits to efficiently compute another string y, |y|=Ω(|x|), with K(y)>(1-?)|y|. This result holds for both unbounded and space-bounded Kolmogorov complexity.We use the extraction procedure for space-bounded complexity to establish zero-one laws for the strong dimensions of complexity classes within ESPACE. The unbounded extraction procedure yields a zero-one law for the constructive strong dimensions of Turing degrees.     

算法随机性置信支持向量机及其签名认证

根据 Kolmogorov算法随机性理论 ,描述定义了具有置信判别能力的置信学习机器 .利用普通支持向量学习机器中的 L agrangian系数 ,从系数基本的物理内涵出发 ,近似实现了 Kolmogorov算法随机性理论定义的普适不可计算的随机性描述函数 .并由此定义了学习的置信度 ,使得支持向量学习机在学习判断对象类别的同时能够给出该次判断的可信程度 ,丰富了学习机器的输出信息 .将置信支持向量机用于认证手写签名的特征向量 ,提高了在线手写签名认证应用系统的可靠性和灵活性     

Between Order and Chaos: The Quest for Meaningful Information

The notion of meaningful information seems to be associated with the sweet spot between order and chaos. This form of meaningfulness of information, which is primarily what science is interested in, is not captured by both Shannon information and Kolmogorov complexity. In this paper I develop a theoretical framework that can be seen as a first approximation to a study of meaningful information. In this context I introduce the notion of facticity of a data set. I discuss the relation between thermodynamics and algorithmic complexity theory in the context of this problem. I prove that, under adequate measurement conditions, the free energy of a system in the world is associated with the randomness deficiency of a data set with observations about this system. These insights suggest an explanation of the efficiency of human intelligence in terms of helpful distributions. Finally I give a critical discussion of Schmidhuber’s views specifically his notion of low complexity art, I defend the view that artists optimize facticity instead. This project is supported by a BSIK grant from the Dutch Ministry of Education, Culture and Science (OC&W) and is part of the ICT innovation program of the Ministry of Economic Affairs (EZ).     

The Kolmogorov complexity of real numbers

We consider for a real number α the Kolmogorov complexities of its expansions with respect to different bases. In the paper it is shown that, for usual and self-delimiting Kolmogorov complexity, the complexity of the prefixes of their expansions with respect to different bases r and b are related in a way that depends only on the relative information of one base with respect to the other.More precisely, we show that the complexity of the length l·log_rb prefix of the base r expansion of α is the same (up to an additive constant) as the log_rb-fold complexity of the length l prefix of the base b expansion of α.Then we consider the classes of reals of maximum and minimum complexity. For maximally complex reals we use our result to derive a further complexity theoretic proof for the base independence of the randomness of real numbers.Finally, we consider Liouville numbers as a natural class of low complex real numbers.     

Informational aesthetics measures.

The Birkhoff aesthetic measure of an object is the ratio between order and complexity. Informational aesthetics describes the interpretation of this measure from an information-theoretic perspective. From these ideas, the authors define a set of ratios based on information theory and Kolmogorov complexity that can help to quantify the aesthetic experience.     

Kolmogorov Complexity for Possibly Infinite Computations

In this paper we study the Kolmogorov complexity for non-effective computations, that is, either halting or non-halting computations on Turing machines. This complexity function is defined as the length of the shortest input that produce a desired output via a possibly non-halting computation. Clearly this function gives a lower bound of the classical Kolmogorov complexity. In particular, if the machine is allowed to overwrite its output, this complexity coincides with the classical Kolmogorov complexity for halting computations relative to the first jump of the halting problem. However, on machines that cannot erase their output –called monotone machines–, we prove that our complexity for non effective computations and the classical Kolmogorov complexity separate as much as we want. We also consider the prefix-free complexity for possibly infinite computations. We study several properties of the graph of these complexity functions and specially their oscillations with respect to the complexities for effective computations.     

Axiomatizing Kolmogorov Complexity

We revisit the axiomatization of Kolmogorov complexity given by Alexander Shen, currently available only in Russian language. We derive an axiomatization for conditional plain Kolmogorov complexity. Next we show that the axiomatic system given by Shen cannot be weakened (at least in any natural way). In addition we prove that the analogue of Shen??s axiomatic system fails to characterize prefix-free Kolmogorov complexity.     

On Strings with Trivial Kolmogorov Complexity

The Kolmogorov complexity of a string is the length of the shortest program that generates it. A binary string is said to have trivial Kolmogorov complexity if its complexity is at most the complexity of its length. Intuitively, such strings carry no more information than the information that is inevitably coded into their length (which is the same as the information coded into a sequence of 0s of the same length). We study the set of these trivial sequences from a computational perspective, and with respect to plain and prefix-free Kolmogorov complexity. This work parallels the well known study of the set of nonrandom strings (which was initiated by Kolmogorov and developed by Kummer, Muchnik, Stephan, Allender and others) and points to several directions for further research.     

结合注意力机制与LSTM的短期风电功率预测模型

风力发电预测在电力系统的运行中发挥着重要作用。现有风电功率的短期预测模型因风速的复杂性和随机性,难以确定风速与风电功率的非线性映射关系,导致预测精度降低。提出一种结合变分模态分解、双阶段注意力机制、误差修正模块与深度学习算法的短期风电功率预测模型。通过对原始数据进行互信息特征选择,获得与风电功率相关性较强的特征,并对其进行信号预处理,利用变分模态分解对多维特征序列进行分解,得到具有一定中心频率的模态分量,以降低各个特征序列的复杂性和非平稳性。采用基于双阶段注意力机制与编解码架构的长短时记忆（LSTM）神经网络对模态分量进行训练与预测,得到初始预测误差。在此基础上,利用误差修正模块对初始预测误差进行变分模态分解和修正,从而提高模型的预测精度。实验结果表明,与自回归移动平均模型、标准编解码结构的LSTM模型相比,该预测模型的平均绝对误差最高可降低约87%,具有较优的预测性能。