检索结果-内蒙古大学图书馆

algorithmic randomness and Fourier Analysis

THEORY OF COMPUTING SYSTEMS 2019年第3期63卷 567-586页

作者： Franklin, Johanna N. Y. McNicholl, Timothy H. Rute, Jason Hofstra Univ Dept Math Room 306Roosevelt Hall Hempstead NY 11549 USA Iowa State Univ Dept Math Ames IA 50011 USA Penn State Univ Dept Math University Pk PA 16802 USA

Suppose 1 < p < . Carleson's Theorem states that the Fourier series of any function in L-p[-, ] converges almost everywhere. We show that the Schnorr random points are precisely those that satisfy this theor... 详细信息

关键词： Computability Fourier analysis Complex analysis algorithmic randomness Computable analysis

来源：评论

学校读者我要写书评

暂无评论

algorithmic randomness based feature selection for traditional Chinese chronic gastritis diagnosis

引用

NEUROCOMPUTING 2014年 140卷 252-264页

作者： Wang, Huazhen Lv, Bing Yang, Fan Zheng, Kai Li, Xuan Hu, Xueqin Huaqiao Univ Coll Comp Sci & Technol Xiamen 361021 Peoples R China Xiamen Univ Sch Informat Sci & Technol Xiamen 361005 Peoples R China China Acad Chinese Med Sci Inst Informat Tradit Chinese Med Beijing 100700 Peoples R China

Machine learning methods involving multivariate interacting effects have become mainstream in feature selection. However, the feature importance score generated by machine learning methods is not statistically interpretable, which hampers its application in practice like medical diagnosis. In this study, a framework of algorithmic randomness based Feature Selection (ARFS) is proposed to measure the feature importance score using the p-value which derives from the combination of algorithmic randomness test and machine learning methods. In ARFS, a machine learning algorithm, such as random forest (RF), support vector machine (SVM) and naive Bayes classifier (NB) is used to compute the nonconformity score of each example belonging to data distribution, and then the p-value from algorithmic randomness test is obtained from nonconformity scores. ARFS evaluates the importance of each feature with the reduction of p-value on the datasets before and after random permutation of that feature, which makes it statistically interpretable. To demonstrate its efficiency, three ARFS models, i.e. ARFS-RF, ARFS-SVM and ARFS-NB were used to compare with some feature selection approaches, i.e. RF-ACC, RF-Gini, KNNpermute, SMFS, ANOVA and SNR. The results showed that ARFS-RF obtained better performances both on the synthetic and benchmark datasets. Further study on chronic gastritis dataset in Traditional Chinese Medicine (TCM) showed that the symptom sets given by ARFS-RF performs substantially better than that of TCM experts with the same size. The symptom ranking list generated by ARFS-RF can offer counselling for the physician to design, select, and interpret the symptoms in chronic gastritis diagnosis. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Feature selection Feature importance algorithmic randomness Conformal predictor Chronic gastritis Random forests

来源：评论

学校读者我要写书评

暂无评论

algorithmic randomness in empirical data

引用

STUDIES IN HISTORY AND PHILOSOPHY OF SCIENCE 2003年第3期34A卷 633-646页

作者： McAllister, JW Leiden Univ Fac Philosophy NL-2300 RA Leiden Netherlands

According to a traditional view, scientific laws and theories constitute algorithmic compressions of empirical data sets collected from observations and measurements. This article defends the thesis that, to the contrary, empirical data sets are algorithmically incompressible. The reason is that individual data points are determined partly by perturbations, or causal factors that cannot be reduced to any pattern. If empirical data sets are incompressible, then they exhibit maximal algorithmic complexity, maximal entropy and zero redundancy. They are therefore maximally efficient carriers of information about the world. Since, on algorithmic information theory, a string is algorithmically random just if it is incompressible, the thesis entails that empirical data sets consist of algorithmically random strings of digits. Rather than constituting compressions of empirical data, scientific laws and theories pick out patterns that data sets exhibit with a certain noise. (C) 2003 Elsevier Ltd. All rights reserved.

