一些定义

  1. 向量空间(vector space): 满足加法和标量乘操作的集合
  2. 范数向量空间(normed vector space): 定义了向量长度的向量空间,这样我们就可以衡量向量间的长度了。
  3. 度量空间(metric space): 定义了两个点的距离的集合(这里不必须是向量空间)。范数向量空间是度量空间,但是度量空间不一定是范数向量空间。
  4. Banach 空间: 一个完备的范数向量空间。一个完备的空间指没有缺失的元素(所有的柯西序列都是收敛的)。
  5. 内积空间(inner product space)
    内积空间$(\mathcal{V}, \langle., .\rangle)$是在域$\mathbb{F}$上可进行$\langle., .\rangle : \mathcal{V}\times \mathcal{V} \to \mathbb{F}$运算法操作的向量空间,其满足三个原则:
    1)共轭对称:$\langle \mathbf{x}, \mathbf{y} \rangle = \overline{\langle \mathbf{y}, \mathbf{x} \rangle}$
    2)第一个变量满足线性性:$\langle a\mathbf{x}, \mathbf{y} \rangle = a \langle \mathbf{x}, \mathbf{y} \rangle$和$\langle \mathbf{x} + \mathbf{z}, \mathbf{y} \rangle = \langle \mathbf{x}, \mathbf{y} \rangle + \langle \mathbf{z}, \mathbf{y} \rangle$
    3)正定性:$\langle \mathbf{x},\mathbf{x} \rangle \geq 0$其中等式只有在$\mathbf{x}=0$时取到。

    注:

    1. 对于内积空间,我们可以推导出范数向量空间,即$l^2$范数空间,但是反过来就不一定成立了,因为如$l^1$范数,$||\mathbf{x}||_{1} = \sum_{i = 1}^n |x_i|$就不能满足内积空间
    2. An inner product space is also known as a pre-Hilbert space, meaning that it is one step behind a Hilbert space
  6. 希尔伯特空间: 当一个内积空间满足通过内积空间可推导出范数空间(赋范空间),并且是完备的,那么这个内积空间就是希尔伯特空间。

    对于常见的$\mathbb R^n$,满足内积运算,能够推导出$l^2$范数,且是完备的,所以是希尔伯特空间。

    另外希尔伯特空间是一个函数空间,即空间中每个元素都是一个函数,所以在希尔伯特空间中的函数可以理解为泛函(functional)

  7. 再生核:
    $\mathcal{X}$是非空集,$\mathcal{H}$是定义在$\mathcal{X}$上的希尔伯特空间。核$\mathcal{k}$满足下面的两条性质就称为$\mathcal{H}$的再生核:
    1) 对于每个$x_0 \in \mathcal{X}$, $k(y, x_0)$作为$y$的函数属于空间$\mathcal{H}$
    2) reproducing property: 对于每个$x_0 \in \mathcal{X}$和$f \in \mathcal{H}$,有$f(x_0) = \langle f(.), k(.,x_0) \rangle_\mathcal{H}$

    对于再生核的理解,首先性质1表示在$\mathcal{X}$中的每个点都可以通过核函数$k$来映射到希尔伯特空间$\mathcal{H}$中,性质2,表示,对于任意的属于$\mathcal{H}$的核函数都可以在$\mathcal{H}$中找到一个函数$f$(注意希尔伯特空间是一个函数空间)来重构出一个新的函数(这里如果函数$f$是一个核函数的话,会再生出一个核函数)

  8. 再生核希尔伯特空间:
    A Hilbert space $\mathcal{H}$ of complex-valued functions on a nonempty set $\mathcal{X}$ is called a reproducing kernel Hilbert space if the point evaluation functional $L_x$ is a bounded (equivalently, continuous) linear operator for all $x\in \mathcal{X}$

    补充定义:
    Point evaluation functional
    The point evaluation functional $L_x:\mathcal{H} → \mathbb{C}$ at a point $x\in \mathcal{X}$ is defined as $L_x(f):=f(x)$.

    Linear operator (Linear map) :
    Let $f:V→W$ be a function between two vector spaces $V,W$ over the same field $\mathbb F$. $f$ is called a linear operator if the following two conditions are satisfied for all $x,y\in \mathcal{V}$ and $a \in \mathbb{F}$.
    1)$f(u+v)=f(u)+f(v)$
    2)$f(au)=af(u)$

    Bounded linear operator :
    Let $f:\mathcal{V}→\mathcal{W}$ be a linear operator between two normed vector spaces $(\mathcal{V},||.||_{\mathcal{V}})$ and $(\mathcal{W},||.||_{\mathcal{W}})$, $f$ is called a bounded linear operator if there exists some $M>0$ such that for all $\mathbb u\in \mathcal{V}$,$||f(\mathbb u)||_{\mathcal{W}} \leq M ||\mathbb u||_{\mathcal{V}}$

  9. 定理:
    一个希尔伯特空间$\mathcal{H}$是一个再生核希尔伯特空间,当且仅当它有一个再生核(证明要见参考1)

  10. 对于给定的希尔伯特空间,再生核是唯一的。

