Knowledge

Shattered set

Source 📝

374: 306: 294: 358: 282: 256:. First, we draw a disc around the subsets of each isolated point. Next, we try to draw a disc around every subset of point pairs. This turns out to be doable for adjacent points, but impossible for points on opposite sides of the circle. Any attempt to include those points on the opposite side will necessarily include other points not in that pair. Hence, any pair of opposite points cannot be isolated out of 233: 661: 351:, we find that we can still isolate all the subsets from above, as well as the points that were formerly problematic. Thus, this specific set of 4 points is shattered by the class of elliptical discs. Visualized below: 489: 1709: 1603: 753: 956:, then S_C(3) would only be 7. If none of those sets can be obtained, S_C(3) would be 0. Additionally, if S_C(2)=3, for example, then there is an element in the set of all 2-point sets from 1126: 684: 1775: 1152: 1061: 1339: 1264: 446: 1896: 1832: 1204: 373: 305: 126: 1009: 795: 1502: 1365: 921: 880: 466: 1290: 1465: 1430: 293: 950: 847: 357: 1471:
gets smaller, there are fewer sets that could be omitted. The extreme of this is S_C(0) (the shattering coefficient of the empty set), which must always be
281: 656:{\displaystyle S_{C}(n)=\max _{\forall x_{1},x_{2},\dots ,x_{n}\in \Omega }\operatorname {card} \{\,\{\,x_{1},x_{2},\dots ,x_{n}\}\cap s,s\in C\}} 2056: 1614: 1518: 388:
With a bit of thought, we could generalize that any set of finite points on a unit circle could be shattered by the class of all
28: 1954: 36: 693: 1993: 1922: 1070: 2051: 1777:. The VC dimension is usually defined as VC_0, the largest cardinality of points chosen that will still shatter 19:
A class of sets is said to shatter another set if it is possible to "pick out" any element of that set using
182:
to refer to a "class" or "collection" of sets, as in a Vapnik–Chervonenkis class (VC-class). The set
1934: 669: 1998: 1717: 1436:
gets larger, there are more sets that could be missed. Alternatively, there is also a largest value of
1131: 1017: 1295: 1220: 425: 2035: 1852: 1788: 1160: 190:
because, in empirical processes, we are interested in the shattering of finite sets of data points.
2017: 60: 96: 1989: 1977: 978: 764: 52: 32: 1474: 1344: 972:) because we have already located a "missing" set in the smaller power set of 2-point sets. 893: 852: 451: 2007: 1963: 1269: 203: 1443: 1408: 336:. And, with a bit of thought, we can prove that no set of four points is shattered by this 926: 823: 401: 199: 140: 1938: 2045: 1968: 1505: 1388: 469: 20: 1952:
Wencour, R. S.; Dudley, R. M. (1981), "Some special Vapnik–Chervonenkis classes",
240:
of four particular points on the unit circle (the unit circle is shown in purple).
299:
Each subset of adjacent points can be isolated with a disc (showing one of four).
687: 215: 207: 389: 211: 187: 2012: 31:, also known as VC-theory. Shattering and VC-theory are used in the study of 148: 232: 206:(two-dimensional space) does not shatter every set of four points on the 2021: 1704:{\displaystyle VC_{0}(C)={\underset {n}{\max }}\{n:S_{C}(n)=2^{n}\}.\,} 1598:{\displaystyle VC(C)={\underset {n}{\min }}\{n:S_{C}(n)<2^{n}\}\,} 287:
Each individual point can be isolated with a disc (showing all four).
964:. It follows from this that S_C(3) would also be less than 8 (i.e. 231: 890:, its shattering coefficient(3) would be 8 and S_C(2) would be 252:, we attempt to draw a disc around every subset of points in 311:
A subset of points on opposite sides of the unit circle can
214:
in the plane does shatter every finite set of points on the
1984:, Ph.D. thesis, Stanford University, Mathematics Department 383:
is also separable by some ellipse (showing one of four)
1379:
then it can not shatter sets of larger cardinalities.
367:
are now separable by some ellipse (showing one of two)
1855: 1791: 1720: 1617: 1521: 1504:. These statements lends themselves to defining the 1477: 1446: 1411: 1347: 1298: 1272: 1223: 1163: 1134: 1073: 1020: 981: 929: 896: 855: 826: 767: 696: 672: 492: 454: 428: 99: 1994:"Empirical discrepancies and subadditive processes" 748:{\displaystyle x_{1},x_{2},\dots ,x_{n}\in \Omega } 225:be a set of four points on the unit circle and let 1890: 1826: 1769: 1703: 1597: 1496: 1459: 1424: 1359: 1333: 1284: 1258: 1198: 1146: 1120: 1055: 1003: 944: 915: 874: 841: 789: 747: 678: 655: 460: 440: 120: 1405:that makes the shatter coefficient(n) less than 1121:{\displaystyle \{s\cap A|s\in C\}\subseteq P(A)} 960:that cannot be obtained from intersections with 516: 1909:A class with finite VC dimension is called a 8: 1982:Combinatorial Entropy and Uniform Limit Laws 1694: 1653: 1591: 1550: 1100: 1074: 975:This example illustrates some properties of 952:cannot be obtained through intersections in 797:is the largest number of subsets of any set 650: 629: 583: 579: 1206:, that means there is a set of cardinality 805:points that can be formed by intersecting 2011: 1967: 1882: 1860: 1854: 1818: 1796: 1790: 1746: 1719: 1700: 1688: 1666: 1643: 1625: 1616: 1594: 1585: 1563: 1540: 1520: 1482: 1476: 1451: 1445: 1416: 1410: 1346: 1325: 1303: 1297: 1271: 1250: 1228: 1222: 1190: 1168: 1162: 1133: 1086: 1072: 1047: 1025: 1019: 986: 980: 928: 901: 895: 860: 854: 825: 772: 766: 733: 714: 701: 695: 671: 623: 604: 591: 586: 582: 559: 540: 527: 519: 497: 491: 453: 427: 406:To quantify the richness of a collection 98: 1941:to the size of its largest shattered set 353: 320:Because there is some subset which can 277: 2036:Origin of "Shattered sets" terminology 1375:cannot shatter any set of cardinality 679:{\displaystyle \operatorname {card} } 7: 1401:, there will be a smallest value of 923:. However, if one of those sets in 1902:and the VC dimension of this class 198:We will show that the class of all 1770:{\displaystyle VC(C)=VC_{0}(C)+1.} 1147:{\displaystyle A\subseteq \Omega } 1141: 1056:{\displaystyle S_{C}(n)\leq 2^{n}} 820:contains 3 points, its power set, 742: 568: 520: 455: 435: 14: 1925:if and only if it is a VC class. 1923:uniformly Glivenko–Cantelli 1371:The third property means that if 1334:{\displaystyle S_{C}(n)<2^{n}} 1259:{\displaystyle S_{C}(N)<2^{N}} 392:(visualize connecting the dots). 1937:, relating the cardinality of a 441:{\displaystyle s\subset \Omega } 372: 356: 304: 292: 280: 29:Vapnik–Chervonenkis theory 16:Notion in computational learning 1911:Vapnik–Chervonenkis class 1383:Vapnik–Chervonenkis class 410:of sets, we use the concept of 379:Each subset of three points in 260:using intersections with class 1891:{\displaystyle S_{C}(n)=2^{n}} 1872: 1866: 1841:there is a set of cardinality 1827:{\displaystyle S_{C}(n)=2^{n}} 1808: 1802: 1758: 1752: 1733: 1727: 1678: 1672: 1637: 1631: 1575: 1569: 1534: 1528: 1440:for which the S_C(n) is still 1315: 1309: 1240: 1234: 1199:{\displaystyle S_{C}(n)=2^{n}} 1180: 1174: 1115: 1109: 1087: 1037: 1031: 998: 992: 939: 933: 836: 830: 784: 778: 509: 503: 1: 2057:Computational learning theory 37:computational learning theory 1969:10.1016/0012-365X(81)90274-0 1210:, which can be shattered by 809:with the sets in collection 1645: 1542: 324:be isolated by any disc in 229:be the class of all discs. 27:plays an important role in 2073: 1845:which can be shattered by 1837:Altneratively, if for any 1386: 468:being any space, often a 399: 121:{\displaystyle a=c\cap A.} 35:as well as in statistical 1004:{\displaystyle S_{C}(n)} 790:{\displaystyle S_{C}(n)} 343:However, if we redefine 328:, we conclude then that 315:be isolated with a disc. 82:, there is some element 1497:{\displaystyle 2^{0}=1} 1397:cannot be shattered by 1360:{\displaystyle n\geq N} 916:{\displaystyle 2^{2}=4} 875:{\displaystyle 2^{3}=8} 461:{\displaystyle \Omega } 412:shattering coefficients 347:to be the class of all 210:, yet the class of all 186:is often assumed to be 2013:10.1214/aop/1176995615 1892: 1828: 1771: 1705: 1608:or, alternatively, as 1599: 1498: 1461: 1426: 1361: 1335: 1286: 1285:{\displaystyle N>1} 1260: 1200: 1148: 1122: 1057: 1005: 946: 917: 876: 843: 791: 749: 680: 657: 477:shattering coefficient 462: 442: 241: 178:We employ the letter 122: 1999:Annals of Probability 1893: 1829: 1772: 1706: 1600: 1499: 1462: 1460:{\displaystyle 2^{n}} 1427: 1425:{\displaystyle 2^{n}} 1362: 1336: 1287: 1261: 1201: 1149: 1123: 1058: 1006: 947: 918: 877: 844: 792: 750: 681: 658: 463: 443: 275:As visualized below: 235: 123: 1955:Discrete Mathematics 1853: 1789: 1718: 1615: 1519: 1475: 1444: 1409: 1345: 1296: 1270: 1221: 1161: 1132: 1071: 1018: 979: 945:{\displaystyle P(A)} 927: 894: 853: 842:{\displaystyle P(A)} 824: 816:For example, if set 765: 694: 670: 490: 452: 426: 418:). For a collection 332:is not shattered by 97: 414:(also known as the 396:Shatter coefficient 363:Opposite points of 74:if for each subset 63:of sets. The class 33:empirical processes 1935:Sauer–Shelah lemma 1888: 1824: 1767: 1701: 1651: 1595: 1548: 1494: 1457: 1422: 1357: 1331: 1282: 1256: 1196: 1144: 1118: 1053: 1001: 968:would not shatter 942: 913: 872: 839: 787: 745: 676: 653: 572: 458: 438: 242: 118: 2052:Empirical process 1644: 1541: 515: 472:, we define the 268:does not shatter 23:. The concept of 2064: 2024: 2015: 1985: 1972: 1971: 1897: 1895: 1894: 1889: 1887: 1886: 1865: 1864: 1833: 1831: 1830: 1825: 1823: 1822: 1801: 1800: 1776: 1774: 1773: 1768: 1751: 1750: 1710: 1708: 1707: 1702: 1693: 1692: 1671: 1670: 1652: 1630: 1629: 1604: 1602: 1601: 1596: 1590: 1589: 1568: 1567: 1549: 1503: 1501: 1500: 1495: 1487: 1486: 1466: 1464: 1463: 1458: 1456: 1455: 1431: 1429: 1428: 1423: 1421: 1420: 1366: 1364: 1363: 1358: 1340: 1338: 1337: 1332: 1330: 1329: 1308: 1307: 1291: 1289: 1288: 1283: 1265: 1263: 1262: 1257: 1255: 1254: 1233: 1232: 1205: 1203: 1202: 1197: 1195: 1194: 1173: 1172: 1153: 1151: 1150: 1145: 1127: 1125: 1124: 1119: 1090: 1062: 1060: 1059: 1054: 1052: 1051: 1030: 1029: 1010: 1008: 1007: 1002: 991: 990: 951: 949: 948: 943: 922: 920: 919: 914: 906: 905: 881: 879: 878: 873: 865: 864: 848: 846: 845: 840: 796: 794: 793: 788: 777: 776: 754: 752: 751: 746: 738: 737: 719: 718: 706: 705: 685: 683: 682: 677: 662: 660: 659: 654: 628: 627: 609: 608: 596: 595: 571: 564: 563: 545: 544: 532: 531: 502: 501: 467: 465: 464: 459: 447: 445: 444: 439: 376: 360: 349:elliptical discs 308: 296: 284: 127: 125: 124: 119: 2072: 2071: 2067: 2066: 2065: 2063: 2062: 2061: 2042: 2041: 2032: 1988: 1976: 1951: 1948: 1931: 1878: 1856: 1851: 1850: 1814: 1792: 1787: 1786: 1742: 1716: 1715: 1684: 1662: 1621: 1613: 1612: 1581: 1559: 1517: 1516: 1478: 1473: 1472: 1447: 1442: 1441: 1412: 1407: 1406: 1391: 1385: 1343: 1342: 1321: 1299: 1294: 1293: 1268: 1267: 1246: 1224: 1219: 1218: 1186: 1164: 1159: 1158: 1130: 1129: 1069: 1068: 1043: 1021: 1016: 1015: 982: 977: 976: 925: 924: 897: 892: 891: 856: 851: 850: 822: 821: 768: 763: 762: 729: 710: 697: 692: 691: 690:of the set and 668: 667: 619: 600: 587: 555: 536: 523: 493: 488: 487: 450: 449: 424: 423: 416:growth function 404: 402:growth function 398: 384: 377: 368: 361: 316: 309: 300: 297: 288: 285: 196: 95: 94: 45: 17: 12: 11: 5: 2070: 2068: 2060: 2059: 2054: 2044: 2043: 2040: 2039: 2038:, by J. Steele 2031: 2030:External links 2028: 2027: 2026: 2006:(1): 118–227, 1986: 1974: 1962:(3): 313–318, 1947: 1944: 1943: 1942: 1939:family of sets 1930: 1927: 1885: 1881: 1877: 1874: 1871: 1868: 1863: 1859: 1821: 1817: 1813: 1810: 1807: 1804: 1799: 1795: 1766: 1763: 1760: 1757: 1754: 1749: 1745: 1741: 1738: 1735: 1732: 1729: 1726: 1723: 1712: 1711: 1699: 1696: 1691: 1687: 1683: 1680: 1677: 1674: 1669: 1665: 1661: 1658: 1655: 1650: 1647: 1642: 1639: 1636: 1633: 1628: 1624: 1620: 1606: 1605: 1593: 1588: 1584: 1580: 1577: 1574: 1571: 1566: 1562: 1558: 1555: 1552: 1547: 1544: 1539: 1536: 1533: 1530: 1527: 1524: 1493: 1490: 1485: 1481: 1454: 1450: 1419: 1415: 1387:Main article: 1384: 1381: 1369: 1368: 1356: 1353: 1350: 1328: 1324: 1320: 1317: 1314: 1311: 1306: 1302: 1281: 1278: 1275: 1253: 1249: 1245: 1242: 1239: 1236: 1231: 1227: 1215: 1193: 1189: 1185: 1182: 1179: 1176: 1171: 1167: 1155: 1143: 1140: 1137: 1117: 1114: 1111: 1108: 1105: 1102: 1099: 1096: 1093: 1089: 1085: 1082: 1079: 1076: 1050: 1046: 1042: 1039: 1036: 1033: 1028: 1024: 1000: 997: 994: 989: 985: 941: 938: 935: 932: 912: 909: 904: 900: 882:elements. If 871: 868: 863: 859: 838: 835: 832: 829: 786: 783: 780: 775: 771: 755:is any set of 744: 741: 736: 732: 728: 725: 722: 717: 713: 709: 704: 700: 675: 664: 663: 652: 649: 646: 643: 640: 637: 634: 631: 626: 622: 618: 615: 612: 607: 603: 599: 594: 590: 585: 581: 578: 575: 570: 567: 562: 558: 554: 551: 548: 543: 539: 535: 530: 526: 522: 518: 514: 511: 508: 505: 500: 496: 457: 437: 434: 431: 400:Main article: 397: 394: 386: 385: 378: 371: 369: 362: 355: 318: 317: 310: 303: 301: 298: 291: 289: 286: 279: 244:To test where 195: 192: 131:Equivalently, 129: 128: 117: 114: 111: 108: 105: 102: 44: 41: 25:shattered sets 15: 13: 10: 9: 6: 4: 3: 2: 2069: 2058: 2055: 2053: 2050: 2049: 2047: 2037: 2034: 2033: 2029: 2023: 2019: 2014: 2009: 2005: 2001: 2000: 1995: 1991: 1990:Steele, J. M. 1987: 1983: 1979: 1978:Steele, J. M. 1975: 1970: 1965: 1961: 1957: 1956: 1950: 1949: 1945: 1940: 1936: 1933: 1932: 1928: 1926: 1924: 1920: 1916: 1912: 1907: 1906:is infinite. 1905: 1901: 1883: 1879: 1875: 1869: 1861: 1857: 1848: 1844: 1840: 1835: 1819: 1815: 1811: 1805: 1797: 1793: 1784: 1780: 1764: 1761: 1755: 1747: 1743: 1739: 1736: 1730: 1724: 1721: 1697: 1689: 1685: 1681: 1675: 1667: 1663: 1659: 1656: 1648: 1640: 1634: 1626: 1622: 1618: 1611: 1610: 1609: 1586: 1582: 1578: 1572: 1564: 1560: 1556: 1553: 1545: 1537: 1531: 1525: 1522: 1515: 1514: 1513: 1511: 1507: 1491: 1488: 1483: 1479: 1470: 1467:, because as 1452: 1448: 1439: 1435: 1417: 1413: 1404: 1400: 1396: 1390: 1382: 1380: 1378: 1374: 1354: 1351: 1348: 1326: 1322: 1318: 1312: 1304: 1300: 1279: 1276: 1273: 1251: 1247: 1243: 1237: 1229: 1225: 1216: 1213: 1209: 1191: 1187: 1183: 1177: 1169: 1165: 1156: 1138: 1135: 1112: 1106: 1103: 1097: 1094: 1091: 1083: 1080: 1077: 1066: 1048: 1044: 1040: 1034: 1026: 1022: 1014: 1013: 1012: 995: 987: 983: 973: 971: 967: 963: 959: 955: 936: 930: 910: 907: 902: 898: 889: 885: 869: 866: 861: 857: 833: 827: 819: 814: 812: 808: 804: 800: 781: 773: 769: 760: 758: 739: 734: 730: 726: 723: 720: 715: 711: 707: 702: 698: 689: 673: 647: 644: 641: 638: 635: 632: 624: 620: 616: 613: 610: 605: 601: 597: 592: 588: 576: 573: 565: 560: 556: 552: 549: 546: 541: 537: 533: 528: 524: 512: 506: 498: 494: 486: 485: 484: 482: 478: 475: 471: 432: 429: 421: 417: 413: 409: 403: 395: 393: 391: 382: 375: 370: 366: 359: 354: 352: 350: 346: 341: 339: 335: 331: 327: 323: 314: 307: 302: 295: 290: 283: 278: 276: 273: 271: 267: 263: 259: 255: 251: 247: 239: 234: 230: 228: 224: 219: 217: 213: 209: 205: 201: 193: 191: 189: 185: 181: 176: 174: 170: 166: 162: 158: 154: 150: 146: 142: 138: 134: 115: 112: 109: 106: 103: 100: 93: 92: 91: 89: 85: 81: 77: 73: 69: 66: 62: 58: 54: 50: 42: 40: 38: 34: 30: 26: 22: 2003: 1997: 1981: 1959: 1953: 1918: 1914: 1910: 1908: 1903: 1899: 1846: 1842: 1838: 1836: 1782: 1778: 1713: 1607: 1509: 1506:VC dimension 1468: 1437: 1433: 1402: 1398: 1394: 1392: 1389:VC dimension 1376: 1372: 1370: 1211: 1207: 1064: 974: 969: 965: 961: 957: 953: 887: 883: 817: 815: 810: 806: 802: 798: 761: 756: 686:denotes the 665: 480: 476: 473: 470:sample space 419: 415: 411: 407: 405: 387: 380: 364: 348: 344: 342: 337: 333: 329: 325: 321: 319: 312: 274: 269: 265: 261: 257: 253: 249: 245: 243: 237: 226: 222: 220: 197: 183: 179: 177: 172: 168: 164: 160: 156: 152: 144: 143:is equal to 141:intersection 136: 132: 130: 87: 83: 79: 75: 71: 67: 64: 56: 48: 46: 24: 21:intersection 18: 1508:of a class 1432:because as 849:, contains 759:points,. 688:cardinality 390:convex sets 216:unit circle 212:convex sets 208:unit circle 139:when their 2046:Categories 1946:References 1917:. A class 1785:such that 1714:Note that 90:such that 43:Definition 1352:≥ 1266:for some 1142:Ω 1139:⊆ 1104:⊆ 1095:∈ 1081:∩ 1041:≤ 886:shatters 743:Ω 740:∈ 724:… 645:∈ 633:∩ 614:… 577:⁡ 569:Ω 566:∈ 550:… 521:∀ 456:Ω 436:Ω 433:⊂ 248:shatters 149:power set 135:shatters 110:∩ 1992:(1978), 1980:(1975), 1929:See also 1915:VC class 1898:for all 1341:for all 1128:for any 1067:because 1063:for all 422:of sets 236:The set 70:the set 68:shatters 47:Suppose 2022:2242865 1849:, then 264:and so 202:in the 194:Example 2020:  1781:(i.e. 666:where 188:finite 159:) = { 2018:JSTOR 1292:then 204:plane 200:discs 61:class 59:is a 51:is a 1579:< 1512:as: 1319:< 1277:> 1244:< 674:card 574:card 221:Let 175:}. 55:and 2008:doi 1964:doi 1921:is 1913:or 1834:). 1646:max 1543:min 1393:If 1217:If 1157:If 813:. 801:of 517:max 483:as 479:of 322:not 313:not 272:. 86:of 78:of 53:set 2048:: 2016:, 2002:, 1996:, 1960:33 1958:, 1765:1. 1011:: 448:, 340:. 218:. 171:∈ 167:| 163:∩ 151:: 147:s 145:A' 39:. 2025:. 2010:: 2004:6 1973:. 1966:: 1919:C 1904:C 1900:n 1884:n 1880:2 1876:= 1873:) 1870:n 1867:( 1862:C 1858:S 1847:C 1843:n 1839:n 1820:n 1816:2 1812:= 1809:) 1806:n 1803:( 1798:C 1794:S 1783:n 1779:A 1762:+ 1759:) 1756:C 1753:( 1748:0 1744:C 1740:V 1737:= 1734:) 1731:C 1728:( 1725:C 1722:V 1698:. 1695:} 1690:n 1686:2 1682:= 1679:) 1676:n 1673:( 1668:C 1664:S 1660:: 1657:n 1654:{ 1649:n 1641:= 1638:) 1635:C 1632:( 1627:0 1623:C 1619:V 1592:} 1587:n 1583:2 1576:) 1573:n 1570:( 1565:C 1561:S 1557:: 1554:n 1551:{ 1546:n 1538:= 1535:) 1532:C 1529:( 1526:C 1523:V 1510:C 1492:1 1489:= 1484:0 1480:2 1469:n 1453:n 1449:2 1438:n 1434:n 1418:n 1414:2 1403:n 1399:C 1395:A 1377:N 1373:C 1367:. 1355:N 1349:n 1327:n 1323:2 1316:) 1313:n 1310:( 1305:C 1301:S 1280:1 1274:N 1252:N 1248:2 1241:) 1238:N 1235:( 1230:C 1226:S 1214:. 1212:C 1208:n 1192:n 1188:2 1184:= 1181:) 1178:n 1175:( 1170:C 1166:S 1154:. 1136:A 1116:) 1113:A 1110:( 1107:P 1101:} 1098:C 1092:s 1088:| 1084:A 1078:s 1075:{ 1065:n 1049:n 1045:2 1038:) 1035:n 1032:( 1027:C 1023:S 999:) 996:n 993:( 988:C 984:S 970:A 966:C 962:C 958:A 954:c 940:) 937:A 934:( 931:P 911:4 908:= 903:2 899:2 888:A 884:C 870:8 867:= 862:3 858:2 837:) 834:A 831:( 828:P 818:A 811:C 807:A 803:n 799:A 785:) 782:n 779:( 774:C 770:S 757:n 735:n 731:x 727:, 721:, 716:2 712:x 708:, 703:1 699:x 651:} 648:C 642:s 639:, 636:s 630:} 625:n 621:x 617:, 611:, 606:2 602:x 598:, 593:1 589:x 584:{ 580:{ 561:n 557:x 553:, 547:, 542:2 538:x 534:, 529:1 525:x 513:= 510:) 507:n 504:( 499:C 495:S 481:C 474:n 430:s 420:C 408:C 381:A 365:A 345:C 338:C 334:C 330:A 326:C 270:A 266:C 262:C 258:A 254:A 250:A 246:C 238:A 227:C 223:A 184:A 180:C 173:C 169:c 165:A 161:c 157:A 155:( 153:P 137:A 133:C 116:. 113:A 107:c 104:= 101:a 88:C 84:c 80:A 76:a 72:A 65:C 57:C 49:A

Index

intersection
Vapnik–Chervonenkis theory
empirical processes
computational learning theory
set
class
intersection
power set
finite
discs
plane
unit circle
convex sets
unit circle

Each individual point can be isolated with a disc (showing all four).
Each subset of adjacent points can be isolated with a disc (showing one of four).
A subset of points on opposite sides of the unit circle can not be isolated with a disc.
Opposite points of A are now separable by some ellipse (showing one of two)
Each subset of three points in A is also separable by some ellipse (showing one of four)
convex sets
growth function
sample space
cardinality
VC dimension
VC dimension
uniformly Glivenko–Cantelli
Sauer–Shelah lemma
family of sets
Discrete Mathematics

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

↑