Computer Vision Chapter 4

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

1 Computer Vision Chapter 4
Statistical Pattern Recognition Presenter:傅楸善 & 李承翰 Cell phone: 指導教授:傅楸善 博士 Digital Camera and Computer Vision Laboratory Department of Computer Science and Information Engineering National Taiwan University, Taipei, Taiwan, R.O.C.

2 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

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

4 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) DC & CV Lab. CSIE NTU

5 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

6 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

7 An Instance DC & CV Lab. CSIE NTU

8 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 有四種狀況 DC & CV Lab. CSIE NTU

9 Another Instance (cont.)
我們可以得到兩張表 一張是表示true state 跟detected state 的機率 DC & CV Lab. CSIE NTU

10 Another Instance (cont.)
另一張表示 true state 跟detected state的economic gain DC & CV Lab. CSIE NTU

11 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 = DC & CV Lab. CSIE NTU

12 Conditional Probability
DC & CV Lab. CSIE NTU

13 Conditional Probability (cont.)
P(b|g): false-alarm rate P(g|b): misdetection rate Another formula for expected profit per object DC & CV Lab. CSIE NTU

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

15 Example 4.1 (cont.) DC & CV Lab. CSIE NTU

16 Example 4.2 P(g) = 0.95, P(b) = 0.05 另一個例子 DC & CV Lab. CSIE NTU

17 Example 4.2 (cont.) DC & CV Lab. CSIE NTU

18 Decision Rule Construction
(t, a): summing (t, a, d) on every measurements d Therefore, Average economic gain DC & CV Lab. CSIE NTU

19 Decision Rule Construction (cont.)
Measurement d 這軸已經被壓進右圖了 這本書的average 通常指的就是期望值 期望值可以從對應的項的sum of products得到 DC & CV Lab. CSIE NTU

20 Decision Rule Construction (cont.)
We can use identity matrix as the economic gain matrix to compute the probability of correct assignment: DC & CV Lab. CSIE NTU

21 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) Decision rule 在分類的時候 我們只使用measurement data 就是他真正的類別跟decision rule是沒有互相影響的 也就是說 我們可以得到以下的式子 接著做一下式子的推導 DC & CV Lab. CSIE NTU

22 Fair Game Assumption (cont.)
From the definition of conditional probability 根據條件機率的定義 DC & CV Lab. CSIE NTU

23 Fair Game Assumption (cont.)
By fair game assumption, P(t, a, d) = By definition, = DC & CV Lab. CSIE NTU

24 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 DC & CV Lab. CSIE NTU

25 Expected Value on f(a|d)
Previous formula By and => 上面是之前求期望值的公式 所以這些代換 可以得到新的期望值公式 DC & CV Lab. CSIE NTU

26 Expected Value on f(a|d) (cont.)
移動一下summation 的位置 我們最後可以得到 這個式子 這式子呈現了 期望值跟decion rule間的影響關係 DC & CV Lab. CSIE NTU

27 Bayes Decision Rules Maximize expected economic gain Satisfy
DC & CV Lab. CSIE NTU

28 Bayes Decision Rules (cont.)
DC & CV Lab. CSIE NTU

29 Bayes Decision Rules (cont.)
+ + DC & CV Lab. CSIE NTU

30 Continuous Measurement
For the same example, try the continuous density function of the measurements: and Prove that they are indeed density function 如果measurement space是連續的 而不是離散的 我們使用連續密度函數 使用積分來取代使用summation 同個例子 T1類別 與T2類別 證明他們是密度函數 我們對0 1區間積分 可以得到1 DC & CV Lab. CSIE NTU

31 Continuous Measurement (cont.)
Suppose that the prior probability of is and the prior probability of is When , a Bayes decision rule will assign an observed unit to t1, which implies => x: measurement 假設 prior probability t1先前的機率 t1 是1/3 t2 是2/3 P(t1,x) =X2 = 3*x2 *1/ p(t2,x) = 3((1-x2)/2 * 2/3 DC & CV Lab. CSIE NTU

32 Continuous Measurement (cont.)
.805 > .68, the continuous measurement has larger expected economic gain than discrete 所以我們可以得到0.85 比之前0.68來的更好 DC & CV Lab. CSIE NTU

33 Prior Probability The Bayes rule: Replace with
The Bayes rule can be determined by assigning any categories that maximizes P(t) 是我們在我們observed the unit’s meaurement之前 預先期望他的true category 是T 所以我們可以得到另外一個Bayes decision rule的公式 使用Prior Probabilty 為什麼本來好好的P(t,d)不要, 要變成 P(d|t)呢 ? 大家看一下這個式子, 有時連P(t) 都不知道了, 更何況是 P(t,d) 呢 ? 一般來說P(d|t)是比較好量的 DC & CV Lab. CSIE NTU

34 Economic Gain Matrix Identity matrix Incorrect loses 1
A more balanced instance DC & CV Lab. CSIE NTU

35 Maximin Decision Rule Maximizes average gain over worst prior probability 小中取大決策準則 極大化最小收益這個準則得到的結果 可以保證比先前最差的期望值來的好 DC & CV Lab. CSIE NTU

36 Example 4.3 DC & CV Lab. CSIE NTU

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

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

39 Example 4.3 (cont.) The lowest Bayes gain is achieved when
E[e;f5]=( )*p(c1) E[e;f7]=( )*p(c1)+0.9 帶回 Bayes gain = 4/7 * /7 * 0.5 = The lowest gain is DC & CV Lab. CSIE NTU

40 Example 4.3 (cont.) 這是所有 decision rule的期望值 中間那條fm就是maximin decision rule DC & CV Lab. CSIE NTU

41 Example 4.4 兩個類別C1 c2 兩個measurement d1 d2 DC & CV Lab. CSIE NTU

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

43 Example 4.4 (cont.) F2 是maximin decion rule DC & CV Lab. CSIE NTU

44 Example 4.4 (cont.) 在這個case maximin decision rule 也是deterministic decision rule DC & CV Lab. CSIE NTU

45 Example 4.5 這個個例子比較複雜 DC & CV Lab. CSIE NTU

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

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

48 Decision Rule Error The misidentification errorαk
The false-identification error βk  [aɪ͵dɛntəfəˋkeʃən] Alpha : 不小心把良品當成不良品 稱之為Type I error Beta : 把不良品當作良品 稱之為tpe II error DC & CV Lab. CSIE NTU

49 An Instance Beta 0 0.05*1+0.05*1 / ( 0.5 +0.5 +0.1+0.1+0.15+0.5)
DC & CV Lab. CSIE NTU

50 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

51 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

52 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:暴力法 DC & CV Lab. CSIE NTU

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

54 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

55 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 1.設定一個threshold 大的往左 小的往右 2.另用一個數學式子來判斷 3.也是一個式子 4..當所有類別的共異變數(convariance)都一樣的時候 Bayes quadratic decision 會變成linear 5.PCA 是一種正交(orthogonal)線性轉換，能將原始資料轉換到一個新的座標系統 DC & CV Lab. CSIE NTU

56 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 1.Error estimation 是個重要的方法去衡量decision rule的效能(performance) 2.要測試一個decision rule 我們通常會拿一組資料去測試 看出來的成果好不好 這組資料必須跟training 用的data set是互相獨立的 這個方法叫做 resubstitution method (重新帶入法) 3.Hold out method(保留法) 把資料分為一半 一半拿來train decision rule 再拿另一半做test data set 然後互換再做一次 合併兩次得到的error rate去做error estimation DC & CV Lab. CSIE NTU

57 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 DC & CV Lab. CSIE NTU

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

59 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