KAIST Information Theory and

Machine Learning Workshop

□ Date and Time : Dec. 20 (Tue) 2016, 09:00~21:00

□ Venue : #201, N1 (IT Convergence Building)

□ Program :

Time	Speaker
09:00~10:00	Dr. Kang Wook Lee (KAIST) “Speeding Up Distributed Computing Systems Using Codes”
10:00~11:00	Dr. Hyeji Kim (UIUC) “On the Optimality of Superposition Coding for the Broadcast Channel”
11:00~12:00	Dr. Jungwon Lee (Samsung USA) “Towards the Limit of Neural Network Quantization”
12:00~13:30	Lunch (Faculty Club)
13:30~14:30	Prof. Jinwoo Shin (KAIST) “Approximating Spectral Sums of Large-scale Matrices using Chebyshev Polynomials: Application to Determinant Point Process”
14:30~15:30	Prof. Young-Han Kim (UCSD) “How to Learn Probability without Learning”
15:30~16:00	Coffee Break
16:00~17:00	Prof. Daniel Lee (UPenn) “Machine Learning and Manifold Representations in Autonomous Systems”
17:00~18:00	Prof. Sae-Young Chung (KAIST) “Artificial Intelligence: Information Theory Perspective”
18:00~21:00	Dinner

“Speeding Up Distributed Computing Systems Using Codes”

Dr. Kang Wook Lee (이강욱 박사)

Korea Advanced Institue of Science and Technology

Abstract:

Modern data centers have been providing exponentially increasing computing and storage resources, which have been fueling core applications ranging from search engines in the early 2000’s to the real-time, large-scale data analysis of today. All these breakthroughs were made possible only due to the scalability in computing and storage resources offered by modern large-scale clusters, comprising individually small and unreliable low-end devices. Given the individually unpredictable nature of the underlying devices in these systems, we face the constant challenge of securing predictable and high-quality performance of such systems in the face of uncertainty.

In this talk, distributed computing systems are viewed through a coding-theoretic lens. The role of codes in providing resiliency against noise has been studied for decades in many other engineering contexts, especially in communication systems. Since the performance of distributed systems is significantly affected by anomalous system behavior and bottlenecks, there is an exciting opportunity for codes to endow distributed systems with robustness against such system noise. In this talk, I will show how computation layer and communication layer of distributed computing systems can be made robust with coding-theoretic tools. For the computation layer, I will inject computing redundancy into distributed algorithms so that they are robust to stragglers, i.e. nodes that are substantially slower than the other nodes; for the communication layer, I will propose a novel data caching and communication protocol, based on coding-theoretic principles that can significantly reduce the network overhead of the data shuffling operation, which can help achieve higher statistical efficiency when running parallel/distributed machine learning algorithms.

Bio:

Kangwook Lee is a postdoctoral scholar in the School of EE at KAIST, working with Prof. Changho Suh. He received his PhD degree in 2016 from the EECS department at UC Berkeley under the supervision of Prof. Kannan Ramchandran. He also obtained his MS degree in EECS from UC Berkeley in 2012, and BS degree in EE from KAIST in 2010.

“On the Optimality of Superposition Coding for the Broadcast Channel”

Dr. Hyeji Kim (김혜지 박사)

University of Illinois Urbana-Champaign

Abstract:

The broadcast channel, first studied by Tom Cover, is a model for one to many communications. The capacity region of the broadcast channel is unknown in general and is one of the most important open problems in network information theory. Superposition coding, also introduced in Cover’s seminal paper on broadcast channels, is the first non trivial and most widely used encoding technique in network information theory. In the work presented in this talk, I focus on the optimality of superposition coding for the broadcast channel.

I will first review the superposition coding scheme and describe the derivation of the optimal achievable rate region and then review known classes of broadcast channels for which superposition coding is optimal.

