Utama
Neural Networks and Deep Learning: A Textbook
Neural Networks and Deep Learning: A Textbook
Charu C. Aggarwal
This book covers both classical and modern models in deep learning. The primary focus is on the theory and algorithms of deep learning. The theory and algorithms of neural networks are particularly important for understanding important concepts, so that one can understand the important design concepts of neural architectures in different applications. Why do neural networks work? When do they work better than offtheshelf machinelearning models? When is depth useful? Why is training neural networks so hard? What are the pitfalls? The book is also rich in discussing different applications in order to give the practitioner a flavor of how neural architectures are designed for different types of problems. Applications associated with many different areas like recommender systems, machine translation, image captioning, image classification, reinforcementlearning based gaming, and text analytics are covered. The chapters of this book span three categories: The basics of neural networks: Many traditional machine learning models can be understood as special cases of neural networks. An emphasis is placed in the first two chapters on understanding the relationship between traditional machine learning and neural networks. Support vector machines, linear/logistic regression, singular value decomposition, matrix factorization, and recommender systems are shown to be special cases of neural networks. These methods are studied together with recent feature engineering methods like word2vec. Fundamentals of neural networks: A detailed discussion of training and regularization is provided in Chapters 3 and 4. Chapters 5 and 6 present radialbasis function (RBF) networks and restricted Boltzmann machines. Advanced topics in neural networks: Chapters 7 and 8 discuss recurrent neural networks and convolutional neural networks. Several advanced topics like deep reinforcement learning, neural Turing machines, Kohonen selforganizing maps, and generative adversarial networks are introduced in Chapters 9 and 10. The book is written for graduate students, researchers, and practitioners. Numerous exercises are available along with a solution manual to aid in classroom teaching. Where possible, an applicationcentric view is highlighted in order to provide an understanding of the practical uses of each class of techniques.
Tahun:
2018
Penerbit:
Springer
Bahasa:
english
Halaman:
524 / 512
ISBN 10:
3319944622
ISBN 13:
9783319944623
File:
PDF, 5.15 MB
Unduh (pdf, 5.15 MB)
Baca buku online
 Open in Browser
 Checking other formats...
 Please login to your account first

Need help? Please read our short guide how to send a book to Kindle.
The file will be sent to your email address. It may take up to 15 minutes before you receive it.
The file will be sent to your Kindle account. It may takes up to 15 minutes before you received it.
Please note you need to add our email km@bookmail.org to approved email addresses. Read more.
Please note you need to add our email km@bookmail.org to approved email addresses. Read more.
You may be interested in
Most frequently terms
neural^{1804}
networks^{1404}
neural networks^{865}
input^{688}
neural network^{663}
layers^{655}
output^{644}
gradient^{578}
weights^{493}
matrix^{465}
convolutional^{433}
activation^{415}
units^{380}
recurrent^{380}
vector^{368}
architecture^{359}
backpropagation^{346}
algorithm^{317}
parameters^{300}
convolutional neural^{267}
linear^{256}
autoencoder^{245}
recurrent neural^{232}
regularization^{226}
dimensional^{226}
update^{225}
nodes^{223}
representation^{218}
descent^{210}
spatial^{205}
furthermore^{204}
reinforcement learning^{203}
equation^{202}
boltzmann^{201}
updates^{195}
parameter^{195}
prediction^{193}
node^{189}
inputs^{187}
applications^{186}
architectures^{184}
perceptron^{183}
outputs^{173}
convolution^{171}
computed^{171}
corresponding^{170}
https^{169}
regression^{169}
computational^{161}
binary^{159}
activations^{154}
probability^{152}
samples^{151}
derivative^{148}
compute^{147}
sigmoid^{147}
batch^{142}
unsupervised^{142}
You can write a book review and share your experiences. Other readers will always be interested in your opinion of the books you've read. Whether you've loved the book or not, if you give your honest and detailed thoughts then people will find new books that are right for them.
1

2

