There has been an explosion of growth in using AI, data science, and machine learning in all aspects of our daily life. There is a global competition among governments, industry, and academic institutions to lead research and development in this area. This paper discusses a novel multidisciplinary graduate education and research program at our institution to help develop a trained workforce to meet the demands required to understand and develop AI, data science and machine learning technologies. The program brings together faculty and students in engineering, computer science, and social science to build a traineeship program where cohort teams study fundamental and applied data science research, using compact modules across courses to personalize instruction and prepare each trainee with skills tailored to their prior experience and future career goals.

Logistic Regression is a widely used generalized linear model applied in classification settings to assign probabilities to class labels. It is also well known that logistic regression is a maximum entropy procedure subject to what are sometimes called the balance conditions. The dominant view in existing explanations are all discriminative, i.e., modeling labels given the data. This paper adds to the maximum entropy interpretation, establishing a generative, maximum entropy explanation for the commonly used logistic regression training and optimization procedures. We show that logistic regression models the conditional distribution on the instance space given class labels with a maximum entropy model subject to a first moment constraint on the training data, and that the commonly used fitting procedure would be a Monte-Carlo fit for the generative view.

This paper develops bounds for learning lossless source coding under the PAC (probably approximately correct) framework. The paper considers iid sources with online learning: first the coder learns the data structure from training sequences. When presented with a test sequence for compression, it continues to learn from/adapt to the test sequence. The results show, not unsurprisingly, that there is little gain from online learning when the training sequence length is much longer than the test sequence length. But if the test sequence length is longer than the training sequence, there is a significant gain. Coders for online learning has a somewhat surprising structure: the training sequence is used to estimate a confidence interval for the distribution, and the coding distribution is found through a prior distribution over this interval.

We study universal compression of n i.i.d. copies of a k−variate Gaussian random vector, when the mean is an unknown vector in an Euclidean ball of ℝk, and the covariance is known. We adopt the high dimensional scaling k = Θ(n) to bring out a compression perspective on the inadmissibility of unbiased estimates of a k−variate Gaussian (when k ≥ 3), in particular focusing on the optimal unbiased Maximum Likelihood estimate. We use arguments based on the redundancy-capacity theorem to show that the redundancy of a universal compressor in this high dimensional setting must be lower bounded as Θ(n). We show that natural compression schemes based on the Maximum Likelihood estimate of the mean have suboptimal Θ(n log n) redundancy, but a scheme based on the James-Stein biased estimate of the mean incurs redundancy that is also Θ(n).

Many current applications in data science need rich model classes to adequately represent the statistics that may be driving the observations. Such rich model classes may be too complex to admit uniformly consistent estimators. In such cases, it is conventional to settle for estimators with guarantees on convergence rate where the performance can be bounded in a model-dependent way, i.e. pointwise consistent estimators. But this viewpoint has the practical drawback that estimator performance is a function of the unknown model within the model class that is being estimated. Even if an estimator is consistent, how well it is doing at any given time may not be clear, no matter what the sample size of the observations. In these cases, a line of analysis favors sample dependent guarantees. We explore this framework by studying rich model classes that may only admit pointwise consistency guarantees, yet enough information about the unknown model driving the observations needed to gauge estimator accuracy can be inferred from the sample at hand. In this paper we obtain a novel characterization of lossless compression problems over a countable alphabet in the data-derived framework in terms of what we term deceptive distributions. We also show that the ability to estimate the redundancy of compressing memoryless sources is equivalent to learning the underlying single-letter marginal in a data-derived fashion. We expect that the methodology underlying such characterizations in a data-derived estimation framework will be broadly applicable to a wide range of estimation problems, enabling a more systematic approach to data-derived guarantees.

