Universal learning is considered from an information theoretic point of view following the universal prediction approach pursued in the 90's by F&Merhav. Interestingly, the extension to learning is not straight-forward. In previous works we considered on-line learning and supervised learning in a stochastic setting. Yet, the most challenging case is batch learning where prediction is done on a test sample once the entire training data is observed, in the individual setting where the features and labels, both training and test, are specific individual quantities. This work provides schemes that for any individual data compete with a "genie" (or reference) that knows the true test label. It suggests design criteria and derive the corresponding universal learning schemes. The main proposed scheme is termed Predictive Normalized Maximum Likelihood (pNML). As demonstrated, pNML learning and its variations provide robust, "stable" learning solutions that outperforms the current leading approach based on Empirical Risk Minimization (ERM). Furthermore, the pNMLconstruction provides a pointwise indication for the learnability that measures the uncertainty in learning the specific test challenge with the given training examples - thus the learner knows when it does not know. The improved performance of the pNML, the induced learnability measure and its utilization are demonstrated in several learning problems including deep neural networks models.
Joint work with Yaniv Fogel and Koby Bibas
Professor Meir Feder received the Sc.D. degree from the Massachusetts Institute of Technology (MIT) and Woods Hole Oceanographic Institution (WHOI) in 1987. He is now a Chaired Professor and Head of the School of Electrical Engineering, Tel-Aviv University. He was a visiting Professor at MIT and had visiting appointments at Bell laboratories and Scripps Institute of Oceanography. While serving in the Israeli defense Forces, he was awarded the 1978 "creative mind" award of the chief Intelligence officer. He received the 1993 best paper award of the Information Theory Society. He was the recipient of the 1994 prize of Tel-Aviv University for excellent young scientists, the 1994 award of the Electronic Industry in Israel (awarded by the president of Israel), and the 1995 research prize in applied electronics awarded by Ben-Gurion University. He is a Fellow of the IEEE for his contribution to universal data prediction and universal compression.
In parallel to his academic career he was closely involved in the high-tech industry with numerous companies. In the early 90's he worked with Intel on the MMX architecture and designed efficient multimedia algorithms for it. In 1998 he co-founded Peach Networks, a provider of server-based interactive TV system via the cable network, which was acquired in 2000 by Microsoft. He then co-founded Bandwiz, to provide massive content delivery systems via "rateless codes". He is currently the Chief Scientist of Amimon, a company he co-founded in 2004. Amimon's "video-modem" technology is the basis of the WHDI (Wireless Home Digital Interface) standard, initiated by the leading Consumer Electronics companies, for wireless high-definition A/V connectivity at the home.