VC维的来龙去脉

十月 18, 2017
Deep Learning

转自:http://www.flickering.cn/machine_learning/2015/04/vc维的来龙去脉

VC维在机器学习领域是一个很基础的概念,它给诸多机器学习方法的可学习性提供了坚实的理论基础,但有时候,特别是对我们工程师而言,SVM,LR,深度学习等可能都已经用到线上了,但却不理解VC维。

这里,在台湾大学机器学习基石课程的基础上,我们简单聊聊“VC维的来龙去脉”。我们将解决以下问题:为什么某机器学习方法是可学习的?为什么会有过拟合?拿什么来衡量机器学习模型的复杂度?深度学习与VC维的关系?

说说历史

在讲VC维之前,我们不妨来说说VC维的历史。而说起VC维的历史,又不得不提起神经网络,一方面是因为神经网络与VC维的发明过程是交织在一起的,另一方面是由于神经网络乏善可陈的泛化控制方法,深度学习在理论基础上一直被怀疑,甚至神经网络和VC维的代表SVM还一起争风吃醋过好多年。

1943年,模拟神经网络由麦卡洛可(McCulloch)和皮茨(Pitts)提出,他们分析了理想化的人工神经元网络,并且指出了它们进行简单逻辑运算的机制。

1957年,康奈尔大学的实验心理学家弗兰克·罗森布拉特(Rosenblatt)在一台IBM–704计算机上模拟实现了一种他发明的叫作“感知机”(Perceptron)的神经网络模型。神经网络与支持向量机都源自于感知机(Perceptron)。

1962年,罗森布拉特著作:《神经动力学原理:感知机和大脑机制的理论》(Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms)。

1969年,明斯基和麻省理工学院的另一位教授佩普特合作著作:《感知机:计算几何学》(Perceptrons: An Introduction to Computational Geometry)。在书中,明斯基和佩普特证明单层神经网络不能解决XOR(异或)问题。

1971年,V. Vapnik and A. Chervonenkis在论文“On the uniform convergence of relative frequencies of events to their probabilities”中提出VC维的概念。

1974年,V. Vapnik提出了结构风险最小化原则。

Read the rest of this entry »

Understanding Waiting Times Between Events with the Poisson and Exponential Distributions

A webhook POSTs to our database each time a particular event occurs on our website. We receive about two of these requests per minute. I was mindlessly monitoring the log files one day and noticed it had been roughly 90 seconds since our database had been hit by this request. Before worrying, though, I wondered how rare that observation is. What is the likelihood of waiting longer than 1.5 minutes for the next request?

This is a probability problem that can be solved with an understanding of Poisson processes and the exponential distribution. A Poisson process is any process where independent events occur at constant known rate, e.g. babies are born at a hospital at a rate of three per hour, or calls come into a call center at a rate of 10 per minute. The exponential distribution is the probability distribution that models the waiting times between these events, e.g. the times between calls at the call center are exponentially distributed. To model Poisson processes and exponental distributions, we need to know two things: a time-unit t and a rate \lambda .

Read the rest of this entry »

常用激活函数比较

十月 12, 2017
Deep Learning

本文结构:

  1. 什么是激活函数
  2. 为什么要用
  3. 都有什么
  4. sigmoid ,ReLU, softmax 的比较
  5. 如何选择

1. 什么是激活函数

如下图,在神经元中,输入的 inputs 通过加权,求和后,还被作用了一个函数,这个函数就是激活函数 Activation Function。

Read the rest of this entry »

如何理解神经网络里面的反向传播算法?

九月 12, 2017
Deep Learning

转自:https://www.zhihu.com/question/24827633

一般都是用链式法则解释,比如如下的神经网络

Read the rest of this entry »

正态分布的前世今生

七月 15, 2017
Linear Algebra

神说,要有正态分布,就有了正态分布。

神看正态分布是好的,就让随机误差服从了正态分布。

— 创世纪—数理统计

学过基础统计学的同学大都对正态分布非常熟悉。这个钟形的分布曲线不但形状优雅,它对应的密度函数写成数学表达式

 \displaystyle f(x)=\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{{(x-\mu})^2}{2\sigma^2}}

也非常具有数学的美感。其标准化后的概率密度函数

 \displaystyle f(x)=\frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}

更加的简洁漂亮,两个最重要的数学常量  \pie  都出现在这公式之中。在我个人的审美之中,它也属于 top-N 的最美丽的数学公式之一,如果有人问我数理统计领域哪个公式最能让人感觉到上帝的存在,那我一定投正态分布的票。因为这个分布戴着神秘的面纱,在自然界中无处不在,让你在纷繁芜杂的数据背后看到隐隐的秩序。

normal_curve

Read the rest of this entry »

Namespaces系列4:user namespace

一月 20, 2017
namespaces

User namespaces are have been introduced as early as Linux 3.5 and are considered as stable starting with Linux 4.3.

