SVM之SMO优化

从大四开始接触SVM时每次都是推公式从原始优化问题到对偶问题然后应用个KKT条件就完事,然后过了一段时间就又觉得不对,好像整个SVM过程还缺了一些东西,前段时间偶然间注意到了SVM的Sequential Minimal Optimization(SMO)优化,才突然反应过来是对偶问题最终求解拉格朗日乘子这一步以前总是被忽略掉。。。汗

首先简要回顾一下SVM问题的求解过程,以最简单的线性可分情况为例,

$$!\min \frac{1}{2}\omega^T\omega\\\textit{s.t. }\forall y^i(\omega^Tx_i-b)\ge 1[......]

Read more

Maximum Product Subarray(LeetCode)

题目:

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.

思路:

这道题的原型是求最大和的子序列,二者差别主要在[......]

Read more

Michael I. Jordan概率图模型tutorial(一)

本文是对Michael Jordan关于Probability Graph Model的一篇tutorial(http://www.cis.upenn.edu/~mkearns/papers/barbados/jordan-tut.pdf)的细节补充。

首先,图模型(Graph Model)分为两种类型:有向图(Directed Graph)和无向图(Undirected Graph)。我们平时接触到的belief networks, bayesian networks, probabilistic
independence networks, M[......]

Read more

Social and Economic Networks: Models and Analysis笔记七:Games on Networks

最后一周的笔记迟迟没有上,真是拖延症,课程其实已经结束,由于没有认证,所以和之前机器学习一样都是没有认证序列号的。

这次课的内容仍然与strategic相关,但与之前的情形有一些差异,从一个特殊的基本情况开始:

1.Start with a Canonical Special Case

  •  Each player chooses action x_i in {0,1}
  • payoff will depend on: 1.how many neighbors choose each[......]

Read more

Social and Economic Networks: Models and Analysis笔记六:Learning on Networks

课程已经完结,真是拖延症,这个笔记还没做完,罪过~~赶紧抓紧补完……

上一节课的内容是扩散,比较适合简单的传染病传播建模,然后这一节课的主题有一点不同,尽管也属于某种扩散,但由于整个网络中所有结点具有决策能力,因此不再是简单的概率随机扩散。

1.Bayesian Learning

假设在一个大小为n的无向连通分量(undirected component)里,每个结点单位在每单位时间内可以进行一次决策,选择执行A或者B,对于这两个选择,A会带来1的收益(payoff),B则可能有概率p带来收益2或者概率1-p带来[......]

Read more

Social and Economic Networks: Models and Analysis笔记五:Diffusion on Networks

课程已经过半,社交网络的一些基础概念也已经在前面几节课中介绍了很多,幸运的是虽然后面的内容算是进阶性的,但是难度还好不是特别大。本次课程主要内容只包括一个单词"Diffusion",即扩散,其在现实世界中可以作为很多不同现象的背后依据。

1.Bass Model

首先介绍的是一个比较简单的扩散模型,注意,这是一个no network model,也就是不包含任何网络结构的模型:Bass Model。

假设现在有一群人(内部没有显示的社会结构),里面所有人都需要做出一项决定,用0和1表示决定的结果, F(t) 表示t时[......]

Read more

Social and Economic Networks: Models and Analysis笔记四:Strategic Network Formation

之前几节课涉及到的网络大多属于概率随机网络,即结点之间是否存在边是服从一定概率分布的,而这节课即使从名字上看也能发现一些不同,Strategic Network Formation既然包含了Stragetic这个词,那么我们的网络中所有边的构成显然不能在听天由命丢骰子决定了,具体如下。

1.An Economic Analysis

首先是一个经济学中的例子,引入变量 u_i(g) 为"payoff to i if the network is g",即在g网络中(无向图),结点i可以获得的收益,那么我们应该如何定义这个变量的计算公式[......]

Read more