EDBT 2026 Demo / reviewers in the wild / expert
Junan Zhang
dblp:83/5847
· DBLP profile ↗
19ranked-venue papers
2as first author
7since 2021 · last 2026
—ORCID · conflict
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 6Artificial intelligence and machine learning · 5 · 1 first-author · 4 since 2021Applied, interdisciplinary, general and emerging computing · 5Graphics, computer vision, multimedia, augmented reality and games · 3 · 1 first-author · 3 since 2021Software engineering, systems software and programming languages · 1 · 1 first-author · 1 since 2021
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Artificial intelligence
5 papers |
Speech recognition and synthesis · 48% Generative modeling · 18% Language models and text generation · 13% | |
| Network and information security
1 paper |
Malware analysis · 100% | |
| Software engineering, system software, and programming languages
1 paper |
Software maintenance and evolution · 100% | |
| Theoretical computer science
4 papers |
Coding theory · 58% Information theory · 27% Combinatorics and discrete mathematics · 8% |
Topics — the 26 heaviest of 27, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Natural language and speech › Language models and text generation › alignment
preference alignment |
1.0 | 1 | 2026 | Multi-Metric Preference Alignment for Generative Speech Restoration · AAAI 2026 |
Machine learning › Generative modeling
masked generative modeling |
0.9 | 1 | 2025 | Metis: A Foundation Speech Generation Model with Masked Generative Pre-training · NeurIPS 2025 |
Computer vision › Vision and language › vision-language model › multimodal large language model
multimodal large language model evaluation |
0.9 | 1 | 2025 | LOKI: A Comprehensive Synthetic Data Detection Benchmark using Large Multimodal Models · ICLR 2025 |
Natural language and speech › Speech recognition and synthesis
speech synthesis |
0.9 | 1 | 2025 | Metis: A Foundation Speech Generation Model with Masked Generative Pre-training · NeurIPS 2025 |
Natural language and speech › Speech recognition and synthesis › speech representation learning
speech tokenization |
0.9 | 1 | 2025 | TaDiCodec: Text-aware Diffusion Speech Tokenizer for Speech Language Modeling · NeurIPS 2025 |
Machine learning › Trustworthy machine learning
synthetic data detection |
0.9 | 1 | 2025 | LOKI: A Comprehensive Synthetic Data Detection Benchmark using Large Multimodal Models · ICLR 2025 |
Natural language and speech › Speech recognition and synthesis › speech synthesis
text-to-speech |
0.9 | 1 | 2025 | TaDiCodec: Text-aware Diffusion Speech Tokenizer for Speech Language Modeling · NeurIPS 2025 |
Natural language and speech › Speech recognition and synthesis › text-to-speech synthesis
zero-shot text-to-speech |
0.9 | 1 | 2025 | TaDiCodec: Text-aware Diffusion Speech Tokenizer for Speech Language Modeling · NeurIPS 2025 |
Malware analysis › malware detection
malicious package detection |
0.9 | 1 | 2025 | Killing Two Birds with One Stone: Malicious Package Detection in NPM and PyPI using a Single Model of Malicious Behavior Sequence · ACM Trans. Softw. Eng. Methodol. 2025 |
Software maintenance and evolution › software supply chain
software supply chain security |
0.9 | 1 | 2025 | Killing Two Birds with One Stone: Malicious Package Detection in NPM and PyPI using a Single Model of Malicious Behavior Sequence · ACM Trans. Softw. Eng. Methodol. 2025 |
Machine learning › Generative modeling
diffusion model |
0.6 | 2 | 2026 | Multi-Metric Preference Alignment for Generative Speech Restoration · AAAI 2026 TaDiCodec: Text-aware Diffusion Speech Tokenizer for Speech Language Modeling · NeurIPS 2025 |
Machine learning › Trustworthy machine learning
AI-generated content detection |
0.3 | 1 | 2025 | LOKI: A Comprehensive Synthetic Data Detection Benchmark using Large Multimodal Models · ICLR 2025 |
Machine learning › Generative modeling › diffusion model › diffusion-based representation learning
diffusion autoencoder |
0.3 | 1 | 2025 | TaDiCodec: Text-aware Diffusion Speech Tokenizer for Speech Language Modeling · NeurIPS 2025 |
Natural language and speech › Language models and text generation
pre-trained language model |
0.3 | 1 | 2025 | Killing Two Birds with One Stone: Malicious Package Detection in NPM and PyPI using a Single Model of Malicious Behavior Sequence · ACM Trans. Softw. Eng. Methodol. 2025 |
Information theory › information measures › entropy
asymptotic equipartition property |
0.1 | 1 | 2006 | Limit Results on Pattern Entropy · IEEE Trans. Inf. Theory 2006 |
Information theory › information measures › entropy
entropy rate |
0.1 | 1 | 2006 | Limit Results on Pattern Entropy · IEEE Trans. Inf. Theory 2006 |
Coding theory
error-correcting codes |
0.1 | 1 | 2005 | Stopping set distribution of LDPC code ensembles · IEEE Trans. Inf. Theory 2005 |
Coding theory › error-correcting codes › decoding
iterative decoding |
0.1 | 1 | 2005 | Stopping set distribution of LDPC code ensembles · IEEE Trans. Inf. Theory 2005 |
Coding theory › error-correcting codes
LDPC codes |
0.1 | 1 | 2005 | Stopping set distribution of LDPC code ensembles · IEEE Trans. Inf. Theory 2005 |
Coding theory › error-correcting codes › decoding › iterative decoding
stopping sets |
0.1 | 1 | 2005 | Stopping set distribution of LDPC code ensembles · IEEE Trans. Inf. Theory 2005 |
Combinatorics and discrete mathematics
enumeration |
0.0 | 1 | 2004 | Universal compression of memoryless sources over unknown alphabets · IEEE Trans. Inf. Theory 2004 |
Coding theory › source coding › lossless compression
pattern compression |
0.0 | 1 | 2004 | Universal compression of memoryless sources over unknown alphabets · IEEE Trans. Inf. Theory 2004 |
Coding theory
source coding |
0.0 | 1 | 2004 | Universal compression of memoryless sources over unknown alphabets · IEEE Trans. Inf. Theory 2004 |
Coding theory › source coding
universal coding |
0.0 | 1 | 2004 | Universal compression of memoryless sources over unknown alphabets · IEEE Trans. Inf. Theory 2004 |
Information theory › estimation theory › entropy estimation
good-turing estimator |
0.0 | 1 | 2003 | Always Good Turing: Asymptotically Optimal Probability Estimation · FOCS 2003 |
Mathematical optimization › statistical estimation
probability estimation |
0.0 | 1 | 2003 | Always Good Turing: Asymptotically Optimal Probability Estimation · FOCS 2003 |
Methods — techniques the papers use, named apart from their topics
pre-trained language model · 1.7fine-tuning · 1.7behavior sequence modeling · 1.7flow matching · 1.0direct preference optimization · 1.0autoregressive model · 1.0vector quantization · 0.9masked generative pretraining · 0.9masked generative modeling · 0.9large multimodal model · 0.9discrete speech representation · 0.9diffusion transformer · 0.9autoregressive modeling · 0.9partition theory · 0.0information-theoretic framework · 0.0
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | Multi-Metric Preference Alignment for Generative Speech RestorationabstractRecent generative models have significantly advanced speech restoration tasks, yet their training objectives often misalign with human perceptual preferences, resulting in suboptimal quality. While post-training alignment has proven effective in other generative domains like text and image generation, its application to generative speech restoration remains largely under-explored. This work investigates the challenges of applying preference-based post-training to this task, focusing on how to define a robust preference signal and curate high-quality data to avoid reward hacking. To address these challenges, we propose a multi-metric preference alignment strategy. We construct a new dataset, GenSR-Pref, comprising 80K preference pairs, where each chosen sample is unanimously favored by a complementary suite of metrics covering perceptual quality, signal fidelity, content consistency, and timbre preservation. This principled approach ensures a holistic preference signal. Applying Direct Preference Optimization (DPO) with our dataset, we observe consistent and significant performance gains across three diverse generative paradigms: autoregressive models (AR), masked generative models (MGM), and flow-matching models (FM) on various restoration benchmarks, in both objective and subjective evaluations. Ablation studies confirm the superiority of our multi-metric strategy over single-metric approaches in mitigating reward hacking. Furthermore, we demonstrate that our aligned models can serve as powerful ''data annotators'', generating high-quality pseudo-labels to serve as a supervision signal for traditional discriminative models in data-scarce scenarios like singing voice restoration. Junan Zhang, Xueyao Zhang, Yuancheng Wang, Zhizheng Wu 0001 |
AAAI | 1 |
| 2025 | LOKI: A Comprehensive Synthetic Data Detection Benchmark using Large Multimodal ModelsabstractWith the rapid development of AI-generated content, the future internet may be inundated with synthetic data, making the discrimination of authentic and credible multimodal data increasingly challenging. Synthetic data detection has thus garnered widespread attention, and the performance of large multimodal models (LMMs) in this task has attracted significant interest. LMMs can provide natural language explanations for their authenticity judgments, enhancing the explainability of synthetic content detection. Simultaneously, the task of distinguishing between real and synthetic data effectively tests the perception, knowledge, and reasoning capabilities of LMMs. In response, we introduce LOKI, a novel benchmark designed to evaluate the ability of LMMs to detect synthetic data across multiple modalities. LOKI encompasses video, image, 3D, text, and audio modalities, comprising 18K carefully curated questions across 26 subcategories with clear difficulty levels. The benchmark includes coarse-grained judgment and multiple-choice questions, as well as fine-grained anomaly selection and explanation tasks, allowing for a comprehensive analysis of LMMs. We evaluated 22 open-source LMMs and 6 closed-source models on LOKI, highlighting their potential as synthetic data detectors and also revealing some limitations in the development of LMM capabilities. More information about LOKI can be found at https://opendatalab.github.io/LOKI/. Junyan Ye, Baichuan Zhou, Junan Zhang, Tianyi Bai, Hengrui Kang, Honglin Lin, Zhizheng Wu 0001, Dahua Lin, Conghui He |
ICLR | 4 |
| 2025 | TaDiCodec: Text-aware Diffusion Speech Tokenizer for Speech Language ModelingabstractSpeech tokenizers serve as foundational components for speech language models, yet current designs exhibit several limitations, including:
(1) dependence on multi-layer residual vector quantization structures or high frame rates,
(2) reliance on auxiliary pre-trained models for semantic distillation, and
(3) requirements for complex two-stage training processes.
In this work, we introduce the **T**ext-**a**ware **Di**ffusion Transformer Speech **Codec** (***TaDiCodec***), a novel approach designed to overcome these challenges.
TaDiCodec employs end-to-end optimization for quantization and reconstruction through a diffusion autoencoder, while integrating text guidance into the diffusion decoder to enhance reconstruction quality and achieve optimal compression.
TaDiCodec achieves an extremely low frame rate of **6.25 Hz** and a corresponding bitrate of **0.0875 kbps** with a **single-layer codebook** for 24 kHz speech,
while maintaining superior performance on critical speech generation evaluation metrics such as Word Error Rate (WER), speaker similarity (SIM), and speech quality (UTMOS),
Notably, TaDiCodec employs a single-stage, end-to-end training paradigm, and obviating the need for auxiliary pre-trained models.
We also validate the compatibility of TaDiCodec in language model based zero-shot text-to-speech with both autoregressive modeling and masked generative modeling, demonstrating its effectiveness and efficiency for speech language modeling, as well as a significantly small *reconstruction-generation gap*.
To facilitate reproducibility and further research, we will make our source code and pre-trained checkpoints publicly available.
Audio samples are are available at https://tadicodec.github.io/. We release code and model checkpoints at https://github.com/AmphionTeam/TaDiCodec. Yuancheng Wang, Dekun Chen, Xueyao Zhang, Junan Zhang, Jiaqi Li 0030, Zhizheng Wu 0001 |
NeurIPS | 4 |
| 2025 | Metis: A Foundation Speech Generation Model with Masked Generative Pre-trainingabstractWe introduce ***Metis***, a foundation model for unified speech generation.
Unlike previous task-specific or multi-task models, Metis follows a pre-training and fine-tuning paradigm. It is pre-trained on large-scale unlabeled speech data using masked generative modeling and then fine-tuned to adapt to diverse speech generation tasks.
Specifically,
(1) Metis utilizes two discrete speech representations: SSL tokens derived from speech self-supervised learning (SSL) features, and acoustic tokens directly quantized from waveforms.
(2) Metis performs masked generative pre-training on SSL tokens, utilizing 300K hours of diverse speech data, without any additional condition.
(3) Through fine-tuning with task-specific conditions, Metis achieves efficient adaptation to various speech generation tasks while supporting multimodal input, even when using limited data and trainable parameters.
Experiments demonstrate that Metis can serve as a foundation model for unified speech generation: Metis outperforms state-of-the-art task-specific or multi-task systems across five speech generation tasks, including zero-shot text-to-speech, voice conversion, target speaker extraction, speech enhancement, and lip-to-speech, even with fewer than 20M trainable parameters or 300 times less training data. Audio samples are are available at https://metis-demo.github.io/. We release the code and model checkpoints at https://github.com/open-mmlab/Amphion. Yuancheng Wang, Jiachen Zheng, Junan Zhang, Xueyao Zhang, Huan Liao, Zhizheng Wu 0001 |
NeurIPS | 3 |
| 2025 | Killing Two Birds with One Stone: Malicious Package Detection in NPM and PyPI using a Single Model of Malicious Behavior SequenceabstractOpen source software (OSS) supply chain enlarges the attack surface of a software system, which makes package registries attractive targets for attacks. Recently, multiple package registries have received intensified attacks with malicious packages. Of those package registries, NPM and PyPI are two of the most severe victims. Existing malicious package detectors are developed with features from a list of packages of the same ecosystem and deployed within the same ecosystem exclusively, which is infeasible to utilize the knowledge of a new malicious NPM package detected recently to detect the new malicious package in PyPI. Moreover, existing detectors lack support to model malicious behavior of OSS packages in a sequential way. To address the two limitations, we propose a single detection model using malicious behavior sequence, named Cerebro , to detect malicious packages in NPM and PyPI. We curate a feature set based on a high-level abstraction of malicious behavior to enable multi-lingual knowledge fusing. We organize extracted features into a behavior sequence to model sequential malicious behavior. We fine-tune the pre-trained language model to understand the semantics of malicious behavior. Extensive evaluation has demonstrated the effectiveness of Cerebro over the state-of-the-art as well as the practically acceptable efficiency. Cerebro has detected 683 and 799 new malicious packages in PyPI and NPM, and received 707 thank letters from the official PyPI and NPM teams. Junan Zhang, Kaifeng Huang 0001, Bihuan Chen 0001, Ruisi Wang, Chong Wang 0013, Xin Peng 0001 |
ACM Trans. Softw. Eng. Methodol. | 1 |
| 2024 | Leveraging Diverse Semantic-Based Audio Pretrained Models for Singing Voice ConversionabstractSinging Voice Conversion (SVC) is a technique that enables any singer to perform any song. To achieve this, it is essential to obtain speaker-agnostic representations from the source audio, which poses a significant challenge. A common solution involves utilizing a semantic-based audio pretrained model as a feature extractor However, the degree to which the extracted features can meet the SVC requirements remains an open question. This includes their capability to accurately model melody and lyrics, the speaker-independency of their underlying acoustic information, and their robustness for in-the-wild acoustic environments. In this study, we investigate the knowledge within classical semantic-based pretrained models in much detail. We discover that the knowledge of different models is diverse and can be complementary for SVC. Based on the above, we design a Singing Voice Conversion framework based on Diverse Semantic-based Feature Fusion (DSFF-SVC). Experimental results demonstrate that DSFF-SVC can be generalized and improve various existing SVC models, particularly in challenging real-world conversion tasks. Our demo website is available at https://diversesemanticsvc.github.io/. Xueyao Zhang, Zihao Fang, Yicheng Gu, Haopeng Chen, Lexiao Zou, Junan Zhang, Liumeng Xue, Zhizheng Wu 0001 |
SLT | 6 |
| 2024 | Amphion: an Open-Source Audio, Music, and Speech Generation ToolkitabstractAmphion is an open-source toolkit for Audio, Music, and Speech Generation, targeting to ease the way for junior researchers and engineers into these fields. It presents a unified framework that includes diverse generation tasks and models, with the added bonus of being easily extendable for new incorporation. The toolkit is designed with beginner-friendly workflows and pre-trained models, allowing both beginners and seasoned researchers to kick-start their projects with relative ease. The initial release of Amphion v0.1 supports a range of tasks including Text to Speech (TTS), Text to Audio (TTA), and Singing Voice Conversion (SVC), supplemented by essential components like data preprocessing, state-of-the-art vocoders, and evaluation metrics. This paper presents a high-level overview of Amphion. Amphion is open-sourced at https://github.com/open-mmlab/Amphion. Xueyao Zhang, Liumeng Xue, Yicheng Gu, Yuancheng Wang, Jiaqi Li 0030, Haorui He, Chaoren Wang, Songting Liu, Junan Zhang, Zihao Fang, Haopeng Chen, Tze Ying Tang, Lexiao Zou, Mingxuan Wang, Kai Chen 0026, Haizhou Li 0001, Zhizheng Wu 0001 |
SLT | 10 |
| 2008 | Further results on relative redundancyabstractStandard 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. Hirakendu Das, Alon Orlitsky, Narayana P. Santhanam, Junan Zhang |
ISIT | 4 |
| 2006 | Relative redundancy for large alphabetsabstractStandard 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 Alon Orlitsky, Narayana P. Santhanam, Junan Zhang |
ISIT | 3 |
| 2006 | Theoretical and Experimental Results on Modeling Low ProbabilitiesabstractBuilding 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. Alon Orlitsky, Narayana P. Santhanam, Krishnamurthy Viswanathan, Junan Zhang |
ITW | 4 |
| 2006 | Limit Results on Pattern EntropyabstractWe 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. Alon Orlitsky, Narayana P. Santhanam, Krishnamurthy Viswanathan, Junan Zhang |
IEEE Trans. Inf. Theory | 4 |
| 2005 | Convergence of profile based estimatorsabstractWe 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 Alon Orlitsky, Narayana P. Santhanam, K. Viswanathan, Junan Zhang |
ISIT | 4 |
| 2005 | Stopping set distribution of LDPC code ensemblesabstractStopping sets determine the performance of low-density parity-check (LDPC) codes under iterative decoding over erasure channels. We derive several results on the asymptotic behavior of stopping sets in Tanner-graph ensembles, including the following. An expression for the normalized average stopping set distribution, yielding, in particular, a critical fraction of the block length above which codes have exponentially many stopping sets of that size. A relation between the degree distribution and the likely size of the smallest nonempty stopping set, showing that for a /spl radic/1-/spl lambda/'(0)/spl rho/'(1) fraction of codes with /spl lambda/'(0)/spl rho/'(1)2, the smallest nonempty stopping set is linear in the block length. Bounds on the average block error probability as a function of the erasure probability /spl epsi/, showing in particular that for codes with lowest variable degree 2, if /spl epsi/ is below a certain threshold, the asymptotic average block error probability is 1-/spl radic/1-/spl lambda/'(0)/spl rho/'(1)/spl epsi/. Alon Orlitsky, Krishnamurthy Viswanathan, Junan Zhang |
IEEE Trans. Inf. Theory | 3 |
| 2004 | Algorithms for modeling distributions over large alphabetsabstractWe 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 Alon Orlitsky, Sajama, Narayana P. Santhanam, Krishnamurthy Viswanathan, Junan Zhang |
ISIT | 5 |
| 2004 | Relative redundancy: a more stringent performance guarantee for universal compressionabstractStandard 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. Alon Orlitsky, Narayana P. Santhanam, Junan Zhang |
ISIT | 3 |
| 2004 | Limit results on pattern entropyabstractWe 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. Alon Orlitsky, Narayana P. Santhanam, Krishnamurthy Viswanathan, Junan Zhang |
ITW | 4 |
| 2004 | On Modeling Profiles Instead of Values
Alon Orlitsky, Narayana P. Santhanam, Krishnamurthy Viswanathan, Junan Zhang |
UAI | 4 |
| 2004 | Universal compression of memoryless sources over unknown alphabetsabstractIt 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. Alon Orlitsky, Narayana P. Santhanam, Junan Zhang |
IEEE Trans. Inf. Theory | 3 |
| 2003 | Always Good Turing: Asymptotically Optimal Probability EstimationabstractWhile 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. Alon Orlitsky, Narayana P. Santhanam, Junan Zhang |
FOCS | 3 |