关键词： algorithmic randomness compression empirical data information law pattern

来源：评论

学校读者我要写书评

暂无评论

algorithmic randomness, reverse mathematics, and the dominated convergence theorem

引用

ANNALS OF PURE AND APPLIED LOGIC 2012年第12期163卷 1854-1864页

作者： Avigad, Jeremy Dean, Edward T. Rute, Jason Carnegie Mellon Univ Dept Philosophy Pittsburgh PA 15213 USA Carnegie Mellon Univ Dept Math Sci Pittsburgh PA 15213 USA

We analyze the pointwise convergence of a sequence of computable elements of L-1(2(omega)) in terms of algorithmic randomness. We consider two ways of expressing the dominated convergence theorem and show that, over the base theory RCA(0), each is equivalent to the assertion that every G(delta) subset of Cantor space with positive measure has an element. This last statement is, in turn, equivalent to weak weak Konig's lemma relativized to the Turing jump of any set. It is also equivalent to the conjunction of the statement asserting the existence of a 2-random relative to any given set and the principle of Sigma(2) collection. (C) 2012 Elsevier B.V. All rights reserved.

关键词： algorithmic randomness Reverse mathematics Dominated convergence

来源：评论

学校读者我要写书评

暂无评论

algorithmic randomness in Continuous-Time Markov Chains 57

Algorithmic Randomness in Continuous-Time Markov Chains

引用

57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)

作者： Huang, Xiang Lutz, Jack H. Migunov, Andrei N. Iowa State Univ Dept Comp Sci Ames IA 50011 USA

ISBN: (纸本)9781728131511

In this paper we develop the elements of the theory of algorithmic randomness in continuous-time Markov chains (CTMCs). Our main contribution is a rigorous, useful notion of what it means for an individual trajectory of a CTMC to be random. CTMCs have discrete state spaces and operate in continuous time. This, together with the fact that trajectories may or may not halt, presents challenges not encountered in more conventional developments of algorithmic randomness. Although we formulate algorithmic randomness in the general context of CTMCs, we are primarily interested in the computational power of stochastic chemical reaction networks, which are special cases of CTMCs. This leads us to embrace situations in which the long-term behavior of a network depends essentially on its initial state and hence to eschew assumptions that are frequently made in Markov chain theory to avoid such dependencies. After defining the randomness of trajectories in terms of a new kind of martingale (algorithmic betting strategy), we prove equivalent characterizations in terms of constructive measure theory and Kolmogorov complexity.

关键词： algorithmic randomness continuous time Markov chain chemical reaction network

来源：评论

学校读者我要写书评

暂无评论

Normal numbers and algorithmic randomness: a historical sketch

引用

CURRENT SCIENCE 2014年第12期106卷 1687-1692页

作者： Arvind, V. Inst Math Sci Madras 600113 Tamil Nadu India

What does it mean to say that a fixed infinite string is random? In this article we will attempt to trace the history of this question and the fundamental role of computability theory in our understanding of randomness. In particular, we will describe Turing's observations on the notion of normal numbers and their construction and how that connects up with algorithmic randomness.

关键词： algorithmic randomness computability theory infinite string normal numbers

来源：评论

学校读者我要写书评

暂无评论

引用

INTERNATIONAL JOURNAL OF APPROXIMATE REASONING 2022年 151卷 272-291页

作者： Persiau, Floris De Bock, Jasper de Cooman, Gert Univ Ghent Fdn Lab imprecise probabil Technol Pk Zwijnaarde 125 B-9052 Zwijnaarde Belgium

The field of algorithmic randomness studies, amongst other things, what it means for infinite binary sequences to be random for some given uncertainty model. Classically, martingale-theoretic notions of randomness involve precise uncertainty models, and it is only recently that imprecision has been introduced into this context. As a consequence, the investigation into how imprecision alters our view on martingale-theoretic random sequences has only just begun. In this contribution, where we allow for non-computable uncertainty models, we establish a close and surprising connection between precise and imprecise uncertainty models in this randomness context. In particular, we show that there are stationary imprecise models and non-computable non-stationary precise models that have the exact same set of random sequences. We also give a preliminary discussion of the possible implications of our result for a statistics based on imprecise probabilities, and shed some light on the practical (ir)relevance of both imprecise and non-computable precise uncertainty models in that context. (c) 2022 Elsevier Inc. All rights reserved.

