Computer Vision Chapter 4

Presentation on theme: "Computer Vision Chapter 4"— Presentation transcript:

1 Computer Vision Chapter 4
Statistical Pattern Recognition Presenter: 小彼得 Digital Camera and Computer Vision Laboratory Department of Computer Science and Information Engineering National Taiwan University, Taipei, Taiwan, R.O.C.

2 Overview of this chapter
Introduction Bayes Decision Rules Economic Gain Matrix Maximin Decision Rule Decision Rule Error Reserving Judgment Nearest Neighbor Rule Binary Decision Tree Classifier Neural Networks It is not cover… ANY 真實的辨識..

3 Introduction Units: Image regions and projected segments
Each unit has an associated measurement vector Using decision rule to assign unit to class or category optimally DC & CV Lab. CSIE NTU

4 Introduction (Cont.) Feature selection and extraction techniques
Decision rule construction techniques Techniques for estimating decision rule error DC & CV Lab. CSIE NTU

5 Simple Pattern Discrimination
Also called pattern identification process A unit is observed or measured A category assignment is made that names or classifies the unit as a type of object The category assignment is made only on observed measurement (pattern) This is called Fair Game Assumption Unit就是真實發生的事 Measure就是儀器量到的 DC & CV Lab. CSIE NTU

6 Overview of this chapter
Introduction Bayes Decision Rules Economic Gain Matrix Maximin Decision Rule Decision Rule Error Reserving Judgment Nearest Neighbor Rule Binary Decision Tree Classifier Neural Networks

7 Simple Pattern Discrimination (cont.)
a: assigned category from a set of categories C t: true category identification from C d: observed measurement from a set of measurements D (t, a, d): event of classifying the observed unit P(t, a, d): probability of the event (t, a, b) 接著要進入統計的世界了 . 先定義一些名詞 DC & CV Lab. CSIE NTU

8 Economic Gain Matrix e(t, a): economic gain/utility with true category t and assigned category a A mechanism to evaluate a decision rule Identity gain matrix 我們在後面會一直常常用到這個 他就是某一個情況下, 事件發生會帶來的影響 DC & CV Lab. CSIE NTU

9 Identity Gain Matrix True/Assigned A B C D 1 DC & CV Lab. CSIE NTU

10 An Instance DC & CV Lab. CSIE NTU

11 Another Instance P(g, g): probability of true good, assigned good, P(g, b): probability of true good, assigned bad, ... e(g, g): economic consequence for event (g, g), … e positive: profit consequence e negative: loss consequence 各有4種狀況, 下面有兩張表格講解 DC & CV Lab. CSIE NTU

12 Another Instance (cont.)
DC & CV Lab. CSIE NTU

13 Another Instance (cont.)
至此大家要注意到. 我們是有兩張Table的 一張給定機率, 另一張給定economic 的影響 DC & CV Lab. CSIE NTU

14 Another Instance (cont.)
Fraction of good objects manufactured P(g) = P(g, g) + P(g, b) P(b) = P(b, g) + P(b, b) Expected profit per object E = P(g, g)*e(g,g) + P(g, b)*e(g,b) P(b, g)*e(b,g) + P(b, b)*e(b,b) 下一頁講條件機率 DC & CV Lab. CSIE NTU

15 Conditional Probability
DC & CV Lab. CSIE NTU

16 Conditional Probability (cont.)
P(b|g): false-alarm rate P(g|b): misdetection rate Another formula for expected profit per object 接著我們把條件機率帶到式子裡, 讓我們來看一個example DC & CV Lab. CSIE NTU

17 Example 4.1 P(g) = 0.95, P(b) = 0.05 DC & CV Lab. CSIE NTU

18 Example 4.1 (cont.) DC & CV Lab. CSIE NTU Table. 4.5在上一頁

19 Example 4.2 P(g) = 0.95, P(b) = 0.05 DC & CV Lab. CSIE NTU
Table 4.7, economic matrix 是一樣的 Prior 也是一樣的 DC & CV Lab. CSIE NTU

20 Example 4.2 (cont.) DC & CV Lab. CSIE NTU
這兩個例子告訴我們給定prior, 給定 economic 後 隨著我們偵測的machine performance會有所改變 DC & CV Lab. CSIE NTU

