Deb Aronson

Like Magic: 1997 Beckman Institute Fellow Brendan Frey

First appeared in Beckman Institute Annual Newsletter in January 2001 under Profiles

In some ways, Brendan Frey, 1997 Beckman Fellow, became interested in machine learning because it appealed to his sense of magic.

“To know the secrets of how something that is beautiful and magical works is, to me, like being a magician,” says Frey, who even as a child was interested in machines that behave intelligently.

“I was always trying to be a magician, to duplicate nature,” says Frey, who now researches machine learning using graphical models, otherwise known as Bayesian Networks.

Although Frey is not pulling anything out of a hat these days, he has been as productive as a rabbit in the first year of his fellowship. In the year since he’s been at the Beckman Institute, he has published one book with MIT Press, three journal papers and 11 conference papers. The book, Graphical Models for Machine Learning and Digital Communication, received numerous glowing reviews from some very well-respected researchers in the field.

“The scope of this book is immense,” says David J.C. MacKay, professor of physics at University of Cambridge. “Brendan presents with great clarity the cutting edge of research on the learning of graphical models, the compression of data using latent variable models, and channel coding. It will be appreciated by everyone from computer scientists and psychologists to statisticians, engineers and information theorists.”

“Anyone doing research in these areas should read this book,” added G. David Forney, Jr. vice president of Motorola.

Frey also gave an invited talk at the Isaac Newton Institute for Mathematical Sciences based in Cambridge, England. He participated in the program on Neural Networks and Machine Learning. The Newton Institute conducts programs along mathematical themes that are at the forefront of current research. Fermat’s Theorem, for example, was proved at the Newton Institute. Having just received his Ph.D. last year from the University of Toronto in Electrical and Computer Engineering, Frey was quite young to be invited to the Newton Institute.

In addition to this hectic professional life, Frey and his wife, Utpala, have a busy home life raising their two young sons, four-year-old Shardul and one-year-old Sarth.

Graphical Models

Graphical models, the foundation of Frey’s research, are a way to describe complex interconnected networks (see illustration?). In graphical models, each node can only communicate with nodes directly connected to it. Frey then develops algorithms, which is the mathematical way to process information as described in a specific graphical model.

Graphical models have numerous applications. They are particularly useful in complex problems with numerous variables and some level of uncertainty. Frey is particularly interested in applications related to machine learning and digital communication. Machine learning refers to ways to teach computers in the way humans learn. In other words, he is interested in creating algorithms that would allow the computer to learn the structure from the data without anyone telling the computer beforehand what the structure is.

For example, by giving a computer thousands of samples of, say, a certain type of x-ray, there is a way to teach the computer (using algorithms and neural networks) to recognize a specific pattern within the x-ray. In the end, the complexity is inside the computer, much like the human brain. This is also known as unsupervised learning.

As a graduate student, Frey was the first to get a new unsupervised learning algorithm to work that mirrors the human brain’s wake/sleep cycle. So in the “wake” mode, the computer observes and in the “sleep” mode it ponders what it has observed. This work, done in collaboration with Geoffrey Hinton (Frey’s thesis advisor) Peter Dayan and Radford Neal, was published in the journal Science.

Shannon’s Law and Turbo Decoding

Frey also has been involved in pioneering a new perspective on digital communication. With the rapid development of mobile telecommunications systems and the recognition that fiber to the home would be very expensive, there has been a new growth of interest in pushing wireless and twisted-pair communication to their limits.

Exactly 50 years ago (Brendan could you give us Shannon’s first name?) Shannon established the field of digital communication limits by showing that for a given channel of communication, you could communicate only a certain amount of information per second (in bits). If any more bits than that were transmitted, the information would be lost. This is called Shannon’s limit. It’s a limit like the speed of light: it can’t be changed. But until now no one could send the information at that limit.

Shannon originally proposed a mathematical solution of how to get to that limit, but for every second of information transmitted, it would take 100 years to decode and translate it, an obviously impractical and unworkable solution. One key to getting close to Shannon’s Limit is to create an outstanding error-correcting algorithm.

A few years ago a team of French researchers figured a solution — using an algorithm — that takes only one second to decode every second of information. This solution came to be known as “turbo-decoding.” The problem isn’t solved perfectly, in the sense that they are not actually at Shannon’s limit, but very close to it.

Frey was the first to recognize that the turbo-decoding algorithm is essentially a Bayesian Network algorithm and that this algorithm was very similar to the ones used in machine learning. Using this similarity, Frey has been able to make lots of connections between artificial intelligence and turbo-decoding. Just last summer MacKay and Frey improved a bit on the turbo-decoding, giving them the “world record,” so to speak, of being the closest to Shannon’s Limit.

Telecommunications applications include sending data files over the Internet, as well as deep-space communication. The next space probe will use turbo-decoding to improve its communication abilities.

Interdisciplinary Projects

Because these algorithms can help solve complex problems, they are useful in a wide range of disciplines. Frey, for example, is in the process of applying graphical models to numerous projects, including indexing and annotation of digital video and automated web-based electron microscopy.

Imagine, for example, that you remember seeing an action movie years ago where the hero skydived into the ocean only to be attacked by sharks. Suppose you could go to your local video store, input that information and a computer could search all the videos for this combination of elements in a matter of seconds.

Frey and his colleagues are developing low-level multijects (multimedia objects) that can summarize snippets of video, audio and closed-captioning in order to figure out what is going on. A multiject would include the video, audio and closed-captioning of, for example, a family quarrel. That multiject could be linked in a graphical model that represents higher-order relationships to other multijects, such as a shark and someone skydiving. The retrieval system will be used to filter videos by answering queries like the one described above. Frey, who is a co-principal investigator (PI) on this project, is collaborating with Beckman Institute’s Thomas Huang (of AI), S.-F. Chang of Columbia University, and C.-H. Lee of Bell Labs.

Frey also is collaborating with Huang, Geoffrey Hinton and Zoubin Ghahroamani of the Gatsby Computational Neuroscience Unit in London, England, on a face modeling project. That project involves creating face-recognition algorithms that would be used in video conferencing and face and gesture recognition for human-machine interactions.

Electron Microscopy

Many researchers use transmission electron microscopes to study and understand protein structures, but collecting this information is a time-consuming and painstaking process. Highly trained microscopists look at low-magnification specimens, find areas that look potentially interesting, zoom in on the area to determine whether it’s worth further study, take a picture and go on to the next area. Only after spending months taking thousands of high-quality, high-magnification pictures, can microscopists gather enough information to study the protein. If a computer could learn to recognize structures that are worthwhile, much of the work could be automated. Frey is part of a team working on this project. Team members of the Imaging Technology Group and members of Klara Nahrstedt’s group also are working on the project. The project has been funded in part by the National Science Foundation and IBM.

“Brendan has been enormously helpful in providing us access to a field of knowledge we knew nothing about,” says Bridget Carragher, what title should I use? “It was a very happy coming together of fields and a fun, exciting project to work on together.”

Frey also enjoys these kinds of interdisciplinary projects.

“I’ve been lucky to find so many interdisciplinary projects to work on, because in general I think fruitful connections are usually few and far between,” says Frey. “You can’t force them.”

To learn more about Frey’s work, visit his Web site at www.cs.utoronto.ca/~frey.