参考

  1. a-tutorial-introduction-to-reproducing-Kernel-Hilbert-Spaces3篇有关希尔伯特空间的系列文章,很赞!不过需要翻墙~
  2. Free Mind

adaboost算法是经典的boosting算法,今天把李航统计学习方法上面的例8.1实现了一下,虽然看着挺简单的,但实现的时候还是有很多细节需要注意。由于代码是严格按照书上算法流程来敲的,这里就不放算法步骤了。直接上代码吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
# coding: utf-8
import numpy as np
class Params:
def __init__(self):
self.w = []
self.alpha = []
self.threshold = []
self.g = []
def setW(self, w):
self.w = w
def getThreshold(x, y, params):
"""获取当前权值分布下的误差率最小的阈值"""
threshold = np.zeros(len(x) + 1)
for idx in range(len(x)):
if idx > 0:
threshold[idx] = np.mean(x[idx-1 : idx+1])
else:
threshold[idx] = x[idx] - 0.5 ## 延拓0.5
threshold[-1] = x[-1] + 0.5
predict = np.ones(len(y)) * -1
minError = 1000
minThreshold = 0
ming = 1 ## 表示小于阈值时取1 否则取-1
for idx in range(len(threshold)):
predict = map(lambda x1: 1 if x1 == True else -1, x < threshold[idx])
error = np.sum(params.w[predict != y]) ##这里用样本权重来衡量误差率
if error < minError:
minThreshold = idx
minError = error
for idx in range(len(threshold)):
predict = map(lambda x1: 1 if x1 == True else -1, x > threshold[idx])
error = np.sum(params.w[predict != y])
if error < minError:
minThreshold = idx
minError = error
ming = -1
params.threshold.append(threshold[minThreshold])
params.g.append(ming)
return minError
def getGofx(idx, x, params):
"""获取第idx个分类器的预测值"""
if params.g[idx] == 1:
G = map(lambda x1: 1 if x1 == True else -1, x < params.threshold[idx])
else:
G = map(lambda x1: 1 if x1 == True else -1, x > params.threshold[idx])
return np.array(G)
def updateWeight(x, y, params):
"""更新样本权重"""
G = getGofx(-1, x, params)
normer = np.exp(- params.alpha[-1] * y * G)
Z = np.dot(params.w, normer)
params.w = params.w * normer / Z
def getPredict(x, params):
"""获取当前分类器的预测"""
predict = np.zeros(len(x))
for idx in range(len(params.alpha)):
G = getGofx(idx, x, params)
predict += G * params.alpha[idx]
predict = np.sign(predict)
return predict
def adaboost(x, y, params):
"""adaboost训练过程"""
errorNum = len(y)
while(errorNum > 0):
errorRate = getThreshold(x, y, params)
alpha = 0.5 * np.log((1 - errorRate)/errorRate)
params.alpha.append(alpha)
updateWeight(x, y, params)
predict = getPredict(x, params)
error = predict != y
errorNum = len(y[error])
print "alpha:", params.alpha
print "threshold:", params.threshold
print "errorNum:", errorNum
def main():
x = np.array([0,1,2,3,4,5,6,7,8,9])
y = np.array([1,1,1,-1,-1,-1,1,1,1,-1])
params = Params()
params.setW(np.ones(len(y)) * (1.0 / len(y)))
adaboost(x, y, params)
predict = getPredict(x, params)
print "y = ", y
print "predict = ", predict
if __name__ == '__main__':
main()
  1. 源代码下载 (如果有帮助记得点赞哦~~哈哈)
  2. 接下来,要用AdaBoost来跑一个实际的数据集来体验一下,同时尝试不同的基分类器看一下他强大的效果。
  3. 啊,Python用的还是不熟啊!!!

