Minimum number of training examples for Find-S/Candidate Elimination algorithms?

Posted by Rich on Stack Overflow See other posts from Stack Overflow or by Rich
Published on 2010-05-02T23:26:31Z Indexed on 2010/05/02 23:27 UTC
Read the original article Hit count: 189

Filed under:

machine-learning

|

search

|

learning

|

artificial-intelligence

Consider the instance space consisting of integer points in the x, y plane, where 0 = x, y = 10, and the set of hypotheses consisting of rectangles (i.e. being of the form (a = x = b, c = y = d), where 0 = a, b, c, d = 10).

What is the smallest number of training examples one needs to provide so that the Find-S algorithm perfectly learns a particular target concept (e.g. (2 = x = 4, 6 = y = 9))? When can we say that the target concept is exactly learned in the case of the Find-S algorithm, and what is the optimal query strategy?

I'd also like to know the answer w.r.t Candidate Elimination.

Thanks in advance.

© Stack Overflow or respective owner

Related posts about machine-learning

Machine learning challenge: diagnosing program in java/groovy (datamining, machine learning)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi All! I'm planning to develop program in Java which will provide diagnosis. The data set is divided into two parts one for training and the other for testing. My program should learn to classify from the training data (BTW which contain answer for 30 questions each in new column, each record in… >>> More
Is it possible to predict future using machine learning and/or AI?

as seen on Programmers - Search for 'Programmers'
Recently I have started reading about machine learning. From 3000 feet view, machine learning seems really great thing but as if now I have found that machine learning is limited to only 3 types of algorithms namely classification, clustering and recommendations. I would like to know if my assumption… >>> More
Design for a machine learning artificial intelligence framework

as seen on Stack Overflow - Search for 'Stack Overflow'
This is a community wiki which aims to provide a good design for a machine learning/artificial intelligence framework (ML/AI framework). Please contribute to the design of a language-agnostic framework which would allow multiple ML/AI algorithms to be plugged into a single framework which: runs… >>> More
Design for a machine learning artificial intelligence framework (community wiki)

as seen on Stack Overflow - Search for 'Stack Overflow'
This is a community wiki which aims to provide a good design for a machine learning/artificial intelligence framework (ML/AI framework). Please contribute to the design of a language-agnostic framework which would allow multiple ML/AI algorithms to be plugged into a single framework which: runs… >>> More
A good machine learning technique to weed out good URLs from bad

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I have an application that needs to discriminate between good HTTP GET requests and bad. For example: http://somesite.com?passes=dodgy+parameter # BAD http://anothersite.com?passes=a+good+parameter # GOOD My system can make a binary decision about whether or not a… >>> More

Related posts about search

"Error in the Site Data Web Service." when performing crawl

as seen on Server Fault - Search for 'Server Fault'
Installed SharePoint Services v3 (SP2, october 2009 cumulative updates, Language Pack), attached to a content database I had previously (all works). Installed Search server 2008 Express (with language pack) on top of WSS and crawl does not work. However it works for newly created web application +… >>> More
Search Alternative Search Engines from within Bing’s Search Page

as seen on How to geek - Search for 'How to geek'
So you love using Bing Search but may still be curious to see what another search engine will provide if used. Now you can search using another search engine from within the Bing Search page and enjoy numbered results using two simple user scripts. Note: These user scripts may also be added to other… >>> More
CONVERT(int, (datepart(month, @search)), (datepart(day, @search)), DateAdd(year, Years.Year - (datepart(year, @search)))

as seen on Stack Overflow - Search for 'Stack Overflow'
In the query the top part is getting all the years that will run in the stored procedure. Works fine But at first i just wanted to run the queries for yesterdays date for all the years, but now i realized i want the user to select a date that will be in a parameter @search Booked <= CONVERT(int… >>> More
Am?lioration du Search MOSS: synonyme et Best Bet - La gestion des synonymes dans MOSS Search

as seen on ASP-PHP.net - Search for 'ASP-PHP.net'
Le moteur de recherche de MOSS permet la configuration d'une liste de synonymes. Nous verrons donc dans cet article comment effectuer cette tache et ce que cela peut apporter ? vos utilisateurs. Nous verrons aussi comment automatiser un peu plus cette configuration par l'utilisation de code ou d'outils… >>> More
Utiliser un MOSS 2007 Search avec SPS 2003 - Comment utiliser un MOSS Search avec SPS Portail

as seen on ASP-PHP.net - Search for 'ASP-PHP.net'
Microsoft Office SharePoint Server 2007 (MOSS) fournit de nombreuses fonctionnalit?s qui ne sont pas disponibles sous SharePoint Portal Server 2003 (SPS). C'est particuli?rement vrai pour le moteur de recherche. Ce moteur de recherche peut pourtant ?tre utilis? sans attendre une ?volution du site… >>> More