257:, i.e., become empty, so that classification becomes impossible. One solution of this problem is proposed by Dubois and Quafafou that proposed the Rough Version Space, where rough sets based approximations are used to learn certain and possible hypothesis in the presence of inconsistent data.
250:" search method that accompanies the version space framework is not a popular learning algorithm, there are some practical implementations that have been developed (e.g., Sverdlik & Reynolds 1992, Hong & Tsang 1997, Dubois & Quafafou 2002).
28:
229:
consistent hypotheses) can be represented by just its lower and upper bounds (maximally general and maximally specific hypothesis sets), and learning operations can be performed just on these representative sets.
233:
After learning, classification can be performed on unseen examples by testing the hypothesis learned by the algorithm. If the example is consistent with multiple hypotheses, a majority vote rule can be applied.
203:
data already observed: Thus, if a novel (never-before-seen) data point is observed, it should be assumed to be negative. (I.e., if data has not previously been ruled in, then it's ruled out.)
222:
data already observed: Thus, if a novel (never-before-seen) data point is observed, it should be assumed to be positive. (I.e., if data has not previously been ruled out, then it's ruled in.)
135:
210:) cover the observed positive training examples, but also cover as much of the remaining feature space without including any negative training examples. These, if enlarged any further,
242:
The notion of version spaces was introduced by
Mitchell in the early 1980s as a framework for understanding the basic problem of supervised learning within the context of
31:
Version space for a "rectangle" hypothesis language in two dimensions. Green pluses are positive examples, and red circles are negative examples. GB is the maximally
218:
training example, and hence become inconsistent. These maximal hypotheses essentially constitute a (optimistic) claim that the true concept is defined just by the
199:
training example, and hence become inconsistent. These minimal hypotheses essentially constitute a (pessimistic) claim that the true concept is defined just by the
318:
253:
A major drawback of version space learning is its inability to deal with noise: any pair of inconsistent examples can cause the version space to
172:
In settings where there is a generality-ordering on hypotheses, it is possible to represent the version space by two sets of hypotheses: (1) the
144:). A version space learning algorithm is presented with examples, which it will use to restrict its hypothesis space; for each example
327:
47:
394:
Hong, Tzung-Pai; Shian-Shyong Tsang (1997). "A generalized version space learning algorithm for noisy and uncertain data".
75:
271:
188:
450:
39:
positive hypothesis boundary. The intermediate (thin) rectangles represent the hypotheses in the version space.
266:
375:
Rough Sets and
Current Trends in Computing: Proceedings of the Third International Conference, RSCTC 2002
373:
Dubois, Vincent; Quafafou, Mohamed (2002). "Concept learning with approximation: Rough version spaces".
55:
282:
67:
411:
243:
225:
Thus, during learning, the version space (which itself is a set – possibly infinite – containing
140:(i.e., either hypothesis 1 is true, or hypothesis 2, or any subset of the hypotheses 1 through
323:
309:
434:
Proceedings, Fourth
International Conference on Tools with Artificial Intelligence (TAI '92)
403:
378:
355:
63:
51:
156:
are removed from the space. This iterative refining of the hypothesis space is called the
444:
359:
415:
432:
Sverdlik, W.; Reynolds, R.G. (1992). "Dynamic version spaces in machine learning".
313:
180:
consistent hypotheses, where "consistent" indicates agreement with observed data.
187:) cover the observed positive training examples, and as little of the remaining
149:
59:
17:
382:
276:
27:
407:
160:
algorithm, the hypothesis space maintained inside the algorithm, its
26:
58:. Version space learning algorithms search a predefined space of
183:
The most specific hypotheses (i.e., the specific boundary
206:
The most general hypotheses (i.e., the general boundary
191:
as possible. These hypotheses, if reduced any further,
35:
positive hypothesis boundary, and SB is the maximally
346:
Mitchell, Tom M. (1982). "Generalization as search".
78:
396:
IEEE Transactions on
Knowledge and Data Engineering
129:
322:(2nd ed.). Prentice Hall. pp. 683–686.
130:{\displaystyle H_{1}\lor H_{2}\lor ...\lor H_{n}}
341:
339:
8:
377:. Malvern, Pennsylvania. pp. 239–246.
319:Artificial Intelligence: A Modern Approach
121:
96:
83:
77:
294:
304:
302:
300:
298:
66:. Formally, the hypothesis space is a
7:
176:consistent hypotheses, and (2) the
436:. Arlington, VA. pp. 308–315.
25:
1:
360:10.1016/0004-3702(82)90040-6
272:Inductive logic programming
168:The version space algorithm
467:
148:, the hypotheses that are
423:Mitchell, Tom M. (1997).
383:10.1007/3-540-45813-1_31
348:Artificial Intelligence
267:Formal concept analysis
246:. Although the basic "
427:. Boston: McGraw-Hill.
131:
44:Version space learning
40:
248:candidate elimination
238:Historical background
158:candidate elimination
132:
62:, viewed as a set of
56:binary classification
30:
76:
283:Inductive reasoning
127:
41:
408:10.1109/69.591457
64:logical sentences
16:(Redirected from
458:
451:Machine learning
437:
428:
425:Machine Learning
419:
387:
386:
370:
364:
363:
343:
334:
333:
306:
155:
147:
143:
136:
134:
133:
128:
126:
125:
101:
100:
88:
87:
52:machine learning
21:
466:
465:
461:
460:
459:
457:
456:
455:
441:
440:
431:
422:
393:
390:
372:
371:
367:
345:
344:
337:
330:
310:Russell, Stuart
308:
307:
296:
292:
263:
244:solution search
240:
170:
153:
145:
141:
117:
92:
79:
74:
73:
54:, specifically
23:
22:
15:
12:
11:
5:
464:
462:
454:
453:
443:
442:
439:
438:
429:
420:
402:(2): 336–340.
389:
388:
365:
354:(2): 203–226.
335:
329:978-0137903955
328:
293:
291:
288:
287:
286:
280:
274:
269:
262:
259:
239:
236:
169:
166:
138:
137:
124:
120:
116:
113:
110:
107:
104:
99:
95:
91:
86:
82:
24:
18:Version spaces
14:
13:
10:
9:
6:
4:
3:
2:
463:
452:
449:
448:
446:
435:
430:
426:
421:
417:
413:
409:
405:
401:
397:
392:
391:
384:
380:
376:
369:
366:
361:
357:
353:
349:
342:
340:
336:
331:
325:
321:
320:
315:
314:Norvig, Peter
311:
305:
303:
301:
299:
295:
289:
284:
281:
278:
275:
273:
270:
268:
265:
264:
260:
258:
256:
251:
249:
245:
237:
235:
231:
228:
223:
221:
217:
213:
209:
204:
202:
198:
194:
190:
189:feature space
186:
181:
179:
175:
174:most specific
167:
165:
163:
162:version space
159:
151:
122:
118:
114:
111:
108:
105:
102:
97:
93:
89:
84:
80:
72:
71:
70:
69:
65:
61:
57:
53:
49:
45:
38:
34:
29:
19:
433:
424:
399:
395:
374:
368:
351:
347:
317:
254:
252:
247:
241:
232:
226:
224:
219:
215:
211:
207:
205:
200:
196:
192:
184:
182:
178:most general
177:
173:
171:
161:
157:
150:inconsistent
139:
50:approach to
43:
42:
36:
32:
68:disjunction
290:References
60:hypotheses
316:(2003) .
277:Rough set
115:∨
103:∨
90:∨
445:Category
416:29926783
261:See also
255:collapse
220:negative
216:negative
201:positive
197:positive
37:specific
212:include
193:exclude
48:logical
33:general
414:
326:
412:S2CID
152:with
46:is a
324:ISBN
404:doi
379:doi
356:doi
227:all
447::
410:.
398:.
352:18
350:.
338:^
312:;
297:^
285:.
279:.
214:a
208:GB
195:a
185:SB
164:.
418:.
406::
400:9
385:.
381::
362:.
358::
332:.
154:x
146:x
142:n
123:n
119:H
112:.
109:.
106:.
98:2
94:H
85:1
81:H
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
