Count 朱: 7月 2017

台大的線上課程，Machine Learning Foundations，在談到Hoeffding's Inequality：

這個不等式是拿來做什麼用的？舉下圖的罐子取球為例：

罐子裡有兩種顏色的彈珠，橘色和綠色。

橘色彈珠，以後稱為紅色，在Machine Learning，代表錯誤的資料。
綠色彈珠，在Machine Learning代表正確的資料。
mu = 紅色彈珠在罐子裡的機率。在Machine Learning代表母體資料的錯誤機率。
nu = 紅色彈珠在樣本裡的機率。在Machine Learning代表樣本資料的錯誤機率。

罐子裡的彈珠數量不明，紅色彈珠在罐子裡的機率mu也不明，要如何預測mu？我們可以從罐子裡取出N顆彈珠，看看紅色彈珠佔的比例nu為多少，就能推測mu。

根據經驗，N愈大，用nu就可以推測的mu，也就是N愈大，nu就愈接近mu，誤差就愈少。通常，因為成本考量，我們無法取得太多的樣本，所以就定義一個容忍度epsilon

epsilon >= |nu - mu|

意思就是希望 nu與mu的誤差，不要超過epsilon。用機率描述我們的需求，就是希望nu與mu的誤差超過epsilon，這件事情，發生的機率，愈少愈好。用數學式子表達就是：

P [|nu - mu| > epsilon]

這就是Hoeffding's Inequality，不等式左邊的意思。於是，計算P的方式，就要靠不等式的右邊：

P的值，是由N與epsilon決定的，我用Python畫成曲線圖：

Python程式碼如下：
[Hoeffding2.py]

	#
	# Draw the Hoeffding's Inequality with the epsilons = 0.3 and the probability.
	#

	from scipy import signal
	import numpy as np
	import math

	def hoeffding (x, epsilon):
	y = 2.0 * math.exp (-2epsilonepsilon*x)
	return y

	x = np.arange (0, 20, 0.01)

	y = [hoeffding (x, 0.3) for x in x]

	import matplotlib.pyplot as plt

	plt.xlabel ('N')
	plt.ylabel ('P')
	latex1 = r'P\leq2e^{\left( -2\varepsilon ^{2}N\right)}'
	plt.title (r"Hoeffding's Inequality: $ %s $" % latex1)

	latext2 = r'\varepsilon'
	plt.plot (x, y, label='$%s$ = 0.3' % latext2)

	x2 = 10
	y2 = hoeffding (10, 0.3)
	#plt.plot ([0, 10], [y2, y2], label='y = %f' % y2)
	plt.axhline (y = y2, color='grey', linestyle='--')
	plt.axvline (x = x2, color='grey', linestyle='--')
	plt.scatter (x2, y2, color='red', label='x = %d, y = %f' % (x2, y2))

	plt.legend ()
	plt.show ()

view raw Hoeffding2.py hosted with ❤ by GitHub

發現N愈大，P就愈小。還發現當N <= 3的時候，P > 1。問題是，機率怎麼可能大於1？所以，對於Hoeffding's Inequality而言，當樣本數很小的情況下，式子的右邊會超過1。遇到這種情況，我們就不要去管它，因為機率大於1，是不可能會發生的事情，雖然它還是滿足了Hoeffding's Inequality。

這件事情也告訴了我們，從母體只取3個當做樣本，是沒有意義。

接下來看看，epsilon如何影響P。用4個epsilon：0.1、0.3、0.5、1，共畫了4條曲線如下：

很明顯，epsilon定的愈嚴，如0.1， P就愈大。定的愈寬，如0.5，P就愈小。

在樣本數量為5的情況下：

我想要表達的意思是，Hoeffding's Inequality是一個不等式，在樣本數量少，或誤差超過1的情況下，此不等式，沒有太大意義。

結論：

容忍度epsilon設的愈嚴，樣本出現錯誤的機率，和母體出錯誤的機率，兩者相差超出epsilon，這件事情發生的機率就愈大。
epsilon設的愈小，那麼所取的樣本數N就要夠大。如此一來，樣本的錯誤率，和母體的錯誤率，就不會相差太大。我們把上圖拉遠一點，如下圖，就可以了解這句話的意思。
最重要的一點，在母體的錯誤率mu不明的情況下，只要樣本數N夠大，在我們容許的範圍epsilon內，樣本的錯誤機率，可以代表母體的錯誤機率。

Python程式如下：

[Hoeffding.py]

	#
	# Draw the Hoeffding's Inequality with different epsilons, 0.1, 0.3, 0.5, and 1.
	#

	from scipy import signal
	import numpy as np
	import math

	def hoeffding (x, epsilon):
	y = 2.0 * math.exp (-2epsilonepsilon*x)
	return y

	#x = np.arange (0, 100, 0.01)
	x = np.arange (0, 10, 0.01)

	y1 = [hoeffding (x, 0.1) for x in x]
	y2 = [hoeffding (x, 0.3) for x in x]
	y3 = [hoeffding (x, 0.5) for x in x]
	y4 = [hoeffding (x, 1) for x in x]

	import matplotlib.pyplot as plt

	plt.xlabel ('N')
	plt.ylabel ('P')
	latex1 = r'P\leq2e^{\left( -2\varepsilon ^{2}N\right)}'
	plt.title (r"Hoeffding's Inequality: $ %s $" % latex1)

	latext2 = r'\varepsilon'
	plt.plot (x, y1, label=r'$%s$ = 0.1' % latext2)
	plt.plot (x, y2, label='$%s$ = 0.3' % latext2)
	plt.plot (x, y3, label='$%s$ = 0.5' % latext2)
	plt.plot (x, y4, label='$%s$ = 1' % latext2)

	plt.legend ()
	plt.show ()

view raw Hoeffding.py hosted with ❤ by GitHub

-Count

2017年7月29日 星期六

Hoeffding's Inequality

2017年7月29日星期六