Forum for Science, Industry and Business

Sponsored by:     3M 
Search our Site:

 

UCSD scientists explain and improve upon ’enigmatic’ probability formula

17.10.2003


Findings could have implications for speech recognition, machine learning, information retrieval



Scientists at the University of California, San Diego (UCSD) have developed new insight into a formula that helped British cryptanalysts crack the German Enigma code in World War II. Writing in the Oct. 17 edition of the journal Science, UCSD Jacobs School of Engineering professor Alon Orlitsky and graduate students Narayana P. Santhanam and Junan Zhang shed light on a lingering mathematical mystery and propose a new solution that could help improve automatic speech recognition, natural language processing, and other machine learning software.

In the article, Orlitsky and his colleagues unlock some of the secrets of the "Good-Turing estimator," a formula for estimating the probability of elements based on observed data. The formula is named after famed mathematicians I.J. Good and Alan Turing who, during WWII, were among a group of cryptanalysts charged with breaking the Enigma cipher -- the code used to encrypt German military communications. Working at Bletchley Park outside of London, their work has been credited by some with shortening the war by several years. (It also led to the development of the first modern computer, and was documented in a number of books and movies.)


The cryptanalysts were greatly aided by their possession of the Kengruppenbuch, the German cipher book that contained all possible secret keys to Enigma, and had been previously captured by British Intelligence. They documented the keys used by various U-boat commanders in previously decrypted messages and used this information to estimate the distributions of pages from which commanders picked their secret keys.

The prevailing technique at the time estimated the likelihood of each page by simply using its empirical frequency, the fraction of the time it had been picked in the past. But Good and Turing developed an unintuitive formula that bore little resemblance to conventional estimators. Surprisingly, this Good-Turing estimator outperformed the more intuitive approaches. Following the war, Good published the formula, mentioning that Turing had an "intuitive demonstration" for its power, but not describing what that demonstration entailed.

Since then, Good-Turing has been incorporated into a variety of applications such as information retrieval, spell-checking, and speech recognition software, where it is used to learn automatically the underlying structure of the language. But despite its usefulness, "its performance has remained something of an enigma itself," said Orlitsky, a professor in the Electrical and Computer Engineering department. While some partial explanations were given as to why Good-Turing may work well, no objective evaluation or results have been established for its optimality. Additionally, scientists observed that while it worked well under many circumstances, at times, its performance was lacking.

Now, Orlitsky, Santhanam, and Zhang believe they have unraveled some of the mystery surrounding Good-Turing, and constructed a new estimator that, unlike the historic formula, is reliable under all conditions. Motivated by information-theoretic and machine-learning considerations, they propose a natural measure for the performance of an estimator. Called attenuation, it evaluates the highest possible ratio between the probability assigned to each symbol in a sequence by any distribution, and the corresponding probability assigned by the estimator.

The UCSD researchers show that intuitive estimators, such as empirical frequency, can attenuate the probability of a symbol by an arbitrary amount. They also prove that Good-Turing performs well in general. While it can attenuate the probability of symbols by a factor of 1.39, it never attenuates by a factor of more than 2. Motivated by these observations, they derived an estimator whose attenuation is 1. This means that as the length of any sequence increases, the probability assigned to each symbol by the new estimator is as high as that assigned to it by any distribution.

"While there is a considerable amount of work to be done in simplifying and further improving the new estimator," concluded Orlitsky, "we hope that this new framework will eventually improve language modeling and hence lead to better speech recognition and data mining software."


* "Always Good-Turing: Asymptotically Optimal Probability Estimation," Science Magazine. http://www.sciencemag.org/

Media Contact: Doug Ramsey 858-822-5825 dramsey@ucsd.edu

Doug Ramsey | EurekAlert!
Further information:
http://www.ucsd.edu/

More articles from Information Technology:

nachricht UT professor develops algorithm to improve online mapping of disaster areas
29.11.2016 | University of Tennessee at Knoxville

nachricht New standard helps optical trackers follow moving objects precisely
23.11.2016 | National Institute of Standards and Technology (NIST)

All articles from Information Technology >>>

The most recent press releases about innovation >>>

Die letzten 5 Focus-News des innovations-reports im Überblick:

Im Focus: Novel silicon etching technique crafts 3-D gradient refractive index micro-optics

A multi-institutional research collaboration has created a novel approach for fabricating three-dimensional micro-optics through the shape-defined formation of porous silicon (PSi), with broad impacts in integrated optoelectronics, imaging, and photovoltaics.

Working with colleagues at Stanford and The Dow Chemical Company, researchers at the University of Illinois at Urbana-Champaign fabricated 3-D birefringent...

Im Focus: Quantum Particles Form Droplets

In experiments with magnetic atoms conducted at extremely low temperatures, scientists have demonstrated a unique phase of matter: The atoms form a new type of quantum liquid or quantum droplet state. These so called quantum droplets may preserve their form in absence of external confinement because of quantum effects. The joint team of experimental physicists from Innsbruck and theoretical physicists from Hannover report on their findings in the journal Physical Review X.

“Our Quantum droplets are in the gas phase but they still drop like a rock,” explains experimental physicist Francesca Ferlaino when talking about the...

Im Focus: MADMAX: Max Planck Institute for Physics takes up axion research

The Max Planck Institute for Physics (MPP) is opening up a new research field. A workshop from November 21 - 22, 2016 will mark the start of activities for an innovative axion experiment. Axions are still only purely hypothetical particles. Their detection could solve two fundamental problems in particle physics: What dark matter consists of and why it has not yet been possible to directly observe a CP violation for the strong interaction.

The “MADMAX” project is the MPP’s commitment to axion research. Axions are so far only a theoretical prediction and are difficult to detect: on the one hand,...

Im Focus: Molecules change shape when wet

Broadband rotational spectroscopy unravels structural reshaping of isolated molecules in the gas phase to accommodate water

In two recent publications in the Journal of Chemical Physics and in the Journal of Physical Chemistry Letters, researchers around Melanie Schnell from the Max...

Im Focus: Fraunhofer ISE Develops Highly Compact, High Frequency DC/DC Converter for Aviation

The efficiency of power electronic systems is not solely dependent on electrical efficiency but also on weight, for example, in mobile systems. When the weight of relevant components and devices in airplanes, for instance, is reduced, fuel savings can be achieved and correspondingly greenhouse gas emissions decreased. New materials and components based on gallium nitride (GaN) can help to reduce weight and increase the efficiency. With these new materials, power electronic switches can be operated at higher switching frequency, resulting in higher power density and lower material costs.

Researchers at the Fraunhofer Institute for Solar Energy Systems ISE together with partners have investigated how these materials can be used to make power...

All Focus news of the innovation-report >>>

Anzeige

Anzeige

Event News

ICTM Conference 2017: Production technology for turbomachine manufacturing of the future

16.11.2016 | Event News

Innovation Day Laser Technology – Laser Additive Manufacturing

01.11.2016 | Event News

#IC2S2: When Social Science meets Computer Science - GESIS will host the IC2S2 conference 2017

14.10.2016 | Event News

 
Latest News

UTSA study describes new minimally invasive device to treat cancer and other illnesses

02.12.2016 | Medical Engineering

Plasma-zapping process could yield trans fat-free soybean oil product

02.12.2016 | Agricultural and Forestry Science

What do Netflix, Google and planetary systems have in common?

02.12.2016 | Physics and Astronomy

VideoLinks
B2B-VideoLinks
More VideoLinks >>>