快速排序与快速选择算法
之所以突然会对这个问题感兴趣是因为，大概一年前，在毫无准备的情况下去参加某互联网公司的面试，被问到了这样一个问题：“给定一个长度为n的数列，如何快速的找出其中第m大的元素。假设m远小于n。”因为对排序和选择算法完全不熟悉，只知道quicksort的时间复杂度应该是，以及从数列中找出最大值的复杂度是 。只好回答最简...
Posts by Category
notes
Product Form of Euler’s Limit Formula for the Gamma Function
This note is a continuation of last one. By the definition of , for , we can rewrite it in the following form,
Asymptotic Expansion of Bessel Functions For Large Argument
This note is based on Appendix B.7 and B.8 of (Grafakos, 2008). First, we show that Bessel function can be written into the following form
Euler’s Limit Formula for the Gamma Function
This note is based on the Appendix A.7 of (Grafakos, 2008). The gamma function is defined by the integral . For integer this defines the factorial up to . ...
Holder’s and Young’s Inequalities
Classical Case A quick proof of general Holder’s inequality is as follows. First, by Jensen’s inequality, we have for positive and satisfying ,
Bessel Functions and Fourier Transform of Radial Functions
Definition of Bessel Functions
Universal Approximation Property of RKHS and Random Features (3)
We have seen the universal approximation property of RKHS generated by radial kernels and of one-hidden-layer neural networks with sigmoidal activation funct...
Universal Approximation Property of RKHS and Random Features (2)
Universal Approximation Property of RKHS In this note, we discuss the universal approximation property of RKHS and compare with the property of neural networ...
Universal Approximation Property of RKHS and Random Features (1)
On a subset of , a binary symmetric function is called positive definite if the matrix is positive semi-definite for any list of elements . It is clear th...
Log Loss and Multi-Class Hinge Loss (1)
Hinge loss functions are mainly used in support vector machines for classification problem, while cross-entropy loss functions are ubiquitous in neural netwo...
Capacity of Neural Networks (5): Sauer’s Lemma
In this note we prove the Sauer’s lemma which plays the key role in establishing the connection between VC-dimension and Rademacher complexity. We use the pr...
Proof of Stirling’s Formula
Stirling’s formula is very useful in all kinds of asymptotic analysis. Here we present one of many proofs.
Capacity of Neural Networks (4): VC-Dimension and Rademacher Complexity
In this note, we discuss the relation between VC-dimension and Rademacher/Gaussian complexities. First, let’s look at the definition of VC-dimension.
Capacity of Neural Networks (3): Main Results
In this note, we will look at the Rademacher complexity of 2-layer neural networks, and compare it with the result of kernel method. This is the main result ...
Capacity of Neural Networks (2): Contraction Inequality
In this section, we discuss the contraction inequality of Rademacher complexity. It is very useful for peeling off the loss function from the hypothesis clas...
Capacity of Neural Networks (1): Rademacher Complexity
Current sample complexity analysis of supervised learning heavily depends on the capacity analysis of the hypothesis classes. There are many different quanti...
On the Spectrum Decay Rate of Gaussian Kernel Operator
In the study of random Fourier features method, (Bach, 2017) proposed a way of generating random features so that the feature space generated randomly approx...
Upper and Lower Bounds of Sample Complexity of Supervised Learning
By the note on No-Free-Lunch, we concluded that there is no learning algorithms solving all problems with a fixed learning rate. It is because of the difficu...
On Hoeffding’s Inequality
Hoeffding inequality was first proved in 1963 for independent bounded random variables. It captures the effect of cancellation among independent random varia...
Weird Function Learned by A Simple Rule
(Proof of Problem 6.3 of (Devroye, Györfi, & Lugosi, 1997)
On No Free Lunch Theorem
This note discusses the implications of the celebrated No-Free-Lunch Theorem on kernel SVM, RF-SVM and neural network.
On Inverse Dependence On Training Data Size
This is a note on the paper SVM optimization: inverse dependence on training data size ((Shalev-Shwartz & Srebro, 2008)).
articles
What Is Random Fourier Features Method?
Random Fourier features method, or more general random features method is a method to help transform data which are not linearly separable to linearly separa...
如何阻止ssh重命名tmux窗口
在使用tmux多窗口终端时，每次登录学校的服务器后，窗口的标签就会被改成与服务器的prompt相同。而且登出后也不会改回来，导致tmux经常几个窗口的名字都很长，也没有反映窗口当时的状况。之所以会这样，是因为tmux默认允许一些进程修改窗口名，而ssh对终端窗口的命名规则是由服务器上的配置文件决定的。
HiDPI Chromebook上Crouton的设置
入手HP Chromebook 13 g1大半年，一开始就安装了Gallium OS。但Gallium OS迟迟无法解决intel skylake model上的音频输出问题，加上Gallium OS的电源管理比Chrome OS要弱不少，不接电源的情况下无法长时间的使用。忍了大半年后，终于回到了Crouton的...
利用Jekyll搭建博客
搭建个人博客主要有三种途径。一种是利用现成的博客网站，如Google的Blogger服务，新浪博客等。另一种则是利用软件生成博客网页， 再上传到自己的服务上。这一类博客生成软件有不少，比如应用最广泛的WordPress，和功能稍弱，但更为简洁的Jekyll和Pelican。
Acer C720电池更换及GalliumOS安装与配置
八月份完成论文的一个主要部分，决定犒赏一下自己。一直以来都想升级一下我的C720，毕竟是4年前的电脑了。特别是电池续航已经大不如从前，系统显示电池满电容量也只有标称容量的一半左右。没有了最初让我惊艳的全天不插电的续航表现，其他方面的弱点就让人更不能忍受了，比如屏幕的大小和分辨率，都距离今天的商务级的dell cp...
Chromebook如何让我变一个Linux粉
昨天花了两个多小时帮室友把他闲置了大半年的Chromebook装上了Linux系统。期间聊起我是什么时候开始接触和使用Linux系统的：
How to Update crouton in China
After the latest update of Chrome OS, the audio output had some problem of the ubuntu precise installed on my C720 via crouton. After searching online for ad...