今天在跟老师讨论多核学习问题时,遇到sigmoid kernel,发现自己记忆的与老师说的好像不一样,然后查了一下,发现原来在形式上是有两种表示形式的,但是本质是相同的。

sigmoid function

sigmoid function : $$sigmoid(x) = \frac{1}{1+e^{-x}}$$
sigmoid function在神经网络中是一种典型的神经元激活函数,图形为:
sigmoid function

sigmoid kernel

sigmoid kernel : $$k(x, y) = \tanh(\alpha x^Ty + c)$$
其中$\tanh(x)$是双曲正切函数
$$\tanh(x) = \frac{e^x - e^{-x}}{e^x + e^{-x}} = \frac{1}{1+e^{-2x}} - \frac{1}{e^{2x} + 1}$$
图形为:
tanh function

可以看到两者的曲线趋势都是差不多的,s型函数,只是值域不同。那么我们再来将tanh拆开画图看看效果:
$$\frac{1}{1+e^{-2x}}$$
tanh function 1
$$- \frac{1}{e^{2x} + 1}$$
tanh function 2

我们可以看到这两个的图形趋势也是相同的,同样值域不一样,而且前者值域是$[0, 1]$,后者的值域是$[-1, 0]$,那么两者相加正好实现了原双曲正切的值域范围。
那么,我们平时所用的sigmoid函数只是取了前半部分。

一些理解

svm的理论部分在很多资料里都有详细的推导过程,这里就不总结了,对于SMO算法,《统计学习方法》中是这样描述的:

smo算法是一种启发式算法,其基本思路是:如果所有变量的解都满足此最优化问题的KKT条件,那么这个最优化问题的解就得到了。因为KKT条件是该最优化问题的充分必要条件

所以,我们的目标就是找到一组解使得他们都满足最优化问题的KKT条件。那么smo算法的手段就是:

否则,选择两个变量,固定其他变量,针对这两个变量构建一个二次规划问题。这个二次规划问题关于这两个变量的解应该更接近于原始二次规划问题,。。。

对于两个变量的选择,要求其中至少一个变量是违反KKT条件的。第一个变量$\alpha_1$选取违反KKT条件最严重的样本点,在实现过程中,感觉并不好判断违反的严重程度,所以选择全部遍历;第二个变量$\alpha_2$选取希望使其能够有足够大的变化。

Python实现

代码有参考博文[1]中的实现,主要改进:

  1. 对于第二个变量的选择,并没有遍历所有的样本点,而是选择能够使得$\alpha_2$有足够大的变化的点,实验表明,这样能够提高迭代效率;
  2. 给出了高斯核函数的实现
  3. 重构了一下代码~~ 当然也还有改进的地方,欢迎下方评论哦~
  4. 源码及样本数据下载如果有帮助记得点赞哦~~哈哈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
