View Single Post
Old 01-29-2015, 07:18 AM
kostya3312 kostya3312 is offline
Junior Member
Join Date: Jan 2015
Posts: 2
Default Re: Hoeffding inequality for multiple hypothesis

Thank you, Professor!

I do not quite understand the following:
Originally Posted by magdon View Post
The factor of M comes from using the union bound

P[for\ no\ h_i, |E_{in}(h_i)-E_{out}(h_i)|>\epsilon]\le P[|E_{in}(h_1)-E_{out}(h_1)|>\epsilon]+P[|E_{in}(h_2)-E_{out}(h_2)|>\epsilon]+\cdots.
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?
Reply With Quote