Using only samples from a probabilistic model, we predict properties of the model and of future observations. The prediction game continues in an online fashion as the sample size grows with new observations. After each prediction, the predictor incurs a binary (0-1) loss. The probability model underlying a sample is otherwise unknown except that it belongs to a known class of models. The goal is to make finitely many errors (i.e. loss of 1) with probability 1 under the generating model, no matter what it may be in the known model class. Model classes admitting predictors that make only finitely many errors are eventually almost surely (eas) predictable. When the losses incurred are observable (the supervised case), we completely characterize eas predictable classes. We provide analogous results in the unsupervised case. Our results have a natural interpretation in terms of regularization. In eas-predictable classes, we study if it is possible to have a universal stopping rule that identifies (to any given confidence) when no more errors will be made. Classes admitting such a stopping rule are eas learnable. When samples are generated iid, we provide a complete characterization of eas learnability. We also study cases when samples are not generated iid, but a full characterization remains open at this point.

We study the problem of online learning a hypothesis class and a given binary 0-1 loss function, using instances generated $i.i.d.$ by a given distribution. The goal of the online learner is to make only finitely many errors (loss 1) with probability $1$ in the infinite horizon. In the binary label case, we show that hypothesis classes are online learnable in the above sense if and only if the class is effectively countable. We extend the results to hypothesis classes where labels can be non-binary. Characterization of non-binary online learnable classes is more involved for general loss functions and is not captured fully by the countability condition even for the ternary label case. In the computational bounded setup, we compare our results with well known results in recursive function learning, showing that the class of all total computable functions is indeed learnable with computable online learners and randomized sampling. Finally, we also show that the finite error guarantee will not be affected even when independent noise is added to the label.

We study the problem of estimating properties of dynamic graphical models in the non-asymptotic regime. Instead of characterizing the behavior of estimation rules with asymptotic consistency, we study sharp bounds on the sample size required to estimate the properties. We show that for certain spatio-temporal Markov random fields governed by an underlying graph, one can estimate certain natural properties with logarithmic (w.r.t. the size of the underlying graph) sample complexity. Matching lower bounds are also established for such estimation problems. We highlight our results with a “bit river” abstraction, where a Bernoulli source at one node flows along the edges of an underlying graph, and the task is to obtain the flow trajectory. If we do not have any restriction on the model class under consideration, we also show that an exponential sample size is required for even very simple properties.

Let P be a class of distributions over natural numbers, and A be a subset of ℝ+. We study the problem of deciding, using i.i.d. samples X1,X2,... from an unknown p ∈ P, whether the entropy H(p) is in A or not. The decision is updated based on every new observation Xn-we are interested in decision rules that make only finitely many errors no matter what the underlying source is. We give necessary and sufficient conditions on the class P and A that can be decided with only finitely many errors. We show for example that such rules exist for testing the rationality of entropy within a given interval, for testing if the entropy falls in an interval of form (a,b], but no such decision rule exists to determine if the entropy is finite or if the entropy falls in an interval of form [a,b]. In the process, we also highlight the conceptual foundation this framework shares with regularization.

We completely characterize the asymptotic per-symbol average case redundancy of any collection P of i.i.d. distributions over a countably infinite alphabet. We prove that universal compression of length-n i.i.d. sequences from a class P is characterized by how well the tails of of the single letter marginals of P can be universally described. We capture this notion by the tail redundancy of a class P$ of distributions, and develop on the properties of tail redundancy.

We study the problem of predicting upper bounds on the next draw of an unknown probability distribution after observing a sample generated by it. The unknown distribution is modeled as belonging to a class P of distributions over natural numbers. The goal is to err only finitely many times even though the game proceeds over an infinite horizon, and though there is no upper bound on what the next sample can be. If a universal prediction scheme exists that makes only finitely many errors regardless of what model in P generated the data, we say P is eventually almost surely (e.a.s.) predictable. In this paper, we fully characterize when P can be e.a.s.-predictable.

