Author name cluster

Leslie Valiant

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

AAAI Conference 2006 Conference Paper

Knowledge Infusion

Leslie Valiant

The question of how machines can be endowed with the ability to acquire and robustly manipulate commonsense knowledge is a fundamental scientific problem. Here we formulate an approach to this problem that we call knowledge infusion. We argue that robust logic offers an appropriate semantics for this endeavor because it supports provably efficient algorithms for a basic set of necessary learning and reasoning tasks. We observe that multiple concepts can be learned simultaneously from a common data set in a data efficient manner. We also point out that the preparation of appropriate teaching materials for training systems constructed according to these principles raises new challenges.

PDF Details

I&C Journal 1989 Journal Article

A general lower bound on the number of examples needed for learning

Andrzej Ehrenfeucht
David Haussler
Michael Kearns
Leslie Valiant

We prove a lower bound of Ω((1/ɛ)ln(1/δ)+VCdim(C)/ɛ) on the number of random examples required for distribution-free learning of a concept class C, where VCdim(C) is the Vapnik-Chervonenkis dimension and ɛ and δ are the accuracy and confidence parameters. This improves the previous best lower bound of Ω((1/ɛ)ln(1/δ)+VCdim(C)) and comes close to the known general upper bound of O((1/ɛ)ln(1/δ)+(VCdim(C)/ɛ)ln(1/ɛ)) for consistent algorithms. We show that for many interesting concept classes, including kCNF and kDNF, our bound is actually tight to within a constant factor.

Details DOI