# -*- coding: utf-8 -*-
'''
Created on 2016年5月1日
@author: heiming
'''
import numpy as np
from scipy import io
import matplotlib.pyplot as plt
class Params:
def __init__(self):
##alpha:lagrange multiplyer
self.a = []
##b bias
self.b = 0.0
## punish parameter
self.c = 10
## decision error
self.epsilon = 0.001
## stop tolerance
self.stopTol = 0.0001
## smo difference of predict accuracy
self.e = []
## maximum iteration
self.maxIter = 100
## kernel type
self.kernelType = 'gaussian'
## gaussian parameter
self.sigma = 0.5
def setC(self, c):
self.c = c
def setEpsilon(self, epsilon):
self.epsilon = epsilon
def setKernel(self, kernelType, *args):
self.kernelType = kernelType
if self.kernelType == 'gaussian':
self.sigma = args[0]
def setMaxIter(self, Maxiter):
self.maxIter = Maxiter
def loadData(filePath, fileType):
"""
load样本
"""
if fileType == 'txt':
data = np.loadtxt(filePath)
trainData = data[:, :-1]
trainLabel = data[:, -1]
testData = []
testLabel = []
if fileType == 'mat':
data = io.loadmat(filePath)
trainData = data['xapp']
trainLabel = np.reshape(data['yapp'], newshape = (1, data['yapp'].size))[0]
testData = data['xtest']
testLabel = np.reshape(data['ytest'], newshape = (1, data['ytest'].size))[0]
return (trainData, trainLabel, testData, testLabel)
def kernel(data_j, data_i, params):
"""
计算样本j和样本i的内积
"""
if params.kernelType == 'linear':
k = np.dot(data_j, data_i)
if params.kernelType == 'gaussian':
diff = data_j - data_i
diff = np.dot(diff, diff)
k = np.exp(- diff / (2.0 * np.square(params.sigma)))
return k
def gOfx(data, label, data_i, params):
"""
计算g(x)=sum(ai * yi * k(xi, x)) + b
"""
if params.kernelType == 'linear':
k = np.dot(data, data_i)
if params.kernelType == 'gaussian':
diff = np.subtract(data, data_i)
diff = np.sum(np.multiply(diff, diff), axis = 1)
k = np.exp(- diff / (2.0 * np.square(params.sigma)))
g = np.dot(np.multiply(params.a ,label), k) + params.b
return g
def init(data, label, params):
"""
初始化E, a
"""
params.a = np.zeros((1, len(label)))[0]
for idx in range(len(params.a)):
diff = gOfx(data, label, data[idx], params) - label[idx]
params.e.append(diff)
def updateE(data, label, params):
"""
更新E
"""
for idx in range(len(params.a)):
diff = gOfx(data, label, data[idx], params) - label[idx]
params.e[idx] = diff
def getMaxE(idx, params):
"""
获取除去第idx个样本后最大的E
"""
tmp = params.e[1 : idx] + [0] + params.e[idx+1 :]
return tmp.index(max(tmp))
def getMinE(idx, params):
"""
获取除去第idx个样本后最小的E
"""
tmp = params.e[1:idx] + [params.c * 10] + params.e[idx+1 :]
return tmp.index(min(tmp))
def judgeConvergence(data, label, params):
"""
判断是否都已满足KKT条件
"""
alphay = 0.0
for idx in range(len(label)):
yg = label[idx] * gOfx(data, label, data[idx], params)
if (params.a[idx] == 0) and (yg < 1 - params.epsilon):
return False
elif (params.a[idx] > 0) and (params.a[idx] < params.c) and \
(yg > 1 + params.epsilon) or (yg < 1 - params.epsilon):
return False
elif (params.a[idx] == params.c) and (yg > 1 + params.epsilon):
return False
if (params.a[idx] < 0) or (params.a[idx] > params.c):
return False
alphay += params.a[idx] * label[idx]
if abs(alphay) > params.epsilon:
return False
return True
def train(data, label, params):
"""
svm train, use smo solve the quadratic convex problem
"""
iters = 0
init(data, label, params)
updated = True
while iters < params.maxIter and updated:
updated = False
iters += 1
##这里直接遍历所有的样本,只要违反了KKT条件就进入迭代
for i in range(len(params.a)):
ai = params.a[i]
ei = params.e[i]
if (label[i] * ei < params.stopTol and ai < params.c) or \
(label[i] * ei > params.stopTol and ai > 0):
if ei > 0:
j = getMinE(i, params)
else:
j = getMaxE(i, params)
eta = kernel(data[i], data[i], params) + \
kernel(data[j], data[j], params) - \
2 * kernel(data[i], data[j], params)
if eta <= 0:
continue
new_aj = params.a[j] + label[j] * \
(params.e[i] - params.e[j]) / eta
L = 0.0
H = 0.0
if label[i] == label[j]:
L = max(0, params.a[j] + params.a[i] - params.c)
H = min(params.c, params.a[j] + params.a[i])
else:
L = max(0, params.a[j] - params.a[i])
H = min(params.c, params.c + params.a[j] - params.a[i])
if new_aj > H:
new_aj = H
if new_aj < L:
new_aj = L
##判断alpha j是否有较大的变化
if abs(params.a[j] - new_aj) < 0.001:
print "j= %d, is not moving enough" % j
continue
new_ai = params.a[i] + label[i] * label[j] * (params.a[j] - new_aj)
new_b1 = params.b - params.e[i] - label[i] * kernel(data[i], data[i], params) * (new_ai - params.a[i]) \
- label[j] * kernel(data[j], data[i], params) * (new_aj - params.a[j])
new_b2 = params.b - params.e[j] - label[i] * kernel(data[i], data[j], params) * (new_ai - params.a[i]) \
- label[j] * kernel(data[j], data[j], params) * (new_aj - params.a[j])
if new_ai > 0 and new_ai < params.c:
new_b = new_b1
elif new_aj > 0 and new_aj < params.c:
new_b = new_b2
else:
new_b = (new_ai + new_aj)/2.0
params.a[i] = new_ai
params.a[j] = new_aj
params.b = new_b
updateE(data, label, params)
updated = True
print "iterate: %d, change pair: i: %d, j: %d" % (iters, i, j)
res = judgeConvergence(data, label, params)
if res:
break
def predictAccuracy(trainData, trainLabel, testData, testLabel, params):
"""
计算测试集的精度
"""
pred = np.zeros((1, len(testLabel)))
for idx in range(len(testLabel)):
pred[0, idx] = gOfx(trainData, trainLabel, testData[idx], params)
accuracy = np.mean(np.sign(pred) == testLabel)
return accuracy
def getSupportVector(params):
"""
获取支持向量的index
"""
supportVector = []
for idx in range(len(params.a)):
if params.a[idx] > 0 and params.a[idx] < params.c:
supportVector.append(idx)
return supportVector
def draw(trainData, trainLabel, params):
"""
特征数是两维时,可以画图来展示
"""
plt.xlabel(u'x1')
plt.xlim(0, 100)
plt.ylabel(u'x2')
plt.ylim(0, 100)
plt.title('svm - %s, tolerance %f, c %f' % ('trainData', params.stopTol, params.c))
for idx in range(len(trainLabel)):
data = trainData[idx]
if int(trainLabel[idx]) > 0:
plt.plot(data[0], data[1], 'or')
else:
plt.plot(data[0], data[1], 'xg')
w1 = 0.0
w2 = 0.0
for i in range(len(trainLabel)):
w1 += params.a[i] * trainLabel[i] * trainData[i][0]
w2 += params.a[i] * trainLabel[i] * trainData[i][1]
w = - w1 / w2
b = - params.b / w2
r = 1 / w2
lp_x1 = [10, 90]
lp_x2 = []
lp_x2up = []
lp_x2down = []
for x1 in lp_x1:
lp_x2.append(w * x1 + b)
lp_x2up.append(w * x1 + b + r)
lp_x2down.append(w * x1 + b - r)
plt.plot(lp_x1, lp_x2, 'b')
plt.plot(lp_x1, lp_x2up, 'b--')
plt.plot(lp_x1, lp_x2down, 'b--')
plt.show()
def main():
####------------------------------------------
# filePath = '../smo/train.txt'
# fileType = 'txt'
# trainData, trainLabel, testData, testLabel = loadData(filePath, fileType)
# params = Params()
# params.setKernel('linear')
####------------------------------------------
filePath = '../smo/ionosphere_1.mat'
fileType = 'mat'
trainData, trainLabel, testData, testLabel = loadData(filePath, fileType)
params = Params()
# params.setKernel("gaussian", 0.5) #acc=0.902857 100步截断
params.setKernel("gaussian", 1) # acc = 0.942857 18步收敛
params.setMaxIter(500) ##在230步左右收敛,精度为0.88,sv 太多
params.setEpsilon(0.01)
####------------------------------------------
train(trainData, trainLabel, params)
print 'a= ', params.a
print 'b= ', params.b
supportVector = getSupportVector(params)
print 'support vector = ', supportVector
#### 两维特征可以在样本空间中画出图来展示划分效果
# draw(trainData, trainLabel, params)
#### 有测试集可以计算出预测精度
print('test set accuracy: %f' % predictAccuracy(trainData, trainLabel, testData, testLabel, params))
if __name__ == '__main__':
main()