We study the redundancy of universally compressing strings X1, ...,Xn generated by a binary Markov source p without any bound on the memory. To better understand the connection between compression and estimation in the Markov regime, we consider a class of Markov sources restricted by a continuity condition. In the absence of an upper bound on memory, the continuity condition implies that p(X0|X-m-1) gets closer to the true probability p(X0|X-∞-1) as m increases, rather than vary around arbitrarily. For such sources, we prove asymptotically matching upper and lower bounds on the redundancy. In the process, we identify what sources in the class matter the most from a redundancy perspective.

The jackknife resampling procedure is a technique to reduce the bias of a statistic. As with other resampling techniques, the jackknife procedure is motivated by and is well understood in the i.i.d. regime. However, analysis of the procedure when samples have memory is limited, and is predominantly restricted to cases with strong mixing or memory constraints. In this paper, we analyze a natural jackknife resampling procedure for Markov sources with no mixing assumptions. For the problem to be well posed without mixing assumptions, we instead adopt a physically motivated continuity condition that ensures that the information a bit in the past provides about the current bit, conditioned on all bits in between, diminishes with the amount of history we have. We analyze the jackknife estimate of the variance of conditional probability estimates given arbitrary contexts, and show that the bias of this jackknife procedure can be bounded by a small constant.

In the write process of multilevel per cell (MLC) flash memories, an iterative approach is used to mitigate the monotonicity problem. The monotonicity in programming is considered to be the major restriction in MLC flash. To solve this issue, an iterative approach called incremental step pulse programming (ISPP) is used to concurrently program lots of cells in small steps. In this paper, we are mostly concerned with deriving a mathematical model for iterative programming using the framework of renewal theory. We obtain a closed-form approximation for the probability distribution of the number of steps required in the ISPP process. We also bound the maximal error between the true distribution and our approximation. Moreover, the results obtained help to accurately analyze the effect of inter-cell interference in this type of memory. Finally, we devise an adaptive step size approach for write process to strike a balance between latency and lifetime under fixed bit error rate constraints or information rate constraints.

The task of community detection in a graph formalizes the intuitive task of grouping together subsets of vertices such that vertices within clusters are connected tighter than those in disparate clusters. This paper approaches community detection in graphs by constructing Markov random walks on the graphs. The mixing properties of the random walk are then used to identify communities. We use coupling from the past as an algorithmic primitive to translate the mixing properties of the walk into revealing the community structure of the graph. We analyze the performance of our algorithms on specific graph structures, including the stochastic block models (SBM) and LFR random graphs.

In the write process of multilevel per cell (MLC) flash memories, an iterative approach is used to mitigate the monotonicity problem. The monotonicity in programming is considered to be the major restriction in MLC flash. In this paper, we are mostly concerned with deriving a mathematical model for iterative programming using the framework of “renewal processes”. Then, we approximate the maximum number of steps in iterative programming, and obtain the voltage distribution in flash due to iterative programming. Moreover, the obtained results help us to accurately analyze the effect of inter-cell interference (ICI) in this type of memory. Finally, we obtain a more precise voltage distribution for the symbol states in flash memory. Simulation results show the effect of varying the step size in the iterative programming and the effect of ICI on the information rate.

We are concerned with the optimal detector design for the all-bit-line MLC flash memory. We provide a channel model of the MLC flash memory, where the channel parameters are mathematically tractable. Then we present an optimal maximum a-posteriori sequence detector. The optimal detector can be executed over a trellis whose branch metrics can be computed by using Fourier transforms of analytically computable characteristic functions (corresponding to likelihood functions). The soft-output detectors for both simple one-dimensional channel models and more realistic page-orientated two-dimensional channel models are derived. Simulation results show not only that the soft-output detector has the same hard-output bit-error-rate performance as some previously known detectors did, but that the soft-output detector outperforms previously known detectors by a gain of 0.23 dB.