关键词： algorithmic randomness Imprecise probabilities Computability theory Probability intervals Supermartingales Non-stationarity

来源：评论

学校读者我要写书评

暂无评论

Cryptography and algorithmic randomness

引用

THEORY OF COMPUTING SYSTEMS 2015年第3期56卷 544-580页

作者： Tadaki, Kohtaro Doi, Norihisa Chuo Univ Res & Dev Initiat Bunkyo Ku Tokyo 1128551 Japan

The secure instantiation of the random oracle is one of the major open problems in modern cryptography. We investigate this problem using concepts and methods of algorithmic randomness. In modern cryptography, the random oracle model is widely used as an imaginary framework in which the security of a cryptographic scheme is discussed. In the random oracle model, the cryptographic hash function used in a cryptographic scheme is formulated as a random variable uniformly distributed over all possibility of the function, called the random oracle. The main result of this paper is to show that, for any secure signature scheme in the random oracle model, there exists a specific computable function which can instantiate the random oracle while keeping the security originally proved in the random oracle model. In modern cryptography the generic group model is used also for a similar purpose to the random oracle model. We show that the same results hold for the generic group model. In the process of proving the results, we introduce the notion of effective security, demonstrating the importance of this notion in modern cryptography.

关键词： Cryptography Random oracle model Generic group model Provable security algorithmic randomness Computable analysis

来源：评论

学校读者我要写书评

暂无评论

ON ANALOGUES OF THE CHURCH-TURING THESIS IN algorithmic randomness

引用

REVIEW OF SYMBOLIC LOGIC 2016年第3期9卷 456-479页

作者： Porter, Christopher P. Univ Florida Dept Math Gainesville FL 32611 USA

In this article, I consider the status of several statements analogous to the Church-Turing thesis that assert that some definition of algorithmic randomness captures the intuitive conception of randomness. I argue that we should not only reject the theses that have appeared in the algorithmic randomness literature, but more generally that we ought not evaluate the adequacy of a definition of randomness on the basis of whether it captures the so-called intuitive conception of randomness to begin with. Instead, I argue that a more promising alternative is to evaluate the adequacy of a definition of randomness on the basis of whether it captures what I refer to as a "notion of almost everywhere typicality." In support of my main claims, I will appeal to recent work in showing the connection between of algorithmic randomness and certain "almost everywhere" theorems from classical mathematics.

关键词： algorithmic randomness MATHEMATICS ALGORITHMS THEOREMS (Mathematics) FUNCTIONS (Mathematics)

来源：评论

学校读者我要写书评

暂无评论

SOME QUESTIONS OF UNIFORMITY IN algorithmic randomness

引用

JOURNAL OF SYMBOLIC LOGIC 2021年第4期86卷 1612-1631页

作者： Bienvenu, Laurent Csima, Barbara E. Harrison-Trainor, Matthew Univ Bordeaux Lab Bordelais Rech Informat CNRS Bordeaux INP Talence France Univ Waterloo Dept Pure Math Waterloo ON Canada Univ Michigan Dept Math Ann Arbor MI 48109 USA

The SI numbers the halting probabilities of universal prefix-free machines are known to be exactly the Martin-Lof random left-c.e. reals. We show that one cannot uniformly produce, from a Martin-L5f random left-c.e. real a, a universal prefix-free machine U whose halting probability is a. We also answer a question of Barmpalias and Lewis-Pye by showing that given a left-c.e. real a, one cannot uniformly produce a left-c.e. real 13 such that a 13 is neither left-c.e. nor right-c.e.

关键词： algorithmic randomness Kolmogorov complexity

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：