实验结果分析

  • 线性核函数的分类效果图
    linear kernel

这里可能跟博文[1]中的结果不太一样了,主要是由于改变了对于第二变量的选择

  • 高斯核函数

    dataset: ionosphere(trainingSet : testingSet = 1:1)
    sigma = 5 accuracy = 0.46 iteration <=100
    sigma = 1 accuracy = 0.942857 iteration = 18
    sigma = 0.5 accuracy = 0.902857 iteration = 100+
    sigma = 0.05 accuracy = 0.645714 iteration <=100

    可以看出sigma的选择对于精度的影响还是很大的。这里只列出了sigma的影响,还有其他的参数对于精度和训练的迭代步数都有影响。

一些想法

  1. 刚开始看的时候有这样一个疑问:

    如果有多组解都满足kkt条件,那么smo算法不一定会找到使得目标函数取最小值的解

    然而有:KKT条件是最优化问题的充分必要条件,不禁感叹这样的理论是多么的强大!!!于是可以放心大胆的用smo了

  2. 对于核函数的选择,高斯核是很常用的,但是对于sigma的选取却很有讲究,在上面的实验结果也能够看出,不同的sigma的选择,对预测精度和迭代步数都有影响,于是搜索了一下,高斯核参数sigma对svm的影响,发现有不少关于这方面的讨论,不过还有一些暂时还消化不了,先总结下来。

    这里面大家需要注意的就是gamma的物理意义,大家提到很多的RBF的幅宽,它会影响每个支持向量对应的高斯的作用范围,从而影响泛化性能。我的理解:如果设的太大,则会造成只会作用于支持向量样本附近,对于未知样本分类效果很差,存在训练准确率可以很高,而测试准确率不高的可能,就是通常说的过训练;而如果设的过小,则会造成平滑效应太大,无法在训练集上得到特别高的准确率,也会影响测试集的准确率

    此外大家注意RBF公式里面的$\sigma$和$\gamma$的关系如下:

    The rbf kernel is typically defined as

    $$k(x,z) = e^{\frac{-d(x,z)^2}{2*\sigma^2}}$$

    which can be re-defined in terms of gamma as

    $$k(x,z) = e^{-\gamma *d(x,z)^2}$$

    where $\gamma = \frac{1}{2*\sigma^2}$.

    $\gamma$越大,支持向量越少,$\gamma$值越小,支持向量越多。
    RBF核应该可以得到与线性核相近的效果(按照理论,RBF核可以模拟线性核),可能好于线性核,也可能差于,但是,不应该相差太多。

    当然,很多问题中,比如维度过高,或者样本海量的情况下,大家更倾向于用线性核,因为效果相当,但是在速度和模型大小方面,线性核会有更好的表现。

  3. smo名字的由来,未知~求解答~~

