Support Vector Machines and Perceptrons - Learning, Optimization, Classification, and Application to Social Networks

Preface

Overview

Audience

Organization

Contents

Acronyms

1 Introduction

1.1 Terminology

1.1.1 What Is a Pattern?

1.1.2 Why Pattern Representation?

1.1.3 What Is Pattern Representation?

1.1.4 How to Represent Patterns?

1.1.5 Why Represent Patterns as Vectors?

1.1.6 Notation

1.2 Proximity Function 1--4

1.2.1 Distance Function

1.2.2 Similarity Function

1.2.3 Relation Between Dot Product and Cosine Similarity

1.3 Classification 2--4

1.3.1 Class

1.3.2 Representation of a Class

1.3.3 Choice of G(X)

1.4 Classifiers

1.4.1 Nearest Neighbor Classifier (NNC)

1.4.2 K-Nearest Neighbor Classifier (KNNC)

1.4.3 Minimum-Distance Classifier (MDC)

1.4.4 Minimum Mahalanobis Distance Classifier

1.4.5 Decision Tree Classifier: (DTC)

1.4.6 Classification Based on a Linear Discriminant Function

1.4.7 Nonlinear Discriminant Function

1.4.8 Naïve Bayes Classifier: (NBC)

1.5 Summary

References

2 Linear Discriminant Function

2.1 Introduction

2.1.1 Associated Terms 1--3

2.2 Linear Classifier [2--4]

2.3 Linear Discriminant Function 2

2.3.1 Decision Boundary

2.3.2 Negative Half Space

2.3.3 Positive Half Space

2.3.4 Linear Separability

2.3.5 Linear Classification Based on a Linear Discriminant Function

2.4 Example Linear Classifiers 2

2.4.1 Minimum-Distance Classifier (MDC)

2.4.2 Naïve Bayes Classifier (NBC)

2.4.3 Nonlinear Discriminant Function

References

3 Perceptron

3.1 Introduction

3.2 Perceptron Learning Algorithm [1]

3.2.1 Learning Boolean Functions

3.2.2 W Is Not Unique

3.2.3 Why Should the Learning Algorithm Work?

3.2.4 Convergence of the Algorithm

3.3 Perceptron Optimization

3.3.1 Incremental Rule

3.3.2 Nonlinearly Separable Case

3.4 Classification Based on Perceptrons 2

3.4.1 Order of the Perceptron

3.4.2 Permutation Invariance

3.4.3 Incremental Computation

3.5 Experimental Results

3.6 Summary

References

4 Linear Support Vector Machines

4.1 Introduction

4.1.1 Similarity with Perceptron

4.1.2 Differences Between Perceptron and SVM

4.1.3 Important Properties of SVM 1--5

4.2 Linear SVM 1, 5

4.2.1 Linear Separability

4.2.2 Margin

4.2.3 Maximum Margin

4.2.4 An Example

4.3 Dual Problem

4.3.1 An Example

4.4 Multiclass Problems 2

4.5 Experimental Results

4.5.1 Results on Multiclass Classification

4.6 Summary

References

5 Kernel-Based SVM

5.1 Introduction

5.1.1 What Happens if the Data Is Not Linearly Separable? 2--4,6

5.1.2 Error in Classification

5.2 Soft Margin Formulation 2

5.2.1 The Solution

5.2.2 Computing b

5.2.3 Difference Between the Soft and Hard Margin Formulations

5.3 Similarity Between SVM and Perceptron

5.4 Nonlinear Decision Boundary 1--6

5.4.1 Why Transformed Space?

5.4.2 Kernel Trick

5.4.3 An Example

5.4.4 Example Kernel Functions

5.5 Success of SVM 2--5

5.6 Experimental Results

5.6.1 Iris Versicolour and Iris Virginica

5.6.2 Handwritten Digit Classification

5.6.3 Multiclass Classification with Varying Values of the Parameter C

5.7 Summary

References

6 Application to Social Networks

6.1 Introduction

6.1.1 What Is a Network?

6.1.2 How Do We Represent It?

6.2 What Is a Social Network? 1--4

6.2.1 Citation Networks

6.2.2 Coauthor Networks

6.2.3 Customer Networks

6.2.4 Homogeneous and Heterogeneous Networks

6.3 Important Properties of Social Networks 4

6.4 Characterization of Communities 2--3

6.4.1 What Is a Community?

6.4.2 Clustering Coefficient of a Subgraph

6.5 Link Prediction 1--4

6.5.1 Similarity Between a Pair of Nodes

6.6 Similarity Functions 1--4

6.6.1 Example

6.6.2 Global Similarity

6.6.3 Link Prediction based on Supervised Learning

6.7 Summary

References

7 Conclusion

Glossary

Index