Knowledge (XXG)

Shattered set

Source 📝

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

Index

Shattering (machine learning)
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

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

↑