reference

  1. SMO序列最小最优化算法 这篇博文写的很赞,里面对KKT条件的推导规约很好
  2. SVM的两个参数 C 和 gamma
  3. 使用svm的一个常见错误 及博主的微博 啊,里面还是有一些暂时不能看懂的东西,核方法很强大,需要进一步学习!
  4. Python Numpy Tutorial 这个是stanford的一个教程,很赞!

python中numpy.exp()和scipy.exp()函数参数取一个很大的值(2500)时,会出现上面的溢出问题,在stackoverflow上提供了两个解决方案:1. 安装一个bigfloat库 2. 用numpy.seterr来控制异常的抛出。目前采用了第一种方法解决。

Bigfloat下载

Unofficial Windows Binaries for Python Extension Packages

windows上whl文件安装

windows下安装easy_install, pip 及whl文件安装方法

概念

半连续(semi-continuity)是对函数连续性的一种描述,与连续相比更弱一些。主要有两种半连续:上半连续(upper semi-continuous)和下半连续(lower semi-continuous)。

定义

上半连续
$$\lim \sup_{x\to x_0} f(x) \leq f(x_0)$$
这里的$\lim \sup$表示极限上界,就是说函数$f(x)$在趋向于$x_0$时,函数的极限上界要小于等于$f(x_0)$,可以借助下图来理解。

upper semi-continuity
可以看出,由于函数是分段的,从左侧趋向于$x_0$时(取不到),必定会小于$f(x_0)$,而从右侧趋向于$x_0$时是可以取到$f(x_0)$的,那么等号成立。

下半连续
$$\lim\inf_{x\to x_0} f(x) \geq f(x_0)$$
同理,这边的$\lim \inf$表示极限下界。

lower semi-continuity
这里的分析与上半连续一致,不赘述了。