1. 简介

user namespace是最近才出现在内核主干里的,主要是为了隔离安全相关的标识和属性,例如 user IDs and group IDs (see credentials(7)), the root directory, keys (see keyctl(2)), and capabilities等等。但是从内核实现上来看,user namespace只是简单的提供了一种uid/gid映射机制,capabilities虽然与user namespace非常相关,但它不是user namespace中的概念,capabilities是进程的概念,它是进程的一种属性,它要远比user namespace出现的早

在这篇文章里,我们分四步走:

  1. 我们先来了解一下,user namespace的基本用法
  2. 以及user namespace如何结合capabilities实现容器的安全性隔离
  3. user namespace在解决什么问题?
  4. 内核实现
  5. 与其他namespace的交互以及兼容性问题

简单来说,有了这个东西之后,容器可以有一个假的root账户,在不影响宿主安全的情况下,最大限度的使用更多的内核特权功能,user namespace让容器变得更像虚拟机了

Read the rest of this entry »

Reconciling High Server Utilization and Sub-millisecond Quality-of-Service

一月 3, 2017
colocation

论文原址:http://csl.stanford.edu/~christos/publications/2014.mutilate.eurosys.pdf

In this paper, we analyze the challenges of maintaining high QoS for low-latency workloads when sharing servers with other workloads.

The additional workloads can interfere with resources such as processing cores, cache space, memory or I/O bandwidth

The goal of this work is to investigate if workload colocation and good quality-of-service for latency-critical services are fundamentally incompatible in modern systems, or if instead we can reconcile the two

Read the rest of this entry »

Heracles: Improving Resource Efficiency at Scale

十二月 5, 2016
colocation

论文原址:

  1. http://csl.stanford.edu/~christos/publications/2015.heracles.isca.pdf
  2. https://cs.stanford.edu/~davidlo/resources/2015.heracles.isca.slides.pdf

一个实时的、自反馈的,大规模提升资源利用率的系统

1. 简介

为了解决LC服务和BE作业混部引起的LC服务SLO下降的问题,我们开发了Heracles,一个实时的控制器,能够动态使用硬件隔离机制和软隔离机制,保证共享资源的干扰问题

Heracles能够在保证LC服务足够SLO的情况下,最大限度的将空闲资源用来运行BE作业,同时,结合实时监控离线分析,自动检测干扰源,并在合适的时机,自动调整隔离机制防御干扰产生

在这里我们分两步走:

第一步,我们首先来研究一些经典案例,最终会抛出一个结论,那就是混部情况下【如无特殊说明,以下混部一律特指LC服务和BE作业】,干扰绝大部分情况下都是不均匀的、但是和负载有较强的相关性,所以,通过静态分区的方式来隔离共享资源是不够的

第二步,然后我们会解释为什么要设计Heracles,并且会证明

  1. 多种隔离机制的互相结合,是实现高利用率并且不打破LC服务SLO的关键所在
  2. 将干扰问题细分成几个独立的子问题,能够大大的降低动态控制的复杂性
  3. 为什么一个运行在所有机器上的、实时的监控程序是必须的

第三步,我们来评估一下Heracles在Google内部生产环境能产生多大的收益,测试表明,能够将机器利用率提高到90%左右

最后,我们通过硬件的一些机制来实现DRAM带宽的监控与隔离,进一步提高Heracles的精确性以及降低对离线分析的依赖

Read the rest of this entry »

CPI2 : CPU performance isolation for shared compute clusters

十月 8, 2016
colocation

论文原址: http://research.google.com/pubs/pub40737.html

This paper describes CPI2, a system that builds on the useful properties of CPI measures to automate all of the following:

  1. observe the run-time performance of hundreds to thousands of tasks belonging to the same job, and learn to distinguish normal performance from outliers
  2. identify performance interference within a few minutes by detecting such outliers
  3. determine which antagonist applications are the likely cause with an online cross-correlation analysis
  4. (if desired) ameliorate the bad behavior by throttling or migrating the antagonists.

Read the rest of this entry »

文件系统:overlayfs

六月 27, 2016
filesystem

overlay文件系统的主要目的是要实现文件系统重叠,docker中的差分机制所依赖的文件系统分层就是依赖这种技术来实现的

1. upper and lower

overlay机制允许将两个文件系统重叠成一个文件系统,其中一个是upper,另一个是lower,对用户的可视顺序是:
upper -> lower

简单来说,如果upper和lower同时存在一个相同的文件,那么用户看到的是upper中的文件,lower中的同路径文件会被自动隐藏

overlay只关心文件,目录是会被穿透的,所以严格来说,overlay重叠的是目录树,而不是“文件系统”

所有的修改都会写入upper,lower是只读的。upper的文件系统必须支持trusted.*扩展属性,所以upper是不支持NFS的

Read the rest of this entry »