21 Decision Rule Construction
(t, a): summing (t, a, d) on every measurements d Therefore, Average economic gain 下一張是期望值的示意圖 DC & CV Lab. CSIE NTU

22 Decision Rule Construction (cont.)
Measurement d 這軸已經被壓進右圖了 這本書的average 通常指的就是期望值 DC & CV Lab. CSIE NTU

23 Decision Rule Construction (cont.)
We can use identity matrix as the economic gain matrix to compute the probability of correct assignment: True/Assigned A B C D 1 DC & CV Lab. CSIE NTU

24 Fair Game Assumption Decision rule uses only measurement data in assignment; the nature and the decision rule are not in collusion In other words, P(a| t, d) = P(a| d) DC & CV Lab. CSIE NTU

25 Fair Game Assumption (cont.)
From the definition of conditional probability DC & CV Lab. CSIE NTU

26 Fair Game Assumption (cont.)
Derive P(t,a|d) = P(a|d)P(t|d) By def., P(t,a|d) = P(t,a,d) / P(d) ----(1) By def., P(a|t,d) = P(t,a,d) / P(t,d) ----(2) By Fair Game Assumption P(a|t,d) = P(a|d) (3) (1)+(2)可得 P(t,a|d)*P(d) = P(a|t,d)*P(t,d) (3)代入得 P(t,a|d)*P(d) = P(a|d)*P(t,d) Q.E.D DC & CV Lab. CSIE NTU

27 預計花20 min DC & CV Lab. CSIE NTU

28 Deterministic Decision Rule
We use the notation f(a|d) to completely define a decision rule; f(a|d) presents all the conditional probability associated with the decision rule A deterministic decision rule: Decision rules which are not deterministic are called probabilistic/nondeterministic/stochastic Ok, 現在我們要開始推deterministic decision rule 這是比較符合”直觀”的想法 , 但不一定是最好的 我們令 function f 為這個分類函式. DC & CV Lab. CSIE NTU

29 Expected Value on f(a|d)
Previous formula By and => 首先e 不變, P(d) 是 prior , 知道生產出來的好壞為何 真正我們要決定的是 f . 這個函式決定了要怎麼分類 DC & CV Lab. CSIE NTU

30 Expected Value on f(a|d) (cont.)
從上面這個式子呢, 很直觀的來看, function f 不是0 就是1 應該針對某個d , 直接把其最大的P(t,d)設定 1, 其它為0 但這樣忘了考量e(t,a)帶來的效果 所以整理成下面這個式子 DC & CV Lab. CSIE NTU

31 Bayes Decision Rules Maximize expected economic gain Satisfy
Constructing f 現在我們正式的定義Bayes Decision Rule, 要從所有可能的function g中找到一個最好的 (可能不只一個) 後面會舉例 DC & CV Lab. CSIE NTU

32 Bayes Decision Rules (cont.)
每一個column 每一個column 看 看看如果 d1 的判斷結果是assign 成c1 , 那大括弧算出來的是什麼 ? 和 0.2 (p106 note) 接著我們要看如何求出false-positive, mis-identification. DC & CV Lab. CSIE NTU

33 Bayes Decision Rules (cont.)
+ 接著是往Continuous 的延伸 + DC & CV Lab. CSIE NTU

34 Continuous Measurement
For the same example, try the continuous density function of the measurements: and Measurement lie in the close interval [0,1] Prove that they are indeed density function P(x|t1) = 3x^2 DC & CV Lab. CSIE NTU

35 Continuous Measurement (cont.)
Suppose that the prior probability of is 1/3 and the prior probability of is 2/3 When , a Bayes decision rule will assign an observed unit to t1, which implies => x: measurement DC & CV Lab. CSIE NTU

36 Continuous Measurement (cont.)
.805 > .68, the continuous measurement has larger expected economic gain than discrete DC & CV Lab. CSIE NTU

37 Break 剛那邊15 minute DC & CV Lab. CSIE NTU

