Mathematical framework

• The client agent can randomly pick m samples to PAC learn a hypothesis h about whether the service agent can offer the ìcorrectî service .

• Theorem(Blumer et.al.) Let H be any hypothesis space of finite VC dimension d contained in , P be any probability distribution on X and the target concept c be any Borel set contained in X. Then for any , given the follo

Previous slide

Next slide

Back to first slide

View graphic version

VC dimension is a combinational measure of concept class complexity which assigns to each concept class C a single number that chracterizes the sample size need to pac learn c.

Step: By determining VC dimension , select EBUXITONG AND Delta,

we can randomly pick m samples to learn a hypothesis about whether the service is ìcorrect