性质

  1. 一个函数是连续的当且仅当他是上半连续的和下半连续的
  2. 两个上半连续的实值函数相加还是上半连续的;如果两个函数都是非负的,那么两者的乘积为上半连续
  3. 一个上半连续的函数乘以一个负数,变为下半连续
  4. 如果$C$是一个紧凑的空间(比如一个闭合的,有界的空间),且$f : C \to [-\infty, \infty)$是上半连续的,那函数$f$在$C$上必定取到最大值;
    同理,对于在$f : C \to (-\infty, \infty]$是下半连续的,那么函数在$C$上必定能取得最小值
  5. 假设$f_i : X \to [-\infty, \infty]$ 是一个下半连续函数,且每个 $ f_i $ 的定义域 $ I $ 都是非空的,那么定义函数 $f$ (追点取极值)

    $$f(x) = \sup_{i\in I} f_i(x), x\in X$$
    那么函数$f$也是下半连续的。

  6. 一个函数$f : \mathbf R^n \to \mathbf R$是下半连续的当且仅当它的上境界是闭合的

reference

  1. wiki semi-continuity

题目描述

给定一个含不同整数的集合,返回其所有的子集

如果 S = [1,2,3],有如下的解:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

思路

这题与全排列的题目有点类似,不过子集需要把所有排列的情况都列出来
这里参考了lintcode 中等题:subSets 子集的解法,感谢博主!

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
"""
@param S: The set of numbers.
@return: A list of lists. See example.
"""
def subsets(self, S):
S.sort()
res = []
self.mydfs(res, S, 0, 0, [])
return res
def mydfs(self, res, S, depth, start, valuelist):
res.append(valuelist)
print res
if depth == len(S): return
for i in range(start, len(S)):
self.mydfs(res, S, depth+1, i+1, valuelist+[S[i]])

题目描述

给出一个具有重复数字的列表,找出列表所有不同的排列。

给出列表 [1,2,2],不同的排列有:
[
[1,2,2],
[2,1,2],
[2,2,1]
]

思路

这题与上一题的思路差不多,先给list排序,然后在进行排列

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
"""
@param nums: A list of integers.
@return: A list of unique permutations.
"""
def permuteUnique(self, nums):
# write your code here
res = []
nums.sort()
self.getPermute([], nums, res)
return res
def getPermute(self, current, num, res):
if not num:
res.append(current + [])
#print res
return
for i, v in enumerate(num):
if i > 0 and num[i] == num[i - 1]:
continue
current.append(num[i])
self.getPermute(current, num[:i] + num[i+1:], res)
current.pop()

题目描述

For nums = [1,2,3], the permutations are:

[[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]]

思路

这题比较简单,不过lintcode平台这题不能用len()函数,所以,需要用enumerate来实现(这里参考了这位博主的方法)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
"""
@param nums: A list of Integers.
@return: A list of permutations.
"""
def permute(self, nums):
# write your code here
#if len(num) <= 1: return [num]
result = []
if nums == None:
return []
else:
self.get_permute([], nums, result)
return result
def get_permute(self, current, num, result):
if not num:
result.append(current + [])
return
for i, v in enumerate(num):
current.append(num[i])
self.get_permute(current, num[:i] + num[i + 1:], result)
current.pop()

写在前面的话

目前hexo搭建静态博客已经很流行了,方便,快捷,而且还有很多主题供大家选择,真是超赞的。不过,由于hexo没有后端,所以,在不同机器上想要实现同步更新博客,就比较麻烦了,不过也有很多解决方案,比如:利用git解决hexo博客多PC间同步问题就提供了好几种,我选择的是在github上建一个单独的仓库,将博客源文件备份到上面,这样,在不同电脑上只要git clone下来,然后再进行hexo环境安装就能够实现同步了

遇到的问题

但是在上传博客源文件时,出现了一个问题,就是themes文件夹下的除了landscape这个主题能正常上传外,其他主题都上传不了,搞了好久,终于在一个博客里找到了答案:由于我们安装的其他主题本身就有git进行管理,没有记错的话,其实我们当初是git clone来的主题,所以,我们需要把这些文件夹下的.git文件夹给删掉,再重新上传就可以了。
参考自用github管理hexo本地文件夹实现两台电脑同步感谢这位博主!