View Single Post
Old 02-19-2015, 11:38 AM
magdon's Avatar
magdon magdon is offline
Join Date: Aug 2009
Location: Troy, NY, USA.
Posts: 595
Default Re: Hoeffding inequality for multiple hypothesis

Sorry, there was a typo in my previous message. Yes they are different events. But they are very related events.

A = [at\ least\ one\ h_i, |E_{in}-E_{out}|>\epsilon]

B = [for\ no\ h_i, |E_{in}-E_{out}|>\epsilon]


Originally Posted by kostya3312 View Post
Thank you, Professor!

I do not quite understand the following:

I thought that the goal is to get the upper bound for probability of event A = [for\ AT\ LEAST\ one\ hypothesis\ |E_{in}-E_{out}|>\epsilon]. That is, for feasibility of learning the probability of this event should be small. In my opinion two events A (mine) and B = [for\ no\ h_i, |E_{in}-E_{out}|>\epsilon] (yours) are different events. Am I right?

My last question is as follows. The LHS of Hoeffding inequality for M hypothesis is P[|E_{in}(g)-E_{out}(g)|>\epsilon]. It implies that event C = |E_{in}(g)-E_{out}(g)|>\epsilon and event A (event B if you are right) are equal. Though I understand the meaning of event A the meaning of event C isn't so clear for me. What it literally means? I think it means [absolute\ difference\ between\ E_{in}\ and\ E_{out}\ for\ final\ hypothesis\ g\ is\ greater\ than\ \epsilon]. Am I right?
Have faith in probability
Reply With Quote