Understanding Randomized Algorithms in Neural Networks

Randomized Algorithm LIANG-JUNG HUANG 2019/12/13

Outline Why is randomized algorithm? Guide for RA Famous RAs Application with randomness in neural network Conclusion

Why is RA? Useful algorithms to find solution or verify correctness Bound for some random variables Randomness relative to neural network

Guide for RA An algorithm that employs a degree of randomness as part of its logic Reduce time complexity or space complexity Running Time Correctness Las Vegas Algorithm Las Vegas Algorithm Probabilistic Certain Monte Carlo Algorithm Monte Carlo Algorithm Certain Probabilistic

Famous RAs Polynomial Identity Testing Given two polynomials, we need to check if ? ? ? ? ? ? = ?=1 ?(? ??) ? ? = ?=1 ????? ?(?2) ?

Famous RAs Polynomial Identity Testing Idea: Sample an integer ? from a uniform distribution set. Check if ? ? = ?(?), conclude ? ? ? ? . Which set to use? Set = [1,2, ,100 ?], where ? is the maximum degree of ?(?) and ?(?).

Famous RAs Polynomial Identity Testing This algorithm will make an error if ? ? ? ? ? we sampled satisfies ? ? = ? ? . How many ? can we sampled to satisfy the conditions?

Famous RAs Polynomial Identity Testing If ? satisfies the conditions, ? will be a solution of ?(?) ?(?) At most ? of them The maximum degree of ?(?) ?(?) is ? ? 1 P(error) = 100 ?= 100

Famous RAs Polynomial Identity Testing We can run this algorithm ? times. ? ???)? if all the ? s Conclude ? ? ? ?with probability = (? satisfy ?(?) = ?(?) Time complexity = ?(??)

Famous RAs Min-Cut Problem Find a cut of graph ? whose size is minimum The best deterministic algorithm for Min-Cut is Stoer-Wagner algorithm Time complexity = ? ? ? + ?2log ? = ?(?? + ?2log?)

Famous RAs Min-Cut Problem Contracting algorithm img src: http://www.cs.nthu.edu.tw/~wkhon/random18.html

Famous RAs Min-Cut Problem Idea: Contracting edge until remaining two vertices in ? The remaining edges is one of min-cut of ? How to make sure this?

Famous RAs Min-Cut Problem Suppose ? is one of min-cut of ?, ? = ? of ? Pr ? ? ??????? ? ?? ??????? Pr ? ?? ?????? ?? ? ? ??? = Pr(??? ????? ?? ? ??? ??? ??????????) Let ?? be the edge contracting not from ? in ?? step, Pr ?=1 ? 2?? = Pr ?1 Pr ?2 ?1 Pr(?? 2 ?=1 ? 3??)

Famous RAs Min-Cut Problem Let ? be the edge size of ?, ? ?? 2 ? ? 1 ? 2 = 1 2 Pr ?1 1 ? 2 Pr ?2 ?1 1 = 1 ? 1 ? Pr ?? 2 ?=1 ? 3?? 1 ? 1 ? 2

Famous RAs Min-Cut Problem Pr ??? ????? ?? ? ??? ??? ?????????? = Pr ?=1 ? 2?? ? 2 ? ? 3 ? 1 ? 4 ? 2 ? 5 ? 3 4 6 3 5 2 4 1 3 2 = ?(? 1)

Famous RAs Min-Cut Problem 2 Pr ? ? ??????? ? ?? ??????? ?(? 1), and run ? times ????????? ? ??????????:1 ? ? ?, and let ? = ?(? 1)log? ? 2 Pr ? ? ??????? ? ?? ??? ??????? 1 ? ? ?2 ? ? 1 1 Complexity of contracting = ? ?2 Time complexity = ? ?4log? > ?(?? + ?2log?) ?

Famous RAs Min-Cut Problem Karger s algorithm Contract edge until only contained ?/ 2 vertices ? ? 2 1 1 2 ? ? 1 Pr ??? ????? ?? ? ??? ??? ?????????? 2 Define ????????(?) = contract edge until only contained ?/ 2 vertices

Famous RAs Min-Cut Problem ?????????? ( ? ) = { ?? ? == 2 ?????? ? ?? ?; ?1 ???????? ? ,?2 ???????? ? ; ?????? min{ ?????????? ?1, ?????????? ?2 }; } Time complexity = ?(?2log?)

Famous RAs Min-Cut Problem Define ?(?) = Pr(? == ??????????(?| |?| = ? )) Pr((?1 ??????? ?) (? == ?????????? ?1)) = Pr ? == ?????????? ?1 Pr( ?1 ??????? ? ) ? 2 2 ?1 ??????? ? ) 1 ?

Famous RAs Min-Cut Problem 2 Pr(? ??????????(?)) = 1 1 ? 2? 2 2 ? ? 1 1 1 ? 2? 1 2 ? ? log ? 2 ? ? 1 ? 2 = 1

Famous RAs Min-Cut Problem Run 2log?log? times, then 2 log ? log ? 1 1 ? 2 log ?= Pr ??? ?????? ? 1 ?2 log ? Time complexity = ? ?2log3? < ?(?? + ?2log?)

Application with Randomness in NN Jacobian Neural Network, JNN The linear combination of two NN, one of them is generated randomly. Random Vector Functional Link, RVFL Weights of generated randomly. Only optimize weights of . img src: https://www.sciencedirect.com/science/article/pii/S002002551600058X

Application with Randomness in NN Radial basis function network, RBF network K-nearest neighbor Recurrent NN, RNN Liquid State Machine Convolution NN, CNN Dropout img src: https://www.csie.ntu.edu.tw/~htlin/course/mltech17spring/doc/214_handout.pdf

Conclusion If real analysis is difficult, we can try a randomized analysis, and calculate the average case Monte Carlo Random search may get a not-bad result, even better Think a stochastic idea than a deterministic algorithm

References Babai, L szl (1980). Isomorphism Testing and Symmetry of Graphs. Annals of Discrete Mathematics Volume 8. Metropolis, N. (1987). "The beginning of the Monte Carlo method". Los Alamos Science (1987 Special Issue dedicated to Stanislaw Ulam). Schwartz, Jack (October 1980). "Fast probabilistic algorithms for verification of polynomial identities". Journal of the ACM. 27 Karger, David (1993). "Global Min-cuts in RNC and Other Ramifications of a Simple Mincut Algorithm". Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms. Zhang., P.N.Suganthan (2016). A survey of randomized algorithms for training neural networks. Information Sciences Volumes 364 365. Q Que, Belkin(2016). Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51.