In applications involving estimation, the relevant model classes of probability distributions are often too complex to admit estimators that converge to the truth with convergence rates that can be uniformly bounded over the entire model class as the sample size increases (uniform consistency). While it is often possible to get pointwise guarantees, so that the convergence rate of the estimator can be bounded in a model-dependent way, such pointwise gaurantees are unsatisfactory - estimator performance is a function of the very unknown quantity that is being estimated. Therefore, even if an estimator is consistent, how well it is doing may not be clear no matter what the sample size. Departing from this traditional uniform/pointwise dichotomy, a new analysis framework is explored by characterizing model classes of probability distributions that may only admit pointwise guarantees, yet where all the information about the unknown model needed to gauge estimator accuracy can be inferred from the sample at hand. To provide a focus to this suggested broad new paradigm, we analyze the universal compression problem in this data-driven pointwise consistency framework.

In this paper we derive the optimal detector for multilevel cell (MLC) flash memory channels with intercell interference (ICI). We start with the MLC channel model proposed by Dong et al. and just slightly alter the model to guarantee mathematical tractability of the optimal detectors (maximum likelihood and maximum a-posteriori sequence and symbol detectors). The optimal detector is obtained by computing branch metrics using Fourier transforms of analytically computable characteristic functions (corresponding to likelihood functions). We derive the detectors for both simple one-dimensional (1D) channel models and more realistic page-orientated two-dimensional (2D) channel models. Simulation results show that the hard-output bit error rate (BER) performance matches some previously known detectors, but that the soft-output detector outperforms previously known detectors by 0.35 dB.

We observe a length-n sample generated by an unknown, stationary ergodic Markov process (model) over a finite alphabet A. Given any string w of symbols from A we want estimates of the conditional probability distribution of symbols following w, as well as the stationary probability of w. Two distinct problems that complicate estimation in this setting are: 1) long memory and 2) slow mixing, which could happen even with only one bit of memory. Any consistent estimator in this setting can only converge pointwise over the class of all ergodic Markov models. Namely, given any estimator and any sample size n, the underlying model could be such that the estimator performs poorly on a sample of size n with high probability. But can we look at a length-n sample and identify if an estimate is likely to be accurate? Since the memory is unknown a-priori, a natural approach is to estimate a potentially coarser model with memory kn= O(log n). As n grows, pointwise consistent estimates that hold eventually almost surely (e.a.s.) are known so long as the scaling of knis not superlogarithmic in n. Here, rather than e.a.s. convergence results, we want the best answers possible with a length-n sample. Combining results in universal compression with Aldous' coupling arguments, we obtain sufficient conditions on the lengthn sample (even for slow mixing models) to identify when naive: 1) estimates of the conditional probabilities and 2) estimates related to the stationary probabilities are accurate, and also bound the deviations of the naive estimates from true values.

We consider estimation of binary channels with memory where the transition probabilities (channel parameters) from the input to output are determined by prior outputs (state of the channel). While the channel is unknown, we observe the joint input/output process of the channel - we have n i.i.d. input bits and their corresponding outputs. Motivated by applications related to the backplane channel, we want to estimate the channel parameters as well as the stationary probabilities for each state. Two distinct problems complicate estimation in this setting: (i) long memory, and (ii) slow mixing which could happen even with only one bit of memory. In this setting, any consistent estimator can only converge pointwise over the model class. Namely, given any estimator and any sample size n, the underlying model could be such that the estimator performs poorly on a sample of size n with high probability. But can we look at a length-n sample and identify if an estimate is likely to be accurate? Since the memory is unknown a-priori, a natural approach, known to be consistent, is to estimate a potentially coarser model with memory kn= αnlog n, where αnis a function that grows O(1). Note however that (i) the coarser model is estimated using only samples from the true model; and (ii) we want the best possible answers with a length-n sample, rather than just consistency. Combining results on universal compression and Aldous' coupling arguments, we obtain sufficient conditions (even for slow mixing models) to identify when naive (i) estimates of the channel parameters and (ii) estimates related to the stationary probabilities of the channel states are accurate, and bound their deviations from true values.