In the second part of the talk, I will describe our work on continuous time Poisson broadcast channels, where we show the surprising result that superposition coding is optimal for almost all channel parameter values. Interestingly, the channel in some subsets of these parameter values does not belong to any of the existing classes of broadcast channels for which superposition coding is known to be optimal (e.g., degraded, less noisy, more capable). For the rest of the channel parameter values, I will show that there is a gap between the best known inner bound and the best known outer bound – Marton’s inner bound and the Nair-El Gamal outer bound.

Last, I will describe our results on skewed binary broadcast channels, which show that although the channels do not belong to previously known classes of broadcast channels for which superposition coding has been shown to be optimal, superposition coding is optimal for a large set of parameters.

Bio:

Hyeji Kim is a postdoctoral research associate with the Coordinated Science Laboratory at University of Illinois at Urbana-Champaign. She received her B.S. degree with honors in Electrical Engineering from the Korea Advanced Institute of Science and Technology in 2011 and her M.S. and Ph.D. degrees in Electrical Engineering from Stanford University in 2013 and 2016, respectively. She is a recipient of the Stanford Graduate Fellowship. Her research interest include information theory and statistical learning.

“Towards the Limit of Neural Network Quantization”

Dr. Jungwon Lee (이정원 박사)

Samsung USA

Abstract:

Network quantization is one of network compression techniques employed to reduce the redundancy of deep neural networks. It shrinks the storage requirement for network parameters by curtailing the number of distinct parameter values. In this talk, we present network quantization schemes that minimize the network performance loss due to quantization given the compression ratio constraint. We analyze the quantitative relation of quantization errors to the neural network loss function and show that the network performance loss can be represented approximately by the Hessian-weighted distortion measure. Then we propose to use Hessian-weighted k-means clustering for network parameter quantization. When optimal variable-length binary codes, e.g., Huffman codes, are employed for quantized values, we derive that the network quantization problem can be related to the entropy-constrained scalar quantization (ECSQ) problem in information theory. We propose two solutions of ECSQ for network quantization, i.e., uniform quantization and an iterative algorithm similar to Lloyd's algorithm for k-means clustering. Our experimental results show that the compression ratios of 51.25, 22.17 and 40.65 are achievable for LeNet, ResNet and AlexNet, respectively.

Bio:

Jungwon Lee is a Senior Director at Samsung Modem R&D Lab in San Diego, CA. He received his PhD degree in Electrical Engineering from Stanford University in 2005. From 2003 to 2010, he was with Marvell Semiconductor Inc. as a Principal Engineer. Since 2010, he has been with Samsung USA leading the development of cellular modems and connectivity chips. His research interests lie in signal processing, communications, and machine learning for real-world applications. Dr. Lee has co-authored more than 90 papers and holds over 200 US patents.

“Approximating Spectral Sums of Large-scale Matrices using Chebyshev Polynomials: Application to Determinant Point Process”

Prof. Jinwoo Shin (신진우 교수)

Korea Advanced Institue of Science and Technology

Abstract:

Computation of the trace of a matrix function plays an important role in many scientific computing applications, including applications in machine learning, computational physics (e.g., lattice quantum chromodynamics), network analysis and computational biology (e.g., protein fold-ing), just to name a few application areas.  We propose a linear-time randomized algorithm for approximating the trace of matrix functions of large symmetric matrices. Our algorithm is based on coupling function approximation using Chebyshev interpolation with stochastic trace estimators (Hutchinson’s method), and as such requires only implicit access to the matrix, in the form of a function that maps a vector to the product of the matrix and the vector. We provide rigorous approximation error in terms of the extremal eigenvalue of the input matrix, and the Bernstein ellipse that corresponds to the function at hand. Based on our general scheme, we provide algorithms with provable guarantees for important matrix computations, including log-determinant, trace of matrix inverse, Estrada index, Schatten p-norm, and testing positive definiteness. Finally, as a concrete machine learning application, I will also explain how it can be used for large-scale optimization associated to determinant point processes.

“How to Learn Probability without Learning”

Prof. Young-Han Kim (김영한 교수)

University of California, San Diego

Abstract:

As Laplace famously asked “What is the probability that the sun will rise tomorrow?,” inferring the probability underlying a given data sample is at the core of statistics. In this talk, we discuss a general principle of assigning probabilities to sequential data based on a somewhat arcane theory of universal probability, which has been developed (sometimes in disguise) in ergodic theory, data compression, and sequential prediction.

We explore the main features and applications of universal probability assignment through a few examples ranging from causality inference on time series data to classification of nucleotide sequences. First, we demonstrate how universal probability can be used to estimate directed information between two time series, which in turn can reveal which time series leads the other. Second, building on earlier work by universal classification and data compression, we develop a two-stage algorithm for modeling and classification of DNA/RNA sequences that achieves a comparable accuracy of the standard-bearing BLAST algorithm with orders-of-magnitude speedup.

Bio:

Young-Han Kim received his B.S. degree in Electrical Engineering from Seoul National University in 1996 and his Ph.D. degree in Electrical Engineering (M.S. degrees in Statistics and in Electrical Engineering) from Stanford University in 2006. Since then he has been a faculty member in the Department of Electrical and Computer Engineering at the University of California, San Diego, where he is currently an Associate Professor.

Professor Kim is a recipient of the NSF CAREER Award (2008), the US-Israel BSF Bergmann Memorial Award (2009), the IEEE Information Theory Paper Award (2012), and the first IEEE James L. Massey Research and Teaching Award (2015). He is an IEEE Fellow. His research interests include information theory, communication engineering, and data science. He has coauthored the book Network Information Theory (Cambridge University Press, 2011), which has been used widely as a textbook on the topic.

“Machine Learning and Manifold Representations in Autonomous Systems”

Prof. Daniel Lee

University of Pennsylvania

Abstract:

Current AI systems for perception and action incorporate a number of

techniques: Bayesian state estimation, probabilistic mapping, trajectory planning, and feedback control. I will describe and demonstrate some of these methods on several autonomous systems including wheeled, legged, and flying robots. In order to model data variability due to pose, illumination, and background changes, low-dimensional manifold representations have long been used in machine learning. But how well can such manifolds be processed by neural networks? I will show how traditional notions of linear separability and VC dimension can be generalized from input points to manifolds. This analysis provides theoretical predictions for the capacity and generalization ability of invariant classifiers, and better understanding of the performance of deep neural networks.

Bio:

Daniel Lee is the UPS Foundation Chair Professor in the School of Engineering and Applied Science at the University of Pennsylvania. He received his B.A. summa cum laude from Harvard University and his Ph.D. in Condensed Matter Physics from the Massachusetts Institute of Technology. Before coming to Penn, he was a researcher at AT&T and Lucent Bell Laboratories in the Theoretical Physics and Biological Computation departments. He is a Fellow of the IEEE and AAAI and has received the National Science Foundation CAREER award and the University of Pennsylvania Lindback award for distinguished teaching.

He was also a fellow of the Hebrew University Institute of Advanced Studies in Jerusalem, an affiliate of the Korea Advanced Institute of Science and Technology, and has organized the US-Japan National Academy of Engineering Frontiers of Engineering symposium and the Neural Information Processing Systems conference. As director of the GRASP Laboratory and co-director of the CMU-Penn University Transportation Center, his group focuses on understanding general computational principles in biological systems, and on applying that knowledge to build autonomous systems.

“Artificial Intelligence: Information Theory Perspective”

Prof. Sae-Young Chung (정세영 교수)

Korea Advanced Institue of Science and Technology

Abstract:

Recent Lee Sedol vs. AlphaGo match successfully demonstrated that machines can now have human-like intuition. Deep learning, which was a key component in AlphaGo's excellent performance, has also been successful in many other areas including image and speech recognition, game playing, and natural language processing. However, current deep learning techniques require a large amount of data for proper training. On the other hand, humans can learn very well even with few training examples, which is not easy with current deep learning approaches. If this problem can be solved, deep learning can be a powerful tool in developing more human-like artificial intelligence. In this talk, I will show some recent approaches based on information theory that can be useful in solving such problems.