38 Prior Probability The Bayes rule: Replace with
The Bayes rule can be determined by assigning any categories that maximizes 為什麼本來好好的P(t,d)不要, 要變成 P(d|t)呢 ? 大家看一下這個式子, 有時連P(t) 都不知道了, 更何況是 P(t,d) 呢 ? 一般來說P(d|t)是比較好量的 DC & CV Lab. CSIE NTU

39 Equal-probability of ignorance
Equal-probability of ignorance assumption P(t) is likely equal. Put identity gain matrix together. Maximum likelihood decision rule. DC & CV Lab. CSIE NTU

40 Overview of this chapter
Introduction Bayes Decision Rules Economic Gain Matrix Maximin Decision Rule Decision Rule Error Reserving Judgment Nearest Neighbor Rule Binary Decision Tree Classifier Neural Networks It is not cover… ANY 真實的辨識..

41 Economic Gain Matrix Do they have different decision rules ? e(t,a) A
B C 1 e(t,a) A B C -30 70 -20 -10 DC & CV Lab. CSIE NTU

42 Economic Gain Matrix Identity matrix Incorrect loses 1
A more balanced instance Why we talk about this ? 之前在算decision rule時, 有e(t,d) 這個 economic matrix 現在我們要探討e 對 rule決定會造成什麼影響 DC & CV Lab. CSIE NTU

43 Economic Gain Matrix Suppose are two different economic gain matrix with relationship According to the construction rule. Given a measurement d, Because We then got DC & CV Lab. CSIE NTU

44 Economic Gain Matrix Summary
Under positive multiplicative constant and additive constant will not change the optimal rule. Why we talk about this ? 之前在算decision rule時, 有e(t,d) 這個 economic matrix 現在我們要探討e 對 rule決定會造成什麼影響 DC & CV Lab. CSIE NTU

45 Economic Gain Matrix In some cases, non regular matrix can derive optimal rule. Revisit the continuous example Let the economic matric be arbitrary, say it is Optimal rule is to assign t1 when Substituting the density for P(t1,x) , P(t2,x) Finally, reach assigns category t1 DC & CV Lab. CSIE NTU

46 Overview of this chapter
Introduction Bayes Decision Rules Economic Gain Matrix Maximin Decision Rule Decision Rule Error Reserving Judgment Nearest Neighbor Rule Binary Decision Tree Classifier Neural Networks 接著要講Maximin, 針對不同的optimal 對像的另一種rule

47 Maximin Decision Rule Recall, we have done that…
Finding function f(a|d) under… given d, pick “a” that maximize What if we don’t know P(t,d) and P(t) is not reasonable to be assume even. Equal-probability-of-ignorance assumption is not true DC & CV Lab. CSIE NTU

48 Maximin Decision Rule Maximizes average gain over worst prior probability 找一個f , 然後試所有可能的prior, DC & CV Lab. CSIE NTU

49 Maximin Decision Rule Simplify using the assumption that
Thus, reaching worst prior of When and others have zero probability Formula became , instead of 即使做了這樣的簡化, 一般情況下要找 Maximin rule仍是很困難 且通常找出來的rule不符合直覺 (是 stochastic的 ) DC & CV Lab. CSIE NTU

50 Example 4.3 DC & CV Lab. CSIE NTU

51 Example 4.3 (cont.) DC & CV Lab. CSIE NTU

52 Example 4.3 (cont.) DC & CV Lab. CSIE NTU

53 Example 4.3 (cont.) The lowest Bayes gain is achieved when
The lowest gain is DC & CV Lab. CSIE NTU

54 Example 4.3 (cont.) DC & CV Lab. CSIE NTU
注意任何f1~f7的線性組合都會落在這個convex hall裡 DC & CV Lab. CSIE NTU

55 Example 4.3 (cont.) The “general” maximin decision rule is a “stochastic” one and is “guaranteed” to achieve the worst possible Bayes gain. To determine a decision rule f that maximize 畫虛線至交點處 下一頁的例子是說最佳解也可以是deterministic DC & CV Lab. CSIE NTU

56 Example 4.4 DC & CV Lab. CSIE NTU

57 Example 4.4 (cont.) DC & CV Lab. CSIE NTU

58 Example 4.4 (cont.) DC & CV Lab. CSIE NTU

59 Example 4.4 (cont.) 下一個例子比較複雜 DC & CV Lab. CSIE NTU