We consider a class of small-sample distribution estimators over noisy channels. Our estimators are designed for repetition channels, and rely on properties of the runs of the observed sequences. These runs are modeled via special types of Markov chains, termed “alternating Markov chains”. We show that alternating chains have redundancy that scales sub-linearly with the lengths of the sequences, and describe how to use a distribution estimator for alternating chains for the purpose of distribution estimation over repetition channels.

The problem of graphical model selection is to estimate the graph structure of a Markov random field given samples from it. We analyze the information-theoretic limitations of the problem of graph selection for binary Markov random fields under high-dimensional scaling, in which the graph size and the number of edges k, and/or the maximal node degree d, are allowed to increase to infinity as a function of the sample size n. For pair-wise binary Markov random fields, we derive both necessary and sufficient conditions for correct graph selection over the class Gp,kof graphs on vertices with at most k edges, and over the class Gp,dof graphs on p vertices with maximum degree at most d. For the class Gp,k, we establish the existence of constants c and c' such that if n; c' k2log p. Similarly, for the class Gp,d, we exhibit constants c and c' such that for n2log p, any method fails with probability at least 1/2, and we demonstrate a graph decoder that succeeds with high probability for n >; c' d3log p.

We consider the problem of classification, where the data of the classes are generated i.i.d. according to unknown probability distributions. The goal is to classify test data with minimum error probability, based on the training data available for the classes. The Likelihood Ratio Test (LRT) is the optimal decision rule when the distributions are known. Hence, a popular approach for classification is to estimate the likelihoods using well known probability estimators, e.g., the Laplace and Good-Turing estimators, and use them in a LRT. We are primarily interested in situations where the alphabet of the underlying distributions is large compared to the training data available, which is indeed the case in most practical applications. We motivate and propose LRT's based on pattern probability estimators that are known to achieve low redundancy for universal compression of large alphabet sources. While a complete proof for optimality of these decision rules is warranted, we demonstrate their performance and compare it with other well-known classifiers by various experiments on synthetic data and real data for text classification.

In statistics and theoretical computer science, the notion of exchangeability provides a framework for the study of large alphabet scenarios. This idea has been developed in an important line of work starting with Kingman's study of population genetics, and leading on to the paintbox processes of Kingman, the Chinese restaurant processes and their generalizations. In information theory, the notion of the pattern of a sequence provides a framework for the study of large alphabet scenarios, as developed in work of Orlitsky and collaborators. The pattern is a statistic that captures all the information present in the data, and yet is universally compressible regardless of the alphabet size. In this note, connections are made between these two lines of work- specifically, patterns are examined in the context of exchangeability. After observing the relationship between patterns and Kingman's paintbox processes, and discussing the redundancy of a class of mixture codes for patterns, alternate representations of patterns in terms of graph limits are discussed.

We consider the problem of estimating unknown source distributions based on a small number of possibly erroneous observations. Errors are modeled as arising from sticky channels, which introduce repetitions of transmitted source symbols. Both the problems of estimating the distribution for known and unknown channel parameters are considered. We propose three heuristic algorithms and a method based on Expectation-Maximization for solving the problem. These algorithms represent a combination of iterative optimization techniques and Good-Turing estimators.

Modeling the joint expression patterns of genes is a challenging task due to the large number of genes simultaneously studied, relative to the amount of microarray data available. To model the joint expression profiles of genes using a small number of observations, we use Ising models to approximate the joint expression profiles. This approach naturally lends itself to the study of gene interactions and has a close connection to clustering techniques, which we use to reconstruct E. coli gene interaction pathways from microarray data. In addition, we note that extending available partial network topology information can be done using very few microarray samples-logarithmic in the number of genes.