Charu C. Aggarwal Neural Networks and Deep Learning A Textbook Neural Networks and Deep Learning Charu C. Aggarwal Neural Networks and Deep Learning A Textbook 123 Charu C. Aggarwal IBM T. J. Watson Research Center International Business Machines Yorktown Heights, NY, USA ISBN 9783319944623 ISBN 9783319944630 (eBook) https://doi.org/10.1007/9783319944630 Library of Congress Control Number: 2018947636 c Springer International Publishing AG, part of Springer Nature 2018 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. This Springer imprint is published by the registered company Springer Nature Switzerland AG The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland To my wife Lata, my daughter Sayani, and my late parents Dr. Prem Sarup and Mrs. Pushplata Aggarwal. Preface “Any A.I. smart enough to pass a Tur; ing test is smart enough to know to fail it.”—Ian McDonald Neural networks were developed to simulate the human nervous system for machine learning tasks by treating the computational units in a learning model in a manner similar to human neurons. The grand vision of neural networks is to create artiﬁcial intelligence by building machines whose architecture simulates the computations in the human nervous system. This is obviously not a simple task because the computational power of the fastest computer today is a minuscule fraction of the computational power of a human brain. Neural networks were developed soon after the advent of computers in the ﬁfties and sixties. Rosenblatt’s perceptron algorithm was seen as a fundamental cornerstone of neural networks, which caused an initial excitement about the prospects of artiﬁcial intelligence. However, after the initial euphoria, there was a period of disappointment in which the data hungry and computationally intensive nature of neural networks was seen as an impediment to their usability. Eventually, at the turn of the century, greater data availability and increasing computational power lead to increased successes of neural networks, and this area was reborn under the new label of “deep learning.” Although we are still far from the day that artiﬁcial intelligence (AI) is close to human performance, there are speciﬁc domains like image recognition, selfdriving cars, and game playing, where AI has matched or exceeded human performance. It is also hard to predict what AI might be able to do in the future. For example, few computer vision experts would have thought two decades ago that any automated system could ever perform an intuitive task like categorizing an image more accurately than a human. Neural networks are theoretically capable of learning any mathematical function with suﬃcient training data, and some variants like recurrent neural networks are known to be Turing complete. Turing completeness refers to the fact that a neural network can simulate any learning algorithm, given suﬃcient training data. The sticking point is that the amount of data required to learn even simple tasks is often extraordinarily large, which causes a corresponding increase in training time (if we assume that enough training data is available in the ﬁrst place). For example, the training time for image recognition, which is a simple task for a human, can be on the order of weeks even on highperformance systems. Furthermore, there are practical issues associated with the stability of neural network training, which are being resolved even today. Nevertheless, given that the speed of computers is VII VIII PREFACE expected to increase rapidly over time, and fundamentally more powerful paradigms like quantum computing are on the horizon, the computational issue might not eventually turn out to be quite as critical as imagined. Although the biological analogy of neural networks is an exciting one and evokes comparisons with science ﬁction, the mathematical understanding of neural networks is a more mundane one. The neural network abstraction can be viewed as a modular approach of enabling learning algorithms that are based on continuous optimization on a computational graph of dependencies between the input and output. To be fair, this is not very diﬀerent from traditional work in control theory; indeed, some of the methods used for optimization in control theory are strikingly similar to (and historically preceded) the most fundamental algorithms in neural networks. However, the large amounts of data available in recent years together with increased computational power have enabled experimentation with deeper architectures of these computational graphs than was previously possible. The resulting success has changed the broader perception of the potential of deep learning. The chapters of the book are organized as follows: 1. The basics of neural networks: Chapter 1 discusses the basics of neural network design. Many traditional machine learning models can be understood as special cases of neural learning. Understanding the relationship between traditional machine learning and neural networks is the ﬁrst step to understanding the latter. The simulation of various machine learning models with neural networks is provided in Chapter 2. This will give the analyst a feel of how neural networks push the envelope of traditional machine learning algorithms. 2. Fundamentals of neural networks: Although Chapters 1 and 2 provide an overview of the training methods for neural networks, a more detailed understanding of the training challenges is provided in Chapters 3 and 4. Chapters 5 and 6 present radialbasis function (RBF) networks and restricted Boltzmann machines. 3. Advanced topics in neural networks: A lot of the recent success of deep learning is a result of the specialized architectures for various domains, such as recurrent neural networks and convolutional neural networks. Chapters 7 and 8 discuss recurrent and convolutional neural networks. Several advanced topics like deep reinforcement learning, neural Turing mechanisms, and generative adversarial networks are discussed in Chapters 9 and 10. We have taken care to include some of the “forgotten” architectures like RBF networks and Kohonen selforganizing maps because of their potential in many applications. The book is written for graduate students, researchers, and practitioners. Numerous exercises are available along with a solution manual to aid in classroom teaching. Where possible, an applicationcentric view is highlighted in order to give the reader a feel for the technology. Throughout this book, a vector or a multidimensional data point is annotated with a bar, such as X or y. A vector or multidimensional point may be denoted by either small letters or capital letters, as long as it has a bar. Vector dot products are denoted by centered dots, such as X · Y . A matrix is denoted in capital letters without a bar, such as R. Throughout the book, the n × d matrix corresponding to the entire training data set is denoted by D, with n documents and d dimensions. The individual data points in D are therefore ddimensional row vectors. On the other hand, vectors with one component for each data PREFACE IX point are usually ndimensional column vectors. An example is the ndimensional column vector y of class variables of n data points. An observed value yi is distinguished from a predicted value ŷi by a circumﬂex at the top of the variable. Yorktown Heights, NY, USA Charu C. Aggarwal Acknowledgments I would like to thank my family for their love and support during the busy time spent in writing this book. I would also like to thank my manager Nagui Halim for his support during the writing of this book. Several ﬁgures in this book have been provided by the courtesy of various individuals and institutions. The Smithsonian Institution made the image of the Mark I perceptron (cf. Figure 1.5) available at no cost. Saket Sathe provided the outputs in Chapter 7 for the tiny Shakespeare data set, based on code available/described in [233, 580]. Andrew Zisserman provided Figures 8.12 and 8.16 in the section on convolutional visualizations. Another visualization of the feature maps in the convolution network (cf. Figure 8.15) was provided by Matthew Zeiler. NVIDIA provided Figure 9.10 on the convolutional neural network for selfdriving cars in Chapter 9, and Sergey Levine provided the image on selflearning robots (cf. Figure 9.9) in the same chapter. Alec Radford provided Figure 10.8, which appears in Chapter 10. Alex Krizhevsky provided Figure 8.9(b) containing AlexNet. This book has beneﬁtted from signiﬁcant feedback and several collaborations that I have had with numerous colleagues over the years. I would like to thank Quoc Le, Saket Sathe, Karthik Subbian, Jiliang Tang, and Suhang Wang for their feedback on various portions of this book. Shuai Zheng provided feedbback on the section on regularized autoencoders in Chapter 4. I received feedback on the sections on autoencoders from Lei Cai and Hao Yuan. Feedback on the chapter on convolutional neural networks was provided by Hongyang Gao, Shuiwang Ji, and Zhengyang Wang. Shuiwang Ji, Lei Cai, Zhengyang Wang and Hao Yuan also reviewed the Chapters 3 and 7, and suggested several edits. They also suggested the ideas of using Figures 8.6 and 8.7 for elucidating the convolution/deconvolution operations. For their collaborations, I would like to thank Tarek F. Abdelzaher, Jinghui Chen, Jing Gao, Quanquan Gu, Manish Gupta, Jiawei Han, Alexander Hinneburg, Thomas Huang, Nan Li, Huan Liu, Ruoming Jin, Daniel Keim, Arijit Khan, Latifur Khan, Mohammad M. Masud, Jian Pei, Magda Procopiuc, Guojun Qi, Chandan Reddy, Saket Sathe, Jaideep Srivastava, Karthik Subbian, Yizhou Sun, Jiliang Tang, MinHsuan Tsai, Haixun Wang, Jianyong Wang, Min Wang, Suhang Wang, Joel Wolf, Xifeng Yan, Mohammed Zaki, ChengXiang Zhai, and Peixiang Zhao. I would also like to thank my advisor James B. Orlin for his guidance during my early years as a researcher. XI XII ACKNOWLEDGMENTS I would like to thank Lata Aggarwal for helping me with some of the ﬁgures created using PowerPoint graphics in this book. My daughter, Sayani, was helpful in incorporating special eﬀects (e.g., image color, contrast, and blurring) in several JPEG images used at various places in this book. Contents 1 An Introduction to Neural Networks 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Humans Versus Computers: Stretching the Limits of Artiﬁcial Intelligence . . . . . . . . . . . . . . . . . . . . . . . . 1.2 The Basic Architecture of Neural Networks . . . . . . . . . . . . . . . . . 1.2.1 Single Computational Layer: The Perceptron . . . . . . . . . . . . 1.2.1.1 What Objective Function Is the Perceptron Optimizing? 1.2.1.2 Relationship with Support Vector Machines . . . . . . . . 1.2.1.3 Choice of Activation and Loss Functions . . . . . . . . . 1.2.1.4 Choice and Number of Output Nodes . . . . . . . . . . . 1.2.1.5 Choice of Loss Function . . . . . . . . . . . . . . . . . . . 1.2.1.6 Some Useful Derivatives of Activation Functions . . . . . 1.2.2 Multilayer Neural Networks . . . . . . . . . . . . . . . . . . . . . . 1.2.3 The Multilayer Network as a Computational Graph . . . . . . . . 1.3 Training a Neural Network with Backpropagation . . . . . . . . . . . . . . 1.4 Practical Issues in Neural Network Training . . . . . . . . . . . . . . . . . 1.4.1 The Problem of Overﬁtting . . . . . . . . . . . . . . . . . . . . . . 1.4.1.1 Regularization . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1.2 Neural Architecture and Parameter Sharing . . . . . . . . 1.4.1.3 Early Stopping . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1.4 Trading Oﬀ Breadth for Depth . . . . . . . . . . . . . . . 1.4.1.5 Ensemble Methods . . . . . . . . . . . . . . . . . . . . . . 1.4.2 The Vanishing and Exploding Gradient Problems . . . . . . . . . . 1.4.3 Diﬃculties in Convergence . . . . . . . . . . . . . . . . . . . . . . . 1.4.4 Local and Spurious Optima . . . . . . . . . . . . . . . . . . . . . . 1.4.5 Computational Challenges . . . . . . . . . . . . . . . . . . . . . . . 1.5 The Secrets to the Power of Function Composition . . . . . . . . . . . . . 1.5.1 The Importance of Nonlinear Activation . . . . . . . . . . . . . . . 1.5.2 Reducing Parameter Requirements with Depth . . . . . . . . . . . 1.5.3 Unconventional Neural Architectures . . . . . . . . . . . . . . . . . 1.5.3.1 Blurring the Distinctions Between Input, Hidden, and Output Layers . . . . . . . . . . . . . . . . . . . . . . 1.5.3.2 Unconventional Operations and SumProduct Networks . . 1 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 4 5 8 10 11 14 14 16 17 20 21 24 25 26 27 27 27 28 28 29 29 29 30 32 34 35 . . 35 36 XIII CONTENTS XIV 1.6 Common Neural Architectures . . . . . . . . . . . . . . . . . . . 1.6.1 Simulating Basic Machine Learning with Shallow Models 1.6.2 Radial Basis Function Networks . . . . . . . . . . . . . . 1.6.3 Restricted Boltzmann Machines . . . . . . . . . . . . . . . 1.6.4 Recurrent Neural Networks . . . . . . . . . . . . . . . . . 1.6.5 Convolutional Neural Networks . . . . . . . . . . . . . . . 1.6.6 Hierarchical Feature Engineering and Pretrained Models . 1.7 Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7.1 Reinforcement Learning . . . . . . . . . . . . . . . . . . . 1.7.2 Separating Data Storage and Computations . . . . . . . . 1.7.3 Generative Adversarial Networks . . . . . . . . . . . . . . 1.8 Two Notable Benchmarks . . . . . . . . . . . . . . . . . . . . . . 1.8.1 The MNIST Database of Handwritten Digits . . . . . . . 1.8.2 The ImageNet Database . . . . . . . . . . . . . . . . . . . 1.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . 1.10.1 Video Lectures . . . . . . . . . . . . . . . . . . . . . . . . 1.10.2 Software Resources . . . . . . . . . . . . . . . . . . . . . . 1.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 37 37 38 38 40 42 44 44 45 45 46 46 47 48 48 50 50 51 2 Machine Learning with Shallow Neural Networks 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Neural Architectures for Binary Classiﬁcation Models . . . . . . 2.2.1 Revisiting the Perceptron . . . . . . . . . . . . . . . . . . 2.2.2 LeastSquares Regression . . . . . . . . . . . . . . . . . . 2.2.2.1 WidrowHoﬀ Learning . . . . . . . . . . . . . . . 2.2.2.2 Closed Form Solutions . . . . . . . . . . . . . . . 2.2.3 Logistic Regression . . . . . . . . . . . . . . . . . . . . . . 2.2.3.1 Alternative Choices of Activation and Loss . . . 2.2.4 Support Vector Machines . . . . . . . . . . . . . . . . . . 2.3 Neural Architectures for Multiclass Models . . . . . . . . . . . . 2.3.1 Multiclass Perceptron . . . . . . . . . . . . . . . . . . . . 2.3.2 WestonWatkins SVM . . . . . . . . . . . . . . . . . . . . 2.3.3 Multinomial Logistic Regression (Softmax Classiﬁer) . . . 2.3.4 Hierarchical Softmax for Many Classes . . . . . . . . . . . 2.4 Backpropagated Saliency for Feature Selection . . . . . . . . . . 2.5 Matrix Factorization with Autoencoders . . . . . . . . . . . . . . 2.5.1 Autoencoder: Basic Principles . . . . . . . . . . . . . . . . 2.5.1.1 Autoencoder with a Single Hidden Layer . . . . 2.5.1.2 Connections with Singular Value Decomposition 2.5.1.3 Sharing Weights in Encoder and Decoder . . . . 2.5.1.4 Other Matrix Factorization Methods . . . . . . . 2.5.2 Nonlinear Activations . . . . . . . . . . . . . . . . . . . . 2.5.3 Deep Autoencoders . . . . . . . . . . . . . . . . . . . . . . 2.5.4 Application to Outlier Detection . . . . . . . . . . . . . . 2.5.5 When the Hidden Layer Is Broader than the Input Layer 2.5.5.1 Sparse Feature Learning . . . . . . . . . . . . . . 2.5.6 Other Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 53 55 56 58 59 61 61 63 63 65 65 67 68 69 70 70 71 72 74 74 76 76 78 80 81 81 82 CONTENTS XV 2.5.7 Recommender Systems: Row Index to Row Value Prediction 2.5.8 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Word2vec: An Application of Simple Neural Architectures . . . . . . 2.6.1 Neural Embedding with Continuous Bag of Words . . . . . . 2.6.2 Neural Embedding with SkipGram Model . . . . . . . . . . . 2.6.3 Word2vec (SGNS) Is Logistic Matrix Factorization . . . . . . 2.6.4 Vanilla SkipGram Is Multinomial Matrix Factorization . . . 2.7 Simple Neural Architectures for Graph Embeddings . . . . . . . . . 2.7.1 Handling Arbitrary Edge Counts . . . . . . . . . . . . . . . . 2.7.2 Multinomial Model . . . . . . . . . . . . . . . . . . . . . . . . 2.7.3 Connections with DeepWalk and Node2vec . . . . . . . . . . 2.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9.1 Software Resources . . . . . . . . . . . . . . . . . . . . . . . . 2.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 86 87 87 90 95 98 98 100 100 100 101 101 102 103 3 Training Deep Neural Networks 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Backpropagation: The Gory Details . . . . . . . . . . . . . . . . . . . 3.2.1 Backpropagation with the Computational Graph Abstraction 3.2.2 Dynamic Programming to the Rescue . . . . . . . . . . . . . 3.2.3 Backpropagation with PostActivation Variables . . . . . . . 3.2.4 Backpropagation with Preactivation Variables . . . . . . . . 3.2.5 Examples of Updates for Various Activations . . . . . . . . . 3.2.5.1 The Special Case of Softmax . . . . . . . . . . . . . 3.2.6 A Decoupled View of VectorCentric Backpropagation . . . . 3.2.7 Loss Functions on Multiple Output Nodes and Hidden Nodes 3.2.8 MiniBatch Stochastic Gradient Descent . . . . . . . . . . . . 3.2.9 Backpropagation Tricks for Handling Shared Weights . . . . 3.2.10 Checking the Correctness of Gradient Computation . . . . . 3.3 Setup and Initialization Issues . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Tuning Hyperparameters . . . . . . . . . . . . . . . . . . . . 3.3.2 Feature Preprocessing . . . . . . . . . . . . . . . . . . . . . . 3.3.3 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 The Vanishing and Exploding Gradient Problems . . . . . . . . . . . 3.4.1 Geometric Understanding of the Eﬀect of Gradient Ratios . . 3.4.2 A Partial Fix with Activation Function Choice . . . . . . . . 3.4.3 Dying Neurons and “Brain Damage” . . . . . . . . . . . . . . 3.4.3.1 Leaky ReLU . . . . . . . . . . . . . . . . . . . . . . 3.4.3.2 Maxout . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 GradientDescent Strategies . . . . . . . . . . . . . . . . . . . . . . . 3.5.1 Learning Rate Decay . . . . . . . . . . . . . . . . . . . . . . . 3.5.2 MomentumBased Learning . . . . . . . . . . . . . . . . . . . 3.5.2.1 Nesterov Momentum . . . . . . . . . . . . . . . . . 3.5.3 ParameterSpeciﬁc Learning Rates . . . . . . . . . . . . . . . 3.5.3.1 AdaGrad . . . . . . . . . . . . . . . . . . . . . . . . 3.5.3.2 RMSProp . . . . . . . . . . . . . . . . . . . . . . . . 3.5.3.3 RMSProp with Nesterov Momentum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 105 107 107 111 113 115 117 117 118 121 121 123 124 125 125 126 128 129 130 133 133 133 134 134 135 136 137 137 138 138 139 XVI CONTENTS 3.5.3.4 AdaDelta . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.3.5 Adam . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.4 Cliﬀs and HigherOrder Instability . . . . . . . . . . . . . . . . 3.5.5 Gradient Clipping . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.6 SecondOrder Derivatives . . . . . . . . . . . . . . . . . . . . . 3.5.6.1 Conjugate Gradients and HessianFree Optimization . 3.5.6.2 QuasiNewton Methods and BFGS . . . . . . . . . . . 3.5.6.3 Problems with SecondOrder Methods: Saddle Points 3.5.7 Polyak Averaging . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.8 Local and Spurious Minima . . . . . . . . . . . . . . . . . . . . 3.6 Batch Normalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Practical Tricks for Acceleration and Compression . . . . . . . . . . . 3.7.1 GPU Acceleration . . . . . . . . . . . . . . . . . . . . . . . . . 3.7.2 Parallel and Distributed Implementations . . . . . . . . . . . . 3.7.3 Algorithmic Tricks for Model Compression . . . . . . . . . . . 3.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9.1 Software Resources . . . . . . . . . . . . . . . . . . . . . . . . . 3.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Teaching Deep Learners to Generalize 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 The BiasVariance TradeOﬀ . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Formal View . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Generalization Issues in Model Tuning and Evaluation . . . . . . . . 4.3.1 Evaluating with HoldOut and CrossValidation . . . . . . . . 4.3.2 Issues with Training at Scale . . . . . . . . . . . . . . . . . . 4.3.3 How to Detect Need to Collect More Data . . . . . . . . . . . 4.4 PenaltyBased Regularization . . . . . . . . . . . . . . . . . . . . . . 4.4.1 Connections with Noise Injection . . . . . . . . . . . . . . . . 4.4.2 L1 Regularization . . . . . . . . . . . . . . . . . . . . . . . . 4.4.3 L1  or L2 Regularization? . . . . . . . . . . . . . . . . . . . . 4.4.4 Penalizing Hidden Units: Learning Sparse Representations . . 4.5 Ensemble Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5.1 Bagging and Subsampling . . . . . . . . . . . . . . . . . . . . 4.5.2 Parametric Model Selection and Averaging . . . . . . . . . . 4.5.3 Randomized Connection Dropping . . . . . . . . . . . . . . . 4.5.4 Dropout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5.5 Data Perturbation Ensembles . . . . . . . . . . . . . . . . . . 4.6 Early Stopping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6.1 Understanding Early Stopping from the Variance Perspective 4.7 Unsupervised Pretraining . . . . . . . . . . . . . . . . . . . . . . . . 4.7.1 Variations of Unsupervised Pretraining . . . . . . . . . . . . . 4.7.2 What About Supervised Pretraining? . . . . . . . . . . . . . 4.8 Continuation and Curriculum Learning . . . . . . . . . . . . . . . . . 4.8.1 Continuation Learning . . . . . . . . . . . . . . . . . . . . . . 4.8.2 Curriculum Learning . . . . . . . . . . . . . . . . . . . . . . . 4.9 Parameter Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 140 141 142 143 145 148 149 151 151 152 156 157 158 160 163 163 165 165 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 169 174 175 178 179 180 181 181 182 183 184 185 186 186 187 188 188 191 192 192 193 197 197 199 199 200 200 CONTENTS XVII 4.10 Regularization in Unsupervised Applications . . . . . . . . . . . . . 4.10.1 ValueBased Penalization: Sparse Autoencoders . . . . . . . . 4.10.2 Noise Injection: Denoising Autoencoders . . . . . . . . . . . 4.10.3 GradientBased Penalization: Contractive Autoencoders . . . 4.10.4 Hidden Probabilistic Structure: Variational Autoencoders . . 4.10.4.1 Reconstruction and Generative Sampling . . . . . . 4.10.4.2 Conditional Variational Autoencoders . . . . . . . . 4.10.4.3 Relationship with Generative Adversarial Networks 4.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.12 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.12.1 Software Resources . . . . . . . . . . . . . . . . . . . . . . . . 4.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Radial Basis Function Networks 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Training an RBF Network . . . . . . . . . . . . . . . . . . . . 5.2.1 Training the Hidden Layer . . . . . . . . . . . . . . . . 5.2.2 Training the Output Layer . . . . . . . . . . . . . . . 5.2.2.1 Expression with PseudoInverse . . . . . . . 5.2.3 Orthogonal LeastSquares Algorithm . . . . . . . . . . 5.2.4 Fully Supervised Learning . . . . . . . . . . . . . . . . 5.3 Variations and Special Cases of RBF Networks . . . . . . . . 5.3.1 Classiﬁcation with Perceptron Criterion . . . . . . . . 5.3.2 Classiﬁcation with Hinge Loss . . . . . . . . . . . . . . 5.3.3 Example of Linear Separability Promoted by RBF . . 5.3.4 Application to Interpolation . . . . . . . . . . . . . . . 5.4 Relationship with Kernel Methods . . . . . . . . . . . . . . . 5.4.1 Kernel Regression as a Special Case of RBF Networks 5.4.2 Kernel SVM as a Special Case of RBF Networks . . . 5.4.3 Observations . . . . . . . . . . . . . . . . . . . . . . . 5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . 5.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 202 202 204 207 210 212 213 213 214 215 215 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 217 220 221 222 224 224 225 226 226 227 227 228 229 229 230 231 231 232 232 6 Restricted Boltzmann Machines 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1.1 Historical Perspective . . . . . . . . . . . . . . . . . . . . 6.2 Hopﬁeld Networks . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.1 Optimal State Conﬁgurations of a Trained Network . . . 6.2.2 Training a Hopﬁeld Network . . . . . . . . . . . . . . . . 6.2.3 Building a Toy Recommender and Its Limitations . . . . 6.2.4 Increasing the Expressive Power of the Hopﬁeld Network 6.3 The Boltzmann Machine . . . . . . . . . . . . . . . . . . . . . . . 6.3.1 How a Boltzmann Machine Generates Data . . . . . . . . 6.3.2 Learning the Weights of a Boltzmann Machine . . . . . . 6.4 Restricted Boltzmann Machines . . . . . . . . . . . . . . . . . . . 6.4.1 Training the RBM . . . . . . . . . . . . . . . . . . . . . . 6.4.2 Contrastive Divergence Algorithm . . . . . . . . . . . . . 6.4.3 Practical Issues and Improvisations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 235 236 237 238 240 241 242 243 244 245 247 249 250 251 . . . . . . . . . . . . . . . . . . . CONTENTS XVIII 6.5 Applications of Restricted Boltzmann Machines . . . . . . . . 6.5.1 Dimensionality Reduction and Data Reconstruction . 6.5.2 RBMs for Collaborative Filtering . . . . . . . . . . . . 6.5.3 Using RBMs for Classiﬁcation . . . . . . . . . . . . . . 6.5.4 Topic Models with RBMs . . . . . . . . . . . . . . . . 6.5.5 RBMs for Machine Learning with Multimodal Data . 6.6 Using RBMs Beyond Binary Data Types . . . . . . . . . . . . 6.7 Stacking Restricted Boltzmann Machines . . . . . . . . . . . 6.7.1 Unsupervised Learning . . . . . . . . . . . . . . . . . . 6.7.2 Supervised Learning . . . . . . . . . . . . . . . . . . . 6.7.3 Deep Boltzmann Machines and Deep Belief Networks 6.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . 6.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 252 254 257 260 262 263 264 266 267 267 268 268 270 7 Recurrent Neural Networks 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1.1 Expressiveness of Recurrent Networks . . . . . . . . . . . 7.2 The Architecture of Recurrent Neural Networks . . . . . . . . . . 7.2.1 Language Modeling Example of RNN . . . . . . . . . . . 7.2.1.1 Generating a Language Sample . . . . . . . . . . 7.2.2 Backpropagation Through Time . . . . . . . . . . . . . . 7.2.3 Bidirectional Recurrent Networks . . . . . . . . . . . . . . 7.2.4 Multilayer Recurrent Networks . . . . . . . . . . . . . . . 7.3 The Challenges of Training Recurrent Networks . . . . . . . . . . 7.3.1 Layer Normalization . . . . . . . . . . . . . . . . . . . . . 7.4 EchoState Networks . . . . . . . . . . . . . . . . . . . . . . . . . 7.5 Long ShortTerm Memory (LSTM) . . . . . . . . . . . . . . . . . 7.6 Gated Recurrent Units (GRUs) . . . . . . . . . . . . . . . . . . . 7.7 Applications of Recurrent Neural Networks . . . . . . . . . . . . 7.7.1 Application to Automatic Image Captioning . . . . . . . . 7.7.2 SequencetoSequence Learning and Machine Translation 7.7.2.1 QuestionAnswering Systems . . . . . . . . . . . 7.7.3 Application to SentenceLevel Classiﬁcation . . . . . . . . 7.7.4 TokenLevel Classiﬁcation with Linguistic Features . . . . 7.7.5 TimeSeries Forecasting and Prediction . . . . . . . . . . 7.7.6 Temporal Recommender Systems . . . . . . . . . . . . . . 7.7.7 Secondary Protein Structure Prediction . . . . . . . . . . 7.7.8 EndtoEnd Speech Recognition . . . . . . . . . . . . . . . 7.7.9 Handwriting Recognition . . . . . . . . . . . . . . . . . . 7.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . 7.9.1 Software Resources . . . . . . . . . . . . . . . . . . . . . . 7.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 271 274 274 277 278 280 283 284 286 289 290 292 295 297 298 299 301 303 304 305 307 309 309 309 310 310 311 312 CONTENTS XIX 8 Convolutional Neural Networks 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1.1 Historical Perspective and Biological Inspiration . . . . . . . . . 8.1.2 Broader Observations About Convolutional Neural Networks . . 8.2 The Basic Structure of a Convolutional Network . . . . . . . . . . . . . 8.2.1 Padding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2.2 Strides . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2.3 Typical Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2.4 The ReLU Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2.5 Pooling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2.6 Fully Connected Layers . . . . . . . . . . . . . . . . . . . . . . . 8.2.7 The Interleaving Between Layers . . . . . . . . . . . . . . . . . . 8.2.8 Local Response Normalization . . . . . . . . . . . . . . . . . . . 8.2.9 Hierarchical Feature Engineering . . . . . . . . . . . . . . . . . . 8.3 Training a Convolutional Network . . . . . . . . . . . . . . . . . . . . . 8.3.1 Backpropagating Through Convolutions . . . . . . . . . . . . . . 8.3.2 Backpropagation as Convolution with Inverted/Transposed Filter 8.3.3 Convolution/Backpropagation as Matrix Multiplications . . . . . 8.3.4 Data Augmentation . . . . . . . . . . . . . . . . . . . . . . . . . 8.4 Case Studies of Convolutional Architectures . . . . . . . . . . . . . . . . 8.4.1 AlexNet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4.2 ZFNet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4.3 VGG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4.4 GoogLeNet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4.5 ResNet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4.6 The Eﬀects of Depth . . . . . . . . . . . . . . . . . . . . . . . . . 8.4.7 Pretrained Models . . . . . . . . . . . . . . . . . . . . . . . . . . 8.5 Visualization and Unsupervised Learning . . . . . . . . . . . . . . . . . 8.5.1 Visualizing the Features of a Trained Network . . . . . . . . . . 8.5.2 Convolutional Autoencoders . . . . . . . . . . . . . . . . . . . . . 8.6 Applications of Convolutional Networks . . . . . . . . . . . . . . . . . . 8.6.1 ContentBased Image Retrieval . . . . . . . . . . . . . . . . . . . 8.6.2 Object Localization . . . . . . . . . . . . . . . . . . . . . . . . . 8.6.3 Object Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.6.4 Natural Language and Sequence Learning . . . . . . . . . . . . . 8.6.5 Video Classiﬁcation . . . . . . . . . . . . . . . . . . . . . . . . . 8.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.8 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.8.1 Software Resources and Data Sets . . . . . . . . . . . . . . . . . 8.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 315 316 317 318 322 324 324 325 326 327 328 330 331 332 333 334 335 337 338 339 341 342 345 347 350 351 352 353 357 363 363 364 365 366 367 368 368 370 371 9 Deep Reinforcement Learning 9.1 Introduction . . . . . . . . . . . . . . . . . . . . . 9.2 Stateless Algorithms: MultiArmed Bandits . . . 9.2.1 Naı̈ve Algorithm . . . . . . . . . . . . . . 9.2.2 Greedy Algorithm . . . . . . . . . . . . 9.2.3 Upper Bounding Methods . . . . . . . . . 9.3 The Basic Framework of Reinforcement Learning 9.3.1 Challenges of Reinforcement Learning . . . . . . . . . . . . . . . . 373 373 375 376 376 376 377 379 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CONTENTS XX 9.3.2 Simple Reinforcement Learning for TicTacToe . . . . . . . . . . 9.3.3 Role of Deep Learning and a StrawMan Algorithm . . . . . . . 9.4 Bootstrapping for Value Function Learning . . . . . . . . . . . . . . . . 9.4.1 Deep Learning Models as Function Approximators . . . . . . . . 9.4.2 Example: Neural Network for Atari Setting . . . . . . . . . . . . 9.4.3 OnPolicy Versus OﬀPolicy Methods: SARSA . . . . . . . . . . 9.4.4 Modeling States Versus StateAction Pairs . . . . . . . . . . . . . 9.5 Policy Gradient Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 9.5.1 Finite Diﬀerence Methods . . . . . . . . . . . . . . . . . . . . . . 9.5.2 Likelihood Ratio Methods . . . . . . . . . . . . . . . . . . . . . . 9.5.3 Combining Supervised Learning with Policy Gradients . . . . . . 9.5.4 ActorCritic Methods . . . . . . . . . . . . . . . . . . . . . . . . 9.5.5 Continuous Action Spaces . . . . . . . . . . . . . . . . . . . . . . 9.5.6 Advantages and Disadvantages of Policy Gradients . . . . . . . . 9.6 Monte Carlo Tree Search . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.7 Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.7.1 AlphaGo: Championship Level Play at Go . . . . . . . . . . . . . 9.7.1.1 Alpha Zero: Enhancements to Zero Human Knowledge 9.7.2 SelfLearning Robots . . . . . . . . . . . . . . . . . . . . . . . . . 9.7.2.1 Deep Learning of Locomotion Skills . . . . . . . . . . . 9.7.2.2 Deep Learning of Visuomotor Skills . . . . . . . . . . . 9.7.3 Building Conversational Systems: Deep Learning for Chatbots . 9.7.4 SelfDriving Cars . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.7.5 Inferring Neural Architectures with Reinforcement Learning . . . 9.8 Practical Challenges Associated with Safety . . . . . . . . . . . . . . . . 9.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.10.1 Software Resources and Testbeds . . . . . . . . . . . . . . . . . . 9.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Advanced Topics in Deep Learning 10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.2 Attention Mechanisms . . . . . . . . . . . . . . . . . . . . . . . 10.2.1 Recurrent Models of Visual Attention . . . . . . . . . . 10.2.1.1 Application to Image Captioning . . . . . . . . 10.2.2 Attention Mechanisms for Machine Translation . . . . . 10.3 Neural Networks with External Memory . . . . . . . . . . . . . 10.3.1 A Fantasy Video Game: Sorting by Example . . . . . . 10.3.1.1 Implementing Swaps with Memory Operations 10.3.2 Neural Turing Machines . . . . . . . . . . . . . . . . . . 10.3.3 Diﬀerentiable Neural Computer: A Brief Overview . . . 10.4 Generative Adversarial Networks (GANs) . . . . . . . . . . . . 10.4.1 Training a Generative Adversarial Network . . . . . . . 10.4.2 Comparison with Variational Autoencoder . . . . . . . . 10.4.3 Using GANs for Generating Image Data . . . . . . . . . 10.4.4 Conditional Generative Adversarial Networks . . . . . . 10.5 Competitive Learning . . . . . . . . . . . . . . . . . . . . . . . 10.5.1 Vector Quantization . . . . . . . . . . . . . . . . . . . . 10.5.2 Kohonen SelfOrganizing Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380 380 383 384 386 387 389 391 392 393 395 395 397 397 398 399 399 402 404 404 406 407 410 412 413 414 414 416 416 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419 419 421 422 424 425 429 430 431 432 437 438 439 442 442 444 449 450 450 CONTENTS 10.6 Limitations of Neural Networks . . . . . . . . . . . . . . 10.6.1 An Aspirational Goal: OneShot Learning . . . . 10.6.2 An Aspirational Goal: EnergyEﬃcient Learning 10.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . 10.8 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . 10.8.1 Software Resources . . . . . . . . . . . . . . . . . 10.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . XXI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453 453 455 456 457 458 458 Bibliography 459 Index 493 Author Biography Charu C. Aggarwal is a Distinguished Research Staﬀ Member (DRSM) at the IBM T. J. Watson Research Center in Yorktown Heights, New York. He completed his undergraduate degree in Computer Science from the Indian Institute of Technology at Kanpur in 1993 and his Ph.D. from the Massachusetts Institute of Technology in 1996. He has worked extensively in the ﬁeld of data mining. He has published more than 350 papers in refereed conferences and journals and authored over 80 patents. He is the author or editor of 18 books, including textbooks on data mining, recommender systems, and outlier analysis. Because of the commercial value of his patents, he has thrice been designated a Master Inventor at IBM. He is a recipient of an IBM Corporate Award (2003) for his work on bioterrorist threat detection in data streams, a recipient of the IBM Outstanding Innovation Award (2008) for his scientiﬁc contributions to privacy technology, and a recipient of two IBM Outstanding Technical Achievement Awards (2009, 2015) for his work on data streams/highdimensional data. He received the EDBT 2014 Test of Time Award for his work on condensationbased privacypreserving data mining. He is also a recipient of the IEEE ICDM Research Contributions Award (2015), which is one of the two highest awards for inﬂuential research contributions in the ﬁeld of data mining. He has served as the general cochair of the IEEE Big Data Conference (2014) and as the program cochair of the ACM CIKM Conference (2015), the IEEE ICDM Conference (2015), and the ACM KDD Conference (2016). He served as an associate editor of the IEEE Transactions on Knowledge and Data Engineering from 2004 to 2008. He is an associate editor of the IEEE Transactions on Big Data, an action editor of the Data Mining and Knowledge Discovery Journal, and an associate editor of the Knowledge and Information Systems Journal. He serves as the editorinchief of the ACM Transactions on Knowledge Discovery from Data as well as the ACM SIGKDD Explorations. He serves on the advisory board of the Lecture Notes on Social Networks, a publication by Springer. He has served as the vicepresident of the SIAM Activity Group on Data Mining and is a member of the SIAM industry committee. He is a fellow of the SIAM, ACM, and the IEEE, for “contributions to knowledge discovery and data mining algorithms.” XXIII Chapter 1 An Introduction to Neural Networks “Thou shalt not make a machine to counterfeit a human mind.”—Frank Herbert 1.1 Introduction Artiﬁcial neural networks are popular machine learning techniques that simulate the mechanism of learning in biological organisms. The human nervous system contains cells, which are referred to as neurons. The neurons are connected to one another with the use of axons and dendrites, and the connecting regions between axons and dendrites are referred to as synapses. These connections are illustrated in Figure 1.1(a). The strengths of synaptic connections often change in response to external stimuli. This change is how learning takes place in living organisms. This biological mechanism is simulated in artiﬁcial neural networks, which contain computation units that are referred to as neurons. Throughout this book, we will use the term “neural networks” to refer to artiﬁcial neural networks rather than biological ones. The computational units are connected to one another through weights, which serve the same w1 w2 w3 NEURON AXON w4 w5 DENDRITES WITH SYNAPTIC WEIGHTS (a) Biological neural network (b) Artiﬁcial neural network Figure 1.1: The synaptic connections between neurons. The image in (a) is from “The Brain: c Understanding Neurobiology Through the Study of Addiction [598].” Copyright 2000 by BSCS & Videodiscovery. All rights reserved. Used with permission. © Springer International Publishing AG, part of Springer Nature 2018 C. C. Aggarwal, Neural Networks and Deep Learning, https://doi.org/10.1007/9783319944630 1 1 2 CHAPTER 1. AN INTRODUCTION TO NEURAL NETWORKS role as the strengths of synaptic connections in biological organisms. Each input to a neuron is scaled with a weight, which aﬀects the function computed at that unit. This architecture is illustrated in Figure 1.1(b). An artiﬁcial neural network computes a function of the inputs by propagating the computed values from the input neurons to the output neuron(s) and using the weights as intermediate parameters. Learning occurs by changing the weights connecting the neurons. Just as external stimuli are needed for learning in biological organisms, the external stimulus in artiﬁcial neural networks is provided by the training data containing examples of inputoutput pairs of the function to be learned. For example, the training data might contain pixel representations of images (input) and their annotated labels (e.g., carrot, banana) as the output. These training data pairs are fed into the neural network by using the input representations to make predictions about the output labels. The training data provides feedback to the correctness of the weights in the neural network depending on how well the predicted output (e.g., probability of carrot) for a particular input matches the annotated output label in the training data. One can view the errors made by the neural network in the computation of a function as a kind of unpleasant feedback in a biological organism, leading to an adjustment in the synaptic strengths. Similarly, the weights between neurons are adjusted in a neural network in response to prediction errors. The goal of changing the weights is to modify the computed function to make the predictions more correct in future iterations. Therefore, the weights are changed carefully in a mathematically justiﬁed way so as to reduce the error in computation on that example. By successively adjusting the weights between neurons over many inputoutput pairs, the function computed by the neural network is reﬁned over time so that it provides more accurate predictions. Therefore, if the neural network is trained with many diﬀerent images of bananas, it will eventually be able to properly recognize a banana in an image it has not seen before. This ability to accurately compute functions of unseen inputs by training over a ﬁnite set of inputoutput pairs is referred to as model generalization. The primary usefulness of all machine learning models is gained from their ability to generalize their learning from seen training data to unseen examples. The biological comparison is often criticized as a very poor caricature of the workings of the human brain; nevertheless, the principles of neuroscience have often been useful in designing neural network architectures. A diﬀerent view is that neural networks are built as higherlevel abstractions of the classical models that are commonly used in machine learning. In fact, the most basic units of computation in the neural network are inspired by traditional machine learning algorithms like leastsquares regression and logistic regression. Neural networks gain their power by putting together many such basic units, and learning the weights of the diﬀerent units jointly in order to minimize the prediction error. From this point of view, a neural network can be viewed as a computational graph of elementary units in which greater power is gained by connecting them in particular ways. When a neural network is used in its most basic form, without hooking together multiple units, the learning algorithms often reduce to classical machine learning models (see Chapter 2). The real power of a neural model over classical methods is unleashed when these elementary computational units are combined, and the weights of the elementary models are trained using their dependencies on one another. By combining multiple units, one is increasing the power of the model to learn more complicated functions of the data than are inherent in the elementary models of basic machine learning. The way in which these units are combined also plays a role in the power of the architecture, and requires some understanding and insight from the analyst. Furthermore, suﬃcient training data is also required in order to learn the larger number of weights in these expanded computational graphs. 1.1. INTRODUCTION 3 ACCURACY DEEP LEARNING CONVENTIONAL MACHINE LEARNING AMOUNT OF DATA Figure 1.2: An illustrative comparison of the accuracy of a typical machine learning algorithm with that of a large neural network. Deep learners become more attractive than conventional methods primarily when suﬃcient data/computational power is available. Recent years have seen an increase in data availability and computational power, which has led to a “Cambrian explosion” in deep learning technology. 1.1.1 Humans Versus Computers: Stretching the Limits of Artiﬁcial Intelligence Humans and computers are inherently suited to diﬀerent types of tasks. For example, computing the cube root of a large number is very easy for a computer, but it is extremely diﬃcult for humans. On the other hand, a task such as recognizing the objects in an image is a simple matter for a human, but has traditionally been very diﬃcult for an automated learning algorithm. It is only in recent years that deep learning has shown an accuracy on some of these tasks that exceeds that of a human. In fact, the recent results by deep learning algorithms that surpass human performance [184] in (some narrow tasks on) image recognition would not have been considered likely by most computer vision experts as recently as 10 years ago. Many deep learning architectures that have shown such extraordinary performance are not created by indiscriminately connecting computational units. The superior performance of deep neural networks mirrors the fact that biological neural networks gain much of their power from depth as well. Furthermore, biological networks are connected in ways we do not fully understand. In the few cases that the biological structure is understood at some level, signiﬁcant breakthroughs have been achieved by designing artiﬁcial neural networks along those lines. A classical example of this type of architecture is the use of the convolutional neural network for image recognition. This architecture was inspired by Hubel and Wiesel’s experiments [212] in 1959 on the organization of the neurons in the cat’s visual cortex. The precursor to the convolutional neural network was the neocognitron [127], which was directly based on these results. The human neuronal connection structure has evolved over millions of years to optimize survivaldriven performance; survival is closely related to our ability to merge sensation and intuition in a way that is currently not possible with machines. Biological neuroscience [232] is a ﬁeld that is still very much in its infancy, and only a limited amount is known about how the brain truly works. Therefore, it is fair to suggest that the biologically inspired success of convolutional neural networks might be replicated in other settings, as we learn more about how the human brain works [176]. A key advantage of neural networks over traditional machine learning is that the former provides a higherlevel abstraction of expressing semantic insights about data domains by architectural design choices in the computational graph. The second advantage is that neural networks provide a simple way to adjust the 4 CHAPTER 1. AN INTRODUCTION TO NEURAL NETWORKS complexity of a model by adding or removing neurons from the architecture according to the availability of training data or computational power. A large part of the recent success of neural networks is explained by the fact that the increased data availability and computational power of modern computers has outgrown the limits of traditional machine learning algorithms, which fail to take full advantage of what is now possible. This situation is illustrated in Figure 1.2. The performance of traditional machine learning remains better at times for smaller data sets because of more choices, greater ease of model interpretation, and the tendency to handcraft interpretable features that incorporate domainspeciﬁc insights. With limited data, the best of a very wide diversity of models in machine learning will usually perform better than a single class of models (like neural networks). This is one reason why the potential of neural networks was not realized in the early years. The “big data” era has been enabled by the advances in data collection technology; virtually everything we do today, including purchasing an item, using the phone, or clicking on a site, is collected and stored somewhere. Furthermore, the development of powerful Graphics Processor Units (GPUs) has enabled increasingly eﬃcient processing on such large data sets. These advances largely explain the recent success of deep learning using algorithms that are only slightly adjusted from the versions that were available two decades back. Furthermore, these recent adjustments to the algorithms have been enabled by increased speed of computation, because reduced runtimes enable eﬃcient testing (and subsequent algorithmic adjustment). If it requires a month to test an algorithm, at most twelve variations can be tested in an year on a single hardware platform. This situation has historically constrained the intensive experimentation required for tweaking neuralnetwork learning algorithms. The rapid advances associated with the three pillars of improved data, computation, and experimentation have resulted in an increasingly optimistic outlook about the future of deep learning. By the end of this century, it is expected that computers will have the power to train neural networks with as many neurons as the human brain. Although it is hard to predict what the true capabilities of artiﬁcial intelligence will be by then, our experience with computer vision should prepare us to expect the unexpected. Chapter Organization This chapter is organized as follows. The next section introduces singlelayer and multilayer networks. The diﬀerent types of activation functions, output nodes, and loss functions are discussed. The backpropagation algorithm is introduced in Section 1.3. Practical issues in neural network training are discussed in Section 1.4. Some key points on how neural networks gain their power with speciﬁc choices of activation functions are discussed in Section 1.5. The common architectures used in neural network design are discussed in Section 1.6. Advanced topics in deep learning are discussed in Section 1.7. Some notable benchmarks used by the deep learning community are discussed in Section 1.8. A summary is provided in Section 1.9. 1.2 The Basic Architecture of Neural Networks In this section, we will introduce singlelayer and multilayer neural networks. In the singlelayer network, a set of inputs is directly mapped to an output by using a generalized variation of a linear function. This simple instantiation of a neural network is also referred to as the perceptron. In multilayer neural networks, the neurons are arranged in layered fashion, in which the input and output layers are separated by a group of hidden layers. This layerwise architecture of the neural network is also referred to as a feedforward network. This section will discuss both singlelayer and multilayer networks. 1.2. THE BASIC ARCHITECTURE OF NEURAL NETWORKS INPUT NODES INPUT NODES x1 x2 x3 x4 5 x1 w1 w2 w3 w4 ∑ w5 x5 w1 w2 x2 OUTPUT NODE y x3 w3 x4 w5 ∑ w4 x5 (a) Perceptron without bias OUTPUT NODE y b +1 BIAS NEURON (b) Perceptron with bias Figure 1.3: The basic architecture of the perceptron 1.2.1 Single Computational Layer: The Perceptron The simplest neural network is referred to as the perceptron. This neural network contains a single input layer and an output node. The basic architecture of the perceptron is shown in Figure 1.3(a). Consider a situation where each training instance is of the form (X, y), where each X = [x1 , . . . xd ] contains d feature variables, and y ∈ {−1, +1} contains the observed value of the binary class variable. By “observed value” we refer to the fact that it is given to us as a part of the training data, and our goal is to predict the class variable for cases in which it is not observed. For example, in a creditcard fraud detection application, the features might represent various properties of a set of credit card transactions (e.g., amount and frequency of transactions), and the class variable might represent whether or not this set of transactions is fraudulent. Clearly, in this type of application, one would have historical cases in which the class variable is observed, and other (current) cases in which the class variable has not yet been observed but needs to be predicted. The input layer contains d nodes that transmit the d features X = [x1 . . . xd ] with edges of weight W = [w1 . . . wd ] to an output node. The input layer does not perform d any computation in its own right. The linear function W · X = i=1 wi xi is computed at the output node. Subsequently, the sign of this real value is used in order to predict the dependent variable of X. Therefore, the prediction ŷ is computed as follows: ŷ = sign{W · X} = sign{ d wj x j } (1.1) j=1 The sign function maps a real value to either +1 or −1, which is appropriate for binary classiﬁcation. Note the circumﬂex on top of the variable y to indicate that it is a predicted value rather than an observed value. The error of the prediction is therefore E(X) = y − ŷ, which is one of the values drawn from the set {−2, 0, +2}. In cases where the error value E(X) is nonzero, the weights in the neural network need to be updated in the (negative) direction of the error gradient. As we will see later, this process is similar to that used in various types of linear models in machine learning. In spite of the similarity of the perceptron with respect to traditional machine learning models, its interpretation as a computational unit is very useful because it allows us to put together multiple units in order to create far more powerful models than are available in traditional machine learning. 6 CHAPTER 1. AN INTRODUCTION TO NEURAL NETWORKS The architecture of the perceptron is shown in Figure 1.3(a), in which a single input layer transmits the features to the output node. The edges from the input to the output contain the weights w1 . . . wd with which the features are multiplied and added at the output node. Subsequently, the sign function is applied in order to convert the aggregated value into a class label. The sign function serves the role of an activation function. Diﬀerent choices of activation functions can be used to simulate diﬀerent types of models used in machine learning, like leastsquares regression with numeric targets, the support vector machine, or a logistic regression classiﬁer. Most of the basic machine learning models can be easily represented as simple neural network architectures. It is a useful exercise to model traditional machine learning techniques as neural architectures, because it provides a clearer picture of how deep learning generalizes traditional machine learning. This point of view is explored in detail in Chapter 2. It is noteworthy that the perceptron contains two layers, although the input layer does not perform any computation and only transmits the feature values. The input layer is not included in the count of the number of layers in a neural network. Since the perceptron contains a single computational layer, it is considered a singlelayer network. In many settings, there is an invariant part of the prediction, which is referred to as the bias. For example, consider a setting in which the feature variables are mean centered, but the mean of the binary class prediction from {−1, +1} is not 0. This will tend to occur in situations in which the binary class distribution is highly imbalanced. In such a case, the aforementioned approach is not suﬃcient for prediction. We need to incorporate an additional bias variable b that captures this invariant part of the prediction: ŷ = sign{W · X + b} = sign{ d wj xj + b} (1.2) j=1 The bias can be incorporated as the weight of an edge by using a bias neuron. This is achieved by adding a neuron that always transmits a value of 1 to the output node. The weight of the edge connecting the bias neuron to the output node provides the bias variable. An example of a bias neuron is shown in Figure 1.3(b). Another approach that works well with singlelayer architectures is to use a feature engineering trick in which an additional feature is created with a constant value of 1. The coeﬃcient of this feature provides the bias, and one can then work with Equation 1.1. Throughout this book, biases will not be explicitly used (for simplicity in architectural representations) because they can be incorporated with bias neurons. The details of the training algorithms remain the same by simply treating the bias neurons like any other neuron with a ﬁxed activation value of 1. Therefore, the following will work with the predictive assumption of Equation 1.1, which does not explicitly uses biases. At the time that the perceptron algorithm was proposed by Rosenblatt [405], these optimizations were performed in a heuristic way with actual hardware circuits, and it was not presented in terms of a formal notion of optimization in machine learning (as is common today). However, the goal was always to minimize the error in prediction, even if a formal optimization formulation was not presented. The perceptron algorithm was, therefore, heuristically designed to minimize the number of misclassiﬁcations, and convergence proofs were available that provided correctness guarantees of the learning algorithm in simpliﬁed settings. Therefore, we can still write the (heuristically motivated) goal of the perceptron algorithm in leastsquares form with respect to all training instances in a data set D con 1.2. THE BASIC ARCHITECTURE OF NEURAL NETWORKS 7 taining featurelabel pairs: Minimize W L = (X,y)∈D (y − ŷ)2 = 2 y − sign{W · X} (X,y)∈D This type of minimization objective function is also referred to as a loss function. As we will see later, almost all neural network learning algorithms are formulated with the use of a loss function. As we will learn in Chapter 2, this loss function looks a lot like leastsquares regression. However, the latter is deﬁned for continuousvalued target variables, and the corresponding loss is a smooth and continuous function of the variables. On the other hand, for the leastsquares form of the objective function, the sign function is nondiﬀerentiable, with steplike jumps at speciﬁc points. Furthermore, the sign function takes on constant values over large portions of the domain, and therefore the exact gradient takes on zero values at diﬀerentiable points. This results in a staircaselike loss surface, which is not suitable for gradientdescent. The perceptron algorithm (implicitly) uses a smooth approximation of the gradient of this objective function with respect to each example: (y − ŷ)X (1.3) ∇Lsmooth = (X,y)∈D Note that the above gradient is not a true gradient of the staircaselike surface of the (heuristic) objective function, which does not provide useful gradients. Therefore, the staircase is smoothed out into a sloping surface deﬁned by the perceptron criterion. The properties of the perceptron criterion will be described in Section 1.2.1.1. It is noteworthy that concepts like the “perceptron criterion” were proposed later than the original paper by Rosenblatt [405] in order to explain the heuristic gradientdescent steps. For now, we will assume that the perceptron algorithm optimizes some unknown smooth function with the use of gradient descent. Although the above objective function is deﬁned over the entire training data, the training algorithm of neural networks works by feeding each input data instance X into the network one by one (or in small batches) to create the prediction ŷ. The weights are then updated, based on the error value E(X) = (y − ŷ). Speciﬁcally, when the data point X is fed into the network, the weight vector W is updated as follows: W ⇐ W + α(y − ŷ)X (1.4) The parameter α regulates the learning rate of the neural network. The perceptron algorithm repeatedly cycles through all the training examples in random order and iteratively adjusts the weights until convergence is reached. A single training data point may be cycled through many times. Each such cycle is referred to as an epoch. One can also write the gradientdescent update in terms of the error E(X) = (y − ŷ) as follows: W ⇐ W + αE(X)X (1.5) The basic perceptron algorithm can be considered a stochastic gradientdescent method, which implicitly minimizes the squared error of prediction by performing gradientdescent updates with respect to randomly chosen training points. The assumption is that the neural network cycles through the points in random order during training and changes the weights with the goal of reducing the prediction error on that point. It is easy to see from Equation 1.5 that nonzero updates are made to the weights only when y = ŷ, which occurs only CHAPTER 1. AN INTRODUCTION TO NEURAL NETWORKS 8 when errors are made in prediction. In minibatch stochastic gradient descent, the aforementioned updates of Equation 1.5 are implemented over a randomly chosen subset of training points S: W ⇐W +α E(X)X (1.6) X∈S W X=0 LINEARLY SEPARABLE NOT LINEARLY SEPARABLE Figure 1.4: Examples of linearly separable and inseparable data in two classes The advantages of using minibatch stochastic gradient descent are discussed in Section 3.2.8 of Chapter 3. An interesting quirk of the perceptron is that it is possible to set the learning rate α to 1, because the learning rate only scales the weights. The type of model proposed in the perceptron is a linear model, in which the equation W · X = 0 deﬁnes a linear hyperplane. Here, W = (w1 . . . wd ) is a ddimensional vector that is normal to the hyperplane. Furthermore, the value of W · X is positive for values of X on one side of the hyperplane, and it is negative for values of X on the other side. This type of model performs particularly well when the data is linearly separable. Examples of linearly separable and inseparable data are shown in Figure 1.4. The perceptron algorithm is good at classifying data sets like the one shown on the lefthand side of Figure 1.4, when the data is linearly separable. On the other hand, it tends to perform poorly on data sets like the one shown on the righthand side of Figure 1.4. This example shows the inherent modeling limitation of a perceptron, which necessitates the use of more complex neural architectures. Since the original perceptron algorithm was proposed as a heuristic minimization of classiﬁcation errors, it was particularly important to show that the algorithm converges to reasonable solutions in some special cases. In this context, it was shown [405] that the perceptron algorithm always converges to provide zero error on the training data when the data are linearly separable. However, the perceptron algorithm is not guaranteed to converge in instances where the data are not linearly separable. For reasons discussed in the next section, the perceptron might sometimes arrive at a very poor solution with data that are not linearly separable (in comparison with many other learning algorithms). 1.2.1.1 What Objective Function Is the Perceptron Optimizing? As discussed earlier in this chapter, the original perceptron paper by Rosenblatt [405] did not formally propose a loss function. In those years, these implementations were achieved using actual hardware circuits. The original Mark I perceptron was intended to be a machine rather than an algorithm, and custombuilt hardware was used to create it (cf. Figure 1.5). 1.2. THE BASIC ARCHITECTURE OF NEURAL NETWORKS 9 The general goal was to minimize the number of classiﬁcation errors with a heuristic update process (in hardware) that changed weights in the “correct” direction whenever errors were made. This heuristic update strongly resembled gradient descent but it was not derived as a gradientdescent method. Gradient descent is deﬁned only for smooth loss functions in algorithmic settings, whereas the hardwarecentric approach was designed in a more Figure 1.5: The perceptron algorithm was originally implemented using hardware circuits. The image depicts the Mark I perceptron machine built in 1958. (Courtesy: Smithsonian Institute) heuristic way with binary outputs. Many of the binary and circuitcentric principles were inherited from the McCullochPitts model [321] of the neuron. Unfortunately, binary signals are not prone to continuous optimization. Can we ﬁnd a smooth loss function, whose gradient turns out to be the perceptron update? The number of classiﬁcation errors in a binary classiﬁcation problem can be written in the form of a 0/1 loss function for training data point (Xi , yi ) as follows: (0/1) Li = 1 (yi − sign{W · Xi })2 = 1 − yi · sign{W · Xi } 2 (1.7) The simpliﬁcation to the righthand side of the above objective function is obtained by setting both yi2 and sign{W ·Xi }2 to 1, since they are obtained by squaring a value drawn from {−1, +1}. However, this objective function is not diﬀerentiable, because it has a staircaselike shape, especially when it is added over multiple points. Note that the 0/1 loss above is dominated by the term −yi sign{W · Xi }, in which the sign function causes most of the problems associated with nondiﬀerentiability. Since neural networks are deﬁned by gradientbased optimization, we need to deﬁne a smooth objective function that is responsible for the perceptron updates. It can be shown [41] that the updates of the perceptron implicitly optimize the perceptron criterion. This objective function is deﬁned by dropping the sign function in the above 0/1 loss and setting negative values to 0 in order to treat all correct predictions in a uniform and lossless way: Li = max{−yi (W · Xi ), 0} (1.8) The reader is encouraged to use calculus to verify that the gradient of this smoothed objective function leads to the perceptron update, and the update of the perceptron is essentially 10 CHAPTER 1. AN INTRODUCTION TO NEURAL NETWORKS W ⇐ W − α∇W Li . The modiﬁed loss function to enable gradient computation of a nondiﬀerentiable function is also referred to as a smoothed surrogate loss function. Almost all continuous optimizationbased learning methods (such as neural networks) with discrete outputs (such as class labels) use some type of smoothed surrogate loss function. HINGE LOSS LOSS PERCEPTRON CRITERION 0 1 VALUE OF W X FOR POSITIVE CLASS INSTANCE Figure 1.6: Perceptron criterion versus hinge loss Although the aforementioned perceptron criterion was reverse engineered by working backwards from the perceptron updates, the nature of this loss function exposes some of the weaknesses of the updates in the original algorithm. An interesting observation about the perceptron criterion is that one can set W to the zero vector irrespective of the training data set in order to obtain the optimal loss value of 0. In spite of this fact, the perceptron updates continue to converge to a clear separator between the two classes in linearly separable cases; after all, a separator between the two classes provides a loss value of 0 as well. However, the behavior for data that are not linearly separable is rather arbitrary, and the resulting solution is sometimes not even a good approximate separator of the classes. The direct sensitivity of the loss to the magnitude of the weight vector can dilute the goal of class separation; it is possible for updates to worsen the number of misclassiﬁcations signiﬁcantly while improving the loss. This is an example of how surrogate loss functions might sometimes not fully achieve their intended goals. Because of this fact, the approach is not stable and can yield solutions of widely varying quality. Several variations of the learning algorithm were therefore proposed for inseparable data, and a natural approach is to always keep track of the best solution in terms of the number of misclassiﬁcations [128]. This approach of always keeping the best solution in one’s “pocket” is referred to as the pocket algorithm. Another highly performing variant incorporates the notion of margin in the loss function, which creates an identical algorithm to the linear support vector machine. For this reason, the linear support vector machine is also referred to as the perceptron of optimal stability. 1.2.1.2 Relationship with Support Vector Machines The perceptron criterion is a shifted version of the hingeloss used in support vector machines (see Chapter 2). The hinge loss looks even more similar to the zeroone loss criterion of Equation 1.7, and is deﬁned as follows: = max{1 − yi (W · Xi ), 0} Lsvm i (1.9) Note that the perceptron does not keep the constant term of 1 on the righthand side of Equation 1.7, whereas the hinge loss keeps this constant within the maximization function. This change does not aﬀect the algebraic expression for the gradient, but it does change 1.2. THE BASIC ARCHITECTURE OF NEURAL NETWORKS 11 which points are lossless and should not cause an update. The relationship between the perceptron criterion and the hinge loss is shown in Figure 1.6. This similarity becomes particularly evident when the perceptron updates of Equation 1.6 are rewritten as follows: W ⇐W +α yX (1.10) (X,y)∈S + Here, S + is deﬁned as the set of all misclassiﬁed training points X ∈ S that satisfy the condition y(W · X) < 0. This update seems to look somewhat diﬀerent from the perceptron, because the perceptron uses the error E(X) for the update, which is replaced with y in the update above. A key point is that the (integer) error value E(X) = (y − sign{W · X}) ∈ {−2, +2} can never be 0 for misclassiﬁed points in S + . Therefore, we have E(X) = 2y for misclassiﬁed points, and E(X) can be replaced with y in the updates after absorbing the factor of 2 within the learning rate. This update is identical to that used by the primal support vector machine (SVM) algorithm [448], except that the updates are performed only for the misclassiﬁed points in the perceptron, whereas the SVM also uses the marginally correct points near the decision boundary for updates. Note that the SVM uses the condition y(W · X) < 1 [instead of using the condition y(W · X) < 0] to deﬁne S + , which is one of the key diﬀerences between the two algorithms. This point shows that the perceptron is fundamentally not very diﬀerent from wellknown machine learning algorithms like the support vector machine in spite of its diﬀerent origins. Freund and Schapire provide a beautiful exposition of the role of margin in improving stability of the perceptron and also its relationship with the support vector machine [123]. It turns out that many traditional machine learning models can be viewed as minor variations of shallow neural architectures like the perceptron. The relationships between classical machine learning models and shallow neural networks are described in detail in Chapter 2. 1.2.1.3 Choice of Activation and Loss Functions The choice of activation function is a critical part of neural network design. In the case of the perceptron, the choice of the sign activation function is motivated by the fact that a binary class label needs to be predicted. However, it is possible to have other types of situations where diﬀerent target variables may be predicted. For example, if the target variable to be predicted is real, then it makes sense to use the identity activation function, and the resulting algorithm is the same as leastsquares regression. If it is desirable to predict a probability of a binary class, it makes sense to use a sigmoid function for activating the output node, so that the prediction ŷ indicates the probability that the observed value, y, of the dependent variable is 1. The negative logarithm of y/2 − 0.5 + ŷ is used as the loss, assuming that y is coded from {−1, 1}. If ŷ is the probability that y is 1, then y/2 − 0.5 + ŷ is the probability that the correct value is predicted. This assertion is easy to verify by examining the two cases where y is 0 or 1. This loss function can be shown to be representative of the negative loglikelihood of the training data (see Section 2.2.3 of Chapter 2). The importance of nonlinear activation functions becomes signiﬁcant when one moves from the singlelayered perceptron to the multilayered architectures discussed later in this chapter. Diﬀerent types of nonlinear functions such as the sign, sigmoid, or hyperbolic tangents may be used in various layers. We use the notation Φ to denote the activation function: ŷ = Φ(W · X) (1.11) Therefore, a neuron really computes two functions within the node, which is why we have incorporated the summation symbol Σ as well as the activation symbol Φ within a neuron. The breakup of the neuron computations into two separate values is shown in Figure 1.7. CHAPTER 1. AN INTRODUCTION TO NEURAL NETWORKS 12 X { W ∑ h= (W. X) BREAK UP X { W ∑ ah = W .X ∑ h= (ah) POSTACTIVATION VALUE PREACTIVATION VALUE Figure 1.7: Preactivation and postactivation values within a neuron The value computed before applying the activation function Φ(·) will be referred to as the preactivation value, whereas the value computed after applying the activation function is referred to as the postactivation value. The output of a neuron is always the postactivation value, although the preactivation variables are often used in diﬀerent types of analyses, such as the computations of the backpropagation algorithm discussed later in this chapter. The preactivation and postactivation values of a neuron are shown in Figure 1.7. The most basic activation function Φ(·) is the identity or linear activation, which provides no nonlinearity: Φ(v) = v The linear activation function is often used in the output node, when the target is a real value. It is even used for discrete outputs when a smoothed surrogate loss function needs to be set up. The classical activation functions that were used early in the development of neural networks were the sign, sigmoid, and the hyperbolic tangent functions: Φ(v) = sign(v) (sign function) 1 (sigmoid function) Φ(v) = 1 + e−v e2v − 1 Φ(v) = 2v (tanh function) e +1 While the sign activation can be used to map to binary outputs at prediction time, its nondiﬀerentiability prevents its use for creating the loss function at training time. For example, while the perceptron uses the sign function for prediction, the perceptron criterion in training only requires linear activation. The sigmoid activation outputs a value in (0, 1), which is helpful in performing computations that should be interpreted as probabilities. Furthermore, it is also helpful in creating probabilistic outputs and constructing loss functions derived from maximumlikelihood models. The tanh function has a shape similar to that of the sigmoid function, except that it is horizontally rescaled and vertically translated/rescaled to [−1, 1]. The tanh and sigmoid functions are related as follows (see Exercise 3): tanh(v) = 2 · sigmoid(2v) − 1 The tanh function is preferable to the sigmoid when the outputs of the computations are desired to be both positive and negative. Furthermore, its meancentering and larger gradient 1.2. THE BASIC ARCHITECTURE OF NEURAL NETWORKS 13 2 1.5 1 1 1 0.8 0.8 0.6 0.6 0.4 0.4 0.2 0.2 0.5 0 0 0 −0.2 −0.2 −0.4 −0.4 −0.6 −0.6 −0.8 −0.8 −0.5 −1 −1.5 −1 −2 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2 −2 −1 −1.5 −1 −0.5 0 0.5 1 1.5 2 −10 1 1 1 0.8 0.8 0.8 0.6 0.6 0.6 0.4 0.4 0.4 0.2 0.2 0.2 0 0 0 −0.2 −0.2 −0.2 −0.4 −0.4 −0.4 −0.6 −0.6 −0.6 −0.8 −0.8 −0.8 −1 −1 −6 −4 −2 0 2 4 6 −2 −5 0 5 10 −1 −1.5 −1 −0.5 0 0.5 1 1.5 2 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2 Figure 1.8: Various activation functions (because of stretching) with respect to sigmoid makes it easier to train. The sigmoid and the tanh functions have been the historical tools of choice for incorporating nonlinearity in the neural network. In recent years, however, a number of piecewise linear activation functions have become more popular: Φ(v) = max{v, 0} (Rectiﬁed Linear Unit [ReLU]) Φ(v) = max {min [v, 1] , −1} (hard tanh) The ReLU and hard tanh activation functions have largely replaced the sigmoid and soft tanh activation functions in modern neural networks because of the ease in training multilayered neural networks with these activation functions. Pictorial representations of all the aforementioned activation functions are illustrated in Figure 1.8. It is noteworthy that all activation functions shown here are monotonic. Furthermore, other than the identity activation function, most1 of the other activation functions saturate at large absolute values of the argument at which increasing further does not change the activation much. As we will see later, such nonlinear activation functions are also very useful in multilayer networks, because they help in creating more powerful compositions of diﬀerent types of functions. Many of these functions are referred to as squashing functions, as they map the outputs from an arbitrary range to bounded outputs. The use of a nonlinear activation plays a fundamental role in increasing the modeling power of a network. If a network used only linear activations, it would not provide better modeling power than a singlelayer linear network. This issue is discussed in Section 1.5. 1 The ReLU shows asymmetric saturation. CHAPTER 1. AN INTRODUCTION TO NEURAL NETWORKS 14 x1 OUTPUTS x2 P(y=blue) v1 x3 P(y=green) v2 P(y=red) x4 v3 HIDDEN LAYER x5 SOFTMAX LAYER INPUT LAYER Figure 1.9: An example of multiple outputs for categorical classiﬁcation with the use of a softmax layer 1.2.1.4 Choice and Number of Output Nodes The choice and number of output nodes is also tied to the activation function, which in turn depends on the application at hand. For example, if kway classiﬁcation is intended, k output values can be used, with a softmax activation function with respect to outputs v = [v1 , . . . , vk ] at the nodes in a given layer. Speciﬁcally, the activation function for the ith output is deﬁned as follows: exp(vi ) Φ(v)i = k j=1 exp(vj ) ∀i ∈ {1, . . . , k} (1.12) It is helpful to think of these k values as the values output by k nodes, in which the inputs are v1 . . . vk . An example of the softmax function with three outputs is illustrated in Figure 1.9, and the values v1 , v2 , and v3 are also shown in the same ﬁgure. Note that the three outputs correspond to the probabilities of the three classes, and they convert the three outputs of the ﬁnal hidden layer into probabilities with the softmax function. The ﬁnal hidden layer often uses linear (identity) activations, when it is input into the softmax layer. Furthermore, there are no weights associated with the softmax layer, since it is only converting realvalued outputs into probabilities. The use of softmax with a single hidden layer of linear activations exactly implements a model, which is referred to as multinomial logistic regression [6]. Similarly, many variations like multiclass SVMs can be easily implemented with neural networks. Another example of a case in which multiple output nodes are used is the autoencoder, in which each input data point is fully reconstructed by the output layer. The autoencoder can be used to implement matrix factorization methods like singular value decomposition. This architecture will be discussed in detail in Chapter 2. The simplest neural networks that simulate basic machine learning algorithms are instructive because they lie on the continuum between traditional machine learning and deep networks. By exploring these architectures, one gets a better idea of the relationship between traditional machine learning and neural networks, and also the advantages provided by the latter. 1.2.1.5 Choice of Loss Function The choice of the loss function is critical in deﬁning the outputs in a way that is sensitive to the application at hand. For example, leastsquares regression with numeric outputs 1.2. THE BASIC ARCHITECTURE OF NEURAL NETWORKS 15 requires a simple squared loss of the form (y − ŷ)2 for a single training instance with target y and prediction ŷ. One can also use other types of loss like hinge loss for y ∈ {−1, +1} and realvalued prediction ŷ (with identity activation): L = max{0, 1 − y · ŷ} (1.13) The hinge loss can be used to implement a learning method, which is referred to as a support vector machine. For multiway predictions (like predicting word identiﬁers or one of multiple classes), the softmax output is particularly useful. However, a softmax output is probabilistic, and therefore it requires a diﬀerent type of loss function. In fact, for probabilistic predictions, two diﬀerent types of loss functions are used, depending on whether the prediction is binary or whether it is multiway: 1. Binary targets (logistic regression): In this case, it is assumed that the observed value y is drawn from {−1, +1}, and the prediction ŷ is a an arbitrary numerical value on using the identity activation function. In such a case, the loss function for a single instance with observed value y and realvalued prediction ŷ (with identity activation) is deﬁned as follows: L = log(1 + exp(−y · ŷ)) (1.14) This type of loss function implements a fundamental machine learning method, referred to as logistic regression. Alternatively, one can use a sigmoid activation function to output ŷ ∈ (0, 1), which indicates the probability that the observed value y is 1. Then, the negative logarithm of y/2 − 0.5 + ŷ provides the loss, assuming that y is coded from {−1, 1}. This is because y/2 − 0.5 + ŷ indicates the probability that the prediction is correct. This observation illustrates that one can use various combinations of activation and loss functions to achieve the same result. 2. Categorical targets: In this case, if ŷ1 . . . ŷk are the probabilities of the k classes (using the softmax activation of Equation 1.9), and the rth class is the groundtruth class, then the loss function for a single instance is deﬁned as follows: L = −log(ŷr ) (1.15) This type of loss function implements multinomial logistic regression, and it is referred to as the crossentropy loss. Note that binary logistic regression is identical to multinomial logistic regression, when the value of k is set to 2 in the latter. The key point to remember is that the nature of the output nodes, the activation function, and the loss function depend on the application at hand. Furthermore, these choices also depend on one another. Even though the perceptron is often presented as the quintessential representative of singlelayer networks, it is only a single representative out of a very large universe of possibilities. In practice, one rarely uses the perceptron criterion as the loss function. For discretevalued outputs, it is common to use softmax activation with crossentropy loss. For realvalued outputs, it is common to use linear activation with squared loss. Generally, crossentropy loss is easier to optimize than squared loss. CHAPTER 1. AN INTRODUCTION TO NEURAL NETWORKS 16 2 1.5 1 1 1 0.8 0.8 0.6 0.6 0.4 0.4 0.2 0.2 0.5 0 0 0 −0.2 −0.2 −0.4 −0.4 −0.6 −0.6 −0.8 −0.8 −0.5 −1 −1.5 −1 −2 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2 −2 −1 −1.5 −1 −0.5 0 0.5 1 1.5 2 −10 1 1 1 0.8 0.8 0.8 0.6 0.6 0.6 0.4 0.4 0.4 0.2 0.2 0.2 0 0 0 −0.2 −0.2 −0.2 −0.4 −0.4 −0.4 −0.6 −0.6 −0.6 −0.8 −0.8 −0.8 −1 −1 −6 −4 −2 0 2 4 6 −2 −5 0 5 10 −1 −1.5 −1 −0.5 0 0.5 1 1.5 2 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2 Figure 1.10: The derivatives of various activation functions 1.2.1.6 Some Useful Derivatives of Activation Functions Most neural network learning is primarily related to gradientdescent with activation functions. For this reason, the derivatives of these activation functions are used repeatedly in this book, and gathering them in a single place for future reference is useful. This section provides details on the derivatives of these loss functions. Later chapters will extensively refer to these results. 1. Linear and sign activations: The derivative of the linear activation function is 1 at all places. The derivative of sign(v) is 0 at all values of v other than at v = 0, where it is discontinuous and nondiﬀerentiable. Because of the zero gradient and nondiﬀerentiability of this activation function, it is rarely used in the loss function even when it is used for prediction at testing time. The derivatives of the linear and sign activations are illustrated in Figure 1.10(a) and (b), respectively. 2. Sigmoid activation: The derivative of sigmoid activation is particularly simple, when it is expressed in terms of the output of the sigmoid, rather than the input. Let o be the output of the sigmoid function with argument v: o= 1 1 + exp(−v) (1.16) Then, one can write the derivative of the activation as follows: exp(−v) ∂o = ∂v (1 + exp(−v))2 (1.17) 1.2. THE BASIC ARCHITECTURE OF NEURAL NETWORKS 17 The key point is that this sigmoid can be written more conveniently in terms of the outputs: ∂o = o(1 − o) (1.18) ∂v The derivative of the sigmoid is often used as a function of the output rather than the input. The derivative of the sigmoid activation function is illustrated in Figure 1.10(c). 3. Tanh activation: As in the case of the sigmoid activation, the tanh activation is often used as a function of the output o rather than the input v: o= exp(2v) − 1 exp(2v) + 1 (1.19) One can then compute the gradient as follows: ∂o 4 · exp(2v) = ∂v (exp(2v) + 1)2 (1.20) One can also write this derivative in terms of the output o: ∂o = 1 − o2 ∂v (1.21) The derivative of the tanh activation is illustrated in Figure 1.10(d). 4. ReLU and hard tanh activations: The ReLU takes on a partial derivative value of 1 for nonnegative values of its argument, and 0, otherwise. The hard tanh function takes on a partial derivative value of 1 for values of the argument in [−1, +1] and 0, otherwise. The derivatives of the ReLU and hard tanh activations are illustrated in Figure 1.10(e) and (f), respectively. 1.2.2 Multilayer Neural Networks Multilayer neural networks contain more than one computational layer. The perceptron contains an input and output layer, of which the output layer is the only computationperforming layer. The input layer transmits the data to the output layer, and all computations are completely visible to the user. Multilayer neural networks contain multiple computational layers; the additional intermediate layers (between input and output) are referred to as hidden layers because the computations performed are not visible to the user. The speciﬁc architecture of multilayer neural networks is referred to as feedforward networks, because successive layers feed into one another in the forward direction from input to output. The default architecture of feedforward networks assumes that all nodes in one layer are connected to those of the next layer. Therefore, the architecture of the neural network is almost fully deﬁned, once the number of layers and the number/type of nodes in each layer have been deﬁned. The only remaining detail is the loss function that is optimized in the output layer. Although the perceptron algorithm uses the perceptron criterion, this is not the only choice. It is extremely common to use softmax outputs with crossentropy loss for discrete prediction and linear outputs with squared loss for realvalued prediction. As in the case of singlelayer networks, bias neurons can be used both in the hidden layers and in the output layers. Examples of multilayer networks with or without the bias neurons are shown in Figure 1.11(a) and (b), respectively. In each case, the neural network CHAPTER 1. AN INTRODUCTION TO NEURAL NETWORKS 18 contains three layers. Note that the input layer is often not counted, because it simply transmits the data and no computation is performed in that layer. If a neural network contains p1 . . . pk units in each of its k layers, then the (column) vector representations of these outputs, denoted by h1 . . . hk have dimensionalities p1 . . . pk . Therefore, the number of units in each layer is referred to as the dimensionality of that layer. INPUT LAYER INPUT LAYER x1 x1 HIDDEN LAYER HIDDEN LAYER x2 x2 OUTPUT LAYER x3 y OUTPUT LAYER x3 x4 x4 x5 x5 y BIAS +1 (a) No bias neurons X x1 +1 NEURON BIAS NEURONS +1 (b) With bias neurons SCALAR WEIGHTS ON CONNECTIONS WEIGHT MATRICES ON CONNECTIONS h1 h2 x2 h11 h21 x3 h12 h22 x4 h13 h23 y X X 5X3 MATRIX h1 3X3 MATRIX 3X1 h2 MATRIX y x5 Figure 1.11: The basic architecture of a feedforward network with two hidden layers and a single output layer. Even though each unit contains a single scalar variable, one often represents all units within a single layer as a single vector unit. Vector units are often represented as rectangles and have connection matrices between them. INPUT LAYER OUTPUT LAYER x1 xI1 HIDDEN LAYER x2 xI2 x3 xI3 x4 xI4 x5 OUTPUT OF THIS LAYER PROVIDES REDUCED REPRESENTATION xI5 Figure 1.12: An example of an autoencoder with multiple outputs 1.2. THE BASIC ARCHITECTURE OF NEURAL NETWORKS 19 The weights of the connections between the input layer and the ﬁrst hidden layer are contained in a matrix W1 with size d × p1 , whereas the weights between the rth hidden layer and the (r + 1)th hidden layer are denoted by the pr × pr+1 matrix denoted by Wr . If the output layer contains o nodes, then the ﬁnal matrix Wk+1 is of size pk × o. The ddimensional input vector x is transformed into the outputs using the following recursive equations: h1 = Φ(W1T x) T hp+1 = Φ(Wp+1 hp ) T o = Φ(Wk+1 hk ) [Input to Hidden Layer] ∀p ∈ {1 . . . k − 1} [Hidden to Hidden Layer] [Hidden to Output Layer] Here, the activation functions like the sigmoid function are applied in elementwise fashion to their vector arguments. However, some activation functions such as the softmax (which are typically used in the output layers) naturally have vector arguments. Even though each unit of a neural network contains a single variable, many architectural diagrams combine the units in a single layer to create a single vector unit, which is represented as a rectangle rather than a circle. For example, the architectural diagram in Figure 1.11(c) (with scalar units) has been transformed to a vectorbased neural architecture in Figure 1.11(d). Note that the connections between the vector units are now matrices. Furthermore, an implicit assumption in the vectorbased neural architecture is that all units in a layer use the same activation function, which is applied in elementwise fashion to that layer. This constraint is usually not a problem, because most neural architectures use the same activation function throughout the computational pipeline, with the only deviation caused by the nature of the output layer. Throughout this book, neural architectures in which units contain vector variables will be depicted with rectangular units, whereas scalar variables will correspond to circular units. Note that the aforementioned recurrence equations and vector architectures are valid only for layerwise feedforward networks, and cannot always be used for unconventional architectural designs. It is possible to have all types of unconventional designs in which inputs might be incorporated in intermediate layers, or the topology might allow connections between nonconsecutive layers. Furthermore, the functions computed at a node may not always be in the form of a combination of a linear function and an activation. It is possible to have all types of arbitrary computational functions at nodes. Although a very classical type of architecture is shown in Figure 1.11, it is possible to vary on it in many ways, such as allowing multiple output nodes. These choices are often determined by the goals of the application at hand (e.g., classiﬁcation or dimensionality reduction). A classical example of the dimensionality reduction setting is the autoencoder, which recreates the outputs from the inputs. Therefore, the number of outputs and inputs is equal, as shown in Figure 1.12. The constricted hidden layer in the middle outputs the reduced representation of each instance. As a result of this constriction, there is some loss in the representation, which typically corresponds to the noise in the data. The outputs of the hidden layers correspond to the reduced representation of the data. In fact, a shallow variant of this scheme can be shown to be mathematically equivalent to a wellknown dimensionality reduction method known as singular value decomposition. As we will learn in Chapter 2, increasing the depth of the network results in inherently more powerful reductions. Although a fully connected architecture is able to perform well in many settings, better performance is often achieved by pruning many of the connections or sharing them in an insightful way. Typically, these insights are obtained by using a domainspeciﬁc understanding of the data. A classical example of this type of weight pruning and sharing is that of CHAPTER 1. AN INTRODUCTION TO NEURAL NETWORKS 20 the convolutional neural network architecture (cf. Chapter 8), in which the architecture is carefully designed in order to conform to the typical properties of image data. Such an approach minimizes the risk of overﬁtting by incorporating domainspeciﬁc insights (or bias). As we will discuss later in this book (cf. Chapter 4), overﬁtting is a pervasive problem in neural network design, so that the network often performs very well on the training data, but it generalizes poorly to unseen test data. This problem occurs when the number of free parameters, (which is typically equal to the number of weight connections), is too large compared to the size of the training data. In such cases, the large number of parameters memorize the speciﬁc nuances of the training data, but fail to recognize the statistically signiﬁcant patterns for classifying unseen test data. Clearly, increasing the number of nodes in the neural network tends to encourage overﬁtting. Much recent work has been focused both on the architecture of the neural network as well as on the computations performed within each node in order to minimize overﬁtting. Furthermore, the way in which the neural network is trained also has an impact on the quality of the ﬁnal solution. Many clever methods, such as pretraining (cf. Chapter 4), have been proposed in recent years in order to improve the quality of the learned solution. This book will explore these advanced training methods in detail. 1.2.3 The Multilayer Network as a Computational Graph It is helpful to view a neural network as a computational graph, which is constructed by piecing together many basic parametric models. Neural networks are fundamentally more powerful than their building blocks because the parameters of these models are learned jointly to create a highly optimized composition function of these models. The common use of the term “perceptron” to refer to the basic unit of a neural network is somewhat misleading, because there are many variations of this basic unit that are leveraged in diﬀerent settings. In fact, it is far more common to use logistic units (with sigmoid activation) and piecewise/fully linear units as building blocks of these models. A multilayer network evaluates compositions of functions computed at individual nodes. A path of length 2 in the neural network in which the function f (·) follows g(·) can be considered a composition function f (g(·)). Furthermore, if g1 (·), g2 (·) . . . gk (·) are the functions computed in layer m, and a particular layer(m + 1) node computes f (·), then the composition function computed by the layer(m + 1) node in terms of the layerm inputs is f (g1 (·), . . . gk (·)). The use of nonlinear activation functions is the key to increasing the power of multiple layers. If all layers use an identity activation function, then a multilayer network can be shown to simplify to linear regression. It has been shown [208] that a netwo