60 Example 4.5 DC & CV Lab. CSIE NTU 他要說明三件事 1.Bayes 是最好的, (廢話, 己知prior)
2.General maximin rule 永遠可以做到和 Bayes最差一樣好 3. General maximin rule != Bayes decision rule DC & CV Lab. CSIE NTU

61 Example 4.5 (cont.) DC & CV Lab. CSIE NTU

62 Example 4.5 (cont.) f1 and f4 forms the lowest Bayes gain
Find some p that eliminate P(c1) p = DC & CV Lab. CSIE NTU

63 Break DC & CV Lab. CSIE NTU

64 Overview of this chapter
Introduction Bayes Decision Rules Economic Gain Matrix Maximin Decision Rule Decision Rule Error Reserving Judgment Nearest Neighbor Rule Binary Decision Tree Classifier Neural Networks 接著要講Maximin, 針對不同的optimal 對像的另一種rule

65 Decision Rule Error (Type I)The misidentification error αk
(Type II)The false-identification error βk Alpha : 不小心把好人指責成壞人 Beta : 把 DC & CV Lab. CSIE NTU

66 An Instance DC & CV Lab. CSIE NTU

67 Reserving Judgment The decision rule may withhold judgment for some measurements Then, the decision rule is characterized by the fraction of time it withhold judgment and the error rate for those measurement it does assign. It is an important technique to control error rate. DC & CV Lab. CSIE NTU

68 Reserving Judgment Let be the maximum Type I error we can tolerate with category k Let be the maximum Type II error we can tolerate with category k Measurement that will not be rejected (acceptance region) DC & CV Lab. CSIE NTU

69 Break DC & CV Lab. CSIE NTU

70 Nearest Neighbor Rule Assign pattern x to the closest vector in the training set The definition of “closest”: where is a metric or measurement space Chief difficulty: brute-force nearest neighbor algorithm computational complexity proportional to number of patterns in training set brute-force nearest neighbor:暴力法 這邊介紹了一個 metric , 講解一下, 距離的定義可以是好多種. DC & CV Lab. CSIE NTU

71 Nearest Neighbor Rule Cover and Hart(1967) showed that nearest neighbor rule will not have an error rate worse than twice the Bayes error rate Speed up: using eigenvalue decomposition. brute-force nearest neighbor:暴力法 這邊介紹了一個 metric , 講解一下, 距離的定義可以是好多種. DC & CV Lab. CSIE NTU

72 Nearest Neighbor Rule kNN algorithm DC & CV Lab. CSIE NTU

73 Nearest Neighbor Rule kNN algorithm DC & CV Lab. CSIE NTU
Open source C++ library , fast! DC & CV Lab. CSIE NTU

74 Binary Decision Tree Classifier
Assign by hierarchical decision procedure DC & CV Lab. CSIE NTU

75 Major Problems Choosing tree structure
Choosing features used at each non-terminal node Choosing decision rule at each non-terminal node DC & CV Lab. CSIE NTU

76 Decision Rules at the Non-terminal Node
Thresholding the measurement component Fisher’s linear decision rule Bayes quadratic decision rule Bayes linear decision rule Linear decision rule from the first principal component DC & CV Lab. CSIE NTU

77 Error Estimation An important way to characterize the performance of a decision rule Training data set: must be independent of testing data set Hold-out method: a common technique construct the decision rule with half the data set, and test with the other half More generalized method divide data set into N parts, use N-1 to train. 如果只用原來的資料測, 有時會有over-fitting的問題 DC & CV Lab. CSIE NTU

78 Neural Network A set of units each of which takes a linear combination of values from either an input vector or the output of other units 由線性組合來構成, 線跟線代表線性function, 邊上有weight 點則代表non-linear function Hidden layer可以有好多好多層 DC & CV Lab. CSIE NTU

79 Neural Network (cont.) Has a training algorithm Responses observed
Reinforcement algorithms Back propagation to change weights DC & CV Lab. CSIE NTU

80 Summary Bayesian approach Maximin decision rule
Misidentification and false-alarm error rates Nearest neighbor rule Construction of decision trees Estimation of decision rules error Neural network DC & CV Lab. CSIE NTU