Standard redundancy measures the excess number of bits needed to compress a sequence as a function of the sequence’s length. Since long sequences can have arbitrarily low minimum description length (MDL), even low standard redundancy can be arbitarily high compared to the sequence’s MDL. By contrast, relative redundancy evaluates the excess number of bits as a function of the sequence’s MDL. Hence unlike standard redundancy, low relative redundancy implies that the number of bits needed to compress any sequence is essentially the lowest possible. Results in [1] show that for iid distributions over binary alphabets, block relative redundancy essentially equals block standard redundancy while sequential relative redundancy is about twice its standard counterpart. We show that unlike binary alphabets, for larger alphabets both block and sequential relative redundancy essentially equal their standard counterparts. We also define and determine expected relative redundancy and show that it is almost same as worst-case relative redundancy.

The problem of graphical model selection is to correctly estimate the graph structure of a Markov random field given samples from the underlying distribution. We analyze the information-theoretic limitations of this problem under high-dimensional scaling, in which the graph size p and the number of edges k (or the maximum degree d) are allowed to increase to infinity as a function of the sample size n. For pairwise binary Markov random fields, we derive both necessary and sufficient conditions on the scaling of the triplet (n, p, k) (or the triplet (n, p, d)) for asympotically reliable reocovery of the graph structure.

We estimate the population size by sampling uniformly from the population. Given an accuracy to which we need to estimate the population with a pre-specified confidence, we provide a simple stopping rule for the sampling process.

We propose a new sequential, adaptive, quadratic-time algorithm for variable-rate lossy compression of memoryless sources at a fixed distortion. The algorithm uses approximate pattern matching and is modeled after the Lempel-Ziv algorithm. As a key new idea, the algorithm uses lower mutual information to carefully select "good" codewords. For Bernoulli sources with Hamming distortion, we empirically demonstrate that the algorithm (a) discovers the optimal reproduction type, (b) leads to absence of multiple matches, and (c) seems to approach the rate-distortion coding rate. Based on empirical observations, we formulate two conjectures that could imply that the algorithm is asymptotically optimal for memoryless sources.

Standard redundancy measures the excess number of bits required to encode a sequence of a given length when the underlying distribution is not known. Relative redundancy measures the same increase, but as a function of the sequence's minimum description length. We consider the relative redundancy of i.i.d. distributions over large alphabets and show that, like standard redundancy, relative redundancy too increases with the alphabet size. We then consider compression of patterns of i.i.d. strings. Again analogous to standard redundancy, we show that the relative redundancy of patterns of large, or even infinite alphabet i.i.d. distributions is negligible compared to the patterns' minimum description length

Building on [1], [5], we model probability distributions from data using the high profile distribution. We show that the high profile distribution is majorized by the empirical frequency distribution, that the support of high profile distributions can be mixed, namely the distribution can have both discrete and continuous components, and obtain the high profile distribution for certain profiles. We then experimentally compare the high profile distribution with certain estimators that have been studied in statistics literature for the species estimation problem.

We determine the entropy rate of patterns of certain random processes including all finite-entropy stationary processes. For independent and identically distributed (i.i.d.) processes, we also bound the speed at which the per-symbol pattern entropy converges to this rate, and show that patterns satisfy an asymptotic equipartition property. To derive some of these results we upper bound the probability that the nth variable in a random process differs from all preceding ones.

We consider estimating distributions and their functions when the alphabet size is large compared to the amount of data observed. We establish consistency results and rates of convergence for estimators based on the data's profile, the number of symbols appearing any given number of times, and compare them with those based on empirical-frequency

We obtain bounds on the probability that the n'th variable in a stationary random process differs from all previous ones, and use it to show that the pattern entropy rate of any finite-entropy stationary process equals the process entropy rate. In the particular case of i.i.d. processes we also bound the speed at which the per-symbol pattern entropy converges to the sequence entropy

We consider the problem of modeling a distribution whose alphabet size is large relative to the amount of observed data. It is well known that conventional maximum-likelihood estimates do not perform well in that regime. Instead, we find the distribution maximizing the probability of the data's pattern. We derive an efficient algorithm for approximating this distribution. Simulations show that the computed distribution models the data well and yields general estimators that evaluate various data attributes as well as specific estimators designed especially for these tasks

Standard redundancy measures the excess number of bits needed to compress sequences of a given length. Instead, we consider relative redundancy that measures the excess number of bits for sequences of a given minimum description length. Low relative redundancy implies that number of bits needed to compress any sequence is essentially the lowest possible. We show that low relative redundancy implies low standard redundancy, that while block relative redundancy resembles block standard redundancy, sequential relative redundancy is twice its counterpart, and that common algorithms achieving standard redundancy have unbounded relative redundancy.

We determine the entropy rate of patterns of i.i.d. strings and show that they satisfy an asymptotic equipartition property. We prove that for discrete distributions the entropy rate of patterns equals that of the distribution, and that for distributions with continuous probability q, the entropy rate of patterns equals that of a modified distribution where the continuous probability is assigned to a new discrete element. One implication of these results is that for discrete distributions the conditional entropy rate of the sequence when its pattern is known is zero. We address only distributions with finite entropy.

We study the redundancy of three approaches to compression of independent and identically distributed (i.i.d.) strings over large, possibly infinite, alphabets: standard compression of the string itself and compression of the string's shape and pattern, which describe its symbols' relative magnitude and precedence, respectively. We determine the rate at which per-symbol standard redundancy increases to infinity as the alphabet size increases, show that the maximum per-symbol shape redundancy is between 0.027 and 1, and compare these to results showing that per-symbol pattern redundancy diminishes to zero for all alphabet sizes. We relate these concepts to ordered and unordered partitions of integers and sets, and use this framework to explore relations between several combinatorial quantities, including the Bell, Fubini, and second-type Stirling numbers.

It has long been known that the compression redundancy of independent and identically distributed (i.i.d.) strings increases to infinity as the alphabet size grows. It is also apparent that any string can be described by separately conveying its symbols, and its pattern-the order in which the symbols appear. Concentrating on the latter, we show that the patterns of i.i.d. strings over all, including infinite and even unknown, alphabets, can be compressed with diminishing redundancy, both in block and sequentially, and that the compression can be performed in linear time. To establish these results, we show that the number of patterns is the Bell number, that the number of patterns with a given number of symbols is the Stirling number of the second kind, and that the redundancy of patterns can be bounded using results of Hardy and Ramanujan on the number of integer partitions. The results also imply an asymptotically optimal solution for the Good-Turing probability-estimation problem.

It was known that universal compression of strings generated by independent and identically distributed sources over infinite alphabets entails infinite per-symbol redundancy. Alternative compression schemes, which decompose the description of such strings into a description of the symbols appearing in the string, and a description of the arrangement of the symbols form were presented. Two descriptions of the symbol arrangement were considered: shapes and patterns. Roughly speaking, shapes describe the relative magnitude of the symbols while patterns describe only the order in which they appear. The per-symbol worst-case redundancy of compressing shapes is a positive constant less than one, and the per-symbol redundancy of compressing patterns diminishes to zero as the block-length increases were proven. Some results on sequential pattern compression were also mentioned.

While deciphering the German Enigma code during World War II, I.J. Good and A.M. Turing considered the problem of estimating a probability distribution from a sample of data. They derived a surprising and unintuitive formula that has since been used in a variety of applications and studied by a number of researchers. Borrowing an information-theoretic and machine-learning framework, we define the attenuation of a probability estimator as the largest possible ratio between the per-symbol probability assigned to an arbitrarily-long sequence by any distribution, and the corresponding probability assigned by the estimator. We show that some common estimators have infinite attenuation and that the attenuation of the Good-Turing estimator is low, yet larger than one. We then derive an estimator whose attenuation is one, namely, as the length of any sequence increases, the per-symbol probability assigned by the estimator is at least the highest possible. Interestingly, some of the proofs use celebrated results by Hardy and Ramanujan on the number of partitions of an integer. To better understand the behavior of the estimator, we study the probability it assigns to several simple sequences. We show that some sequences this probability agrees with our intuition, while for others it is rather unexpected.