{"entities":{"Q809614":{"pageid":811462,"ns":120,"title":"Item:Q809614","lastrevid":42709226,"modified":"2025-07-08T17:35:10Z","type":"item","id":"Q809614","labels":{"en":{"language":"en","value":"Learnability with respect to fixed distributions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4213475"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809614$488B3A9F-852F-4077-9AAE-9A38849DD9FE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2e037ad9a3f0e4207d6a7243ba7197f81b5c5784","datavalue":{"value":{"text":"Learnability with respect to fixed distributions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q809614$8968B424-ED61-451F-8D3D-DAFD58046ECD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e5d65cce28f2b2fd8ad725c60b942e0971dd1132","datavalue":{"value":"0733.68066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809614$785B0036-773A-4768-96DF-8A733F6CB8ED","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9ba74d7b72bf710d3281466f401fc1f0973e3703","datavalue":{"value":"10.1016/0304-3975(91)90026-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809614$FF0CF610-C285-4C7D-9255-23081236C1DB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b47a9d55bf9a54a1b2f60b334a18eb90271afd10","datavalue":{"value":{"entity-type":"item","numeric-id":809613,"id":"Q809613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809614$A32138DD-55C8-46DA-8593-8C7AD090755A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"768e033f31190cbaea0944ac118f8a6cb545c066","datavalue":{"value":{"entity-type":"item","numeric-id":294682,"id":"Q294682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809614$E2E7A5AD-40D5-47E0-ADAE-B4D92A5849BD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809614$A2C43F6C-5BFB-419A-AD7F-E696EF55F068","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q809614$13593D56-E9CC-4BB2-8C9D-925D9DF933C7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4bf84adb7052453c0d06a42a99bdc55b05806354","datavalue":{"value":"Let D be a distribution over a set X (X is finite, countable or \\(\\subseteq E^ r)\\), \\(C\\subseteq 2^ X-a\\) concept class. For \\(x\\in X^ 1\\), \\(1\\geq 1\\) and a concept \\(c\\in C\\) the 1-sample of c is \\(sam_ c(x)=(<x_ 1,I(x_ 1)>,...,<x_ 1,I(x_ 1)>)\\), where \\(I_ c(x_ j)=1\\) if \\(x_ j\\in C\\) and \\(I_ c(x_ j)=0\\) otherwise. The sample space \\(S_ c\\) is the set of all l-samples of c over all \\(c\\in C\\) and \\(1\\geq 1\\). For an algebra H of Borel sets over X let \\(F_{CH}\\) be the set of all functions \\(f:S_ c\\to H\\). The concept class C is learnable with respect (w.r.) to distribution D (over X) in terms of H if there exists a function \\(f\\in F_{CH}\\) such that for all \\(\\epsilon,\\delta >0\\) there exists \\(1>0\\) such that for every \\(c\\in C\\) and every \\(x\\in X^ 1\\) selected according to D, \\(f(sam_ c(x))\\) and c are \\(\\epsilon\\)-close w.r. to D with probability at least 1-\\(\\delta\\) \\((Y_ 1,Y_ 2\\) are \\(\\epsilon\\)-close w.r. to D if \\(\\Pr_ D(Y_ 1\\oplus Y_ 2)<\\epsilon\\), where \\(\\oplus\\) denotes the symmetric difference). A set \\(H_{\\epsilon}\\subseteq 2^ X\\) is an \\(\\epsilon\\)-cover of C w.r. to D if for every \\(c\\in C\\) there is an \\(h\\in H_{\\epsilon}\\) which is \\(\\epsilon\\)- close to c. C is finitely coverable w.r. to D if for every \\(\\epsilon >0\\) there is a finite \\(\\epsilon\\)-cover of C.    It is proved that C is learnable w.r. to D iff C is finitely coverable w.r. to D. A connection is established between the size of the cover and the Vapnik-Chervonenkis dimension of the concept class. Learning with errors (i.e. if labels in samples are independently correct with probability \\(\\zeta >0.5)\\) is considered also.","type":"string"},"datatype":"string"},"type":"statement","id":"Q809614$0DBC0DBE-972B-4A57-8E79-B0B3D61B69BF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cfe779e91fe9c53ee133568259955801965765ae","datavalue":{"value":"68T05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809614$44539C1E-B6C8-4534-B925-A22F0CCCE924","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"665fc2702192f4fbe702862f428364a48d197770","datavalue":{"value":"4213475","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809614$47B91665-268F-4D53-8ABC-87496A88E843","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f46069d3cc3c8a32a7c415ea2f166da26cf9f70","datavalue":{"value":"machine-learning","type":"string"},"datatype":"string"},"type":"statement","id":"Q809614$50984FAA-79CA-41D1-B9F7-F13989701A0E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4e1df29911c330da2d8d89435a35b182dae9e523","datavalue":{"value":{"entity-type":"item","numeric-id":589408,"id":"Q589408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809614$83A81046-72F1-438B-9405-AC1BAF7A8C92","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809614$86494DD5-1EA5-4A31-A58B-981569BAE3EF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"83c6293f25e8bc7e1747aa6978fc2fd52b5104b6","datavalue":{"value":{"entity-type":"item","numeric-id":1141153,"id":"Q1141153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809614$EC4E9E0B-17EE-4B3F-99D6-DD8EAE884B90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d22ca44b5be34ff406c2d5da98992eae3e05645","datavalue":{"value":{"entity-type":"item","numeric-id":3795256,"id":"Q3795256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809614$A6062321-3DF8-400D-A088-0359239D3401","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5eceee8709c432551836aeb4f4aa8499755cd2c1","datavalue":{"value":{"entity-type":"item","numeric-id":3474905,"id":"Q3474905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809614$C9B3A679-1983-49F6-84BF-145DDB421FA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1f4496e9c5097df00995c9eacd5b0b3cb6d9ba4","datavalue":{"value":{"entity-type":"item","numeric-id":1108056,"id":"Q1108056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809614$8BB42A21-C246-43BC-AB6C-71654B2C10CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ae46fc46a5f1dd9c91f7372322e8ee112c21fd0","datavalue":{"value":{"entity-type":"item","numeric-id":5798359,"id":"Q5798359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809614$9475A4E7-96BA-445A-8B26-179EC5073282","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cbddb13cb8efcf1db983402e229f3a18f9e4224b","datavalue":{"value":{"entity-type":"item","numeric-id":4016907,"id":"Q4016907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809614$AA55550F-C69F-47FF-9AFE-308EBCCE03FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34866ea766971af89b30adf0e5d6c644f933a12f","datavalue":{"value":{"entity-type":"item","numeric-id":3813320,"id":"Q3813320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809614$C9A7974B-D381-4A4B-9C70-9964C8154706","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e55670eeffeb14e6ce51166fb8470acff9c12ef5","datavalue":{"value":{"entity-type":"item","numeric-id":5660314,"id":"Q5660314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809614$DD5C170E-54C5-4DB6-9874-50A4F88555D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a4339f157b5db47124df1e48c6422ab87d6805d","datavalue":{"value":{"entity-type":"item","numeric-id":3714486,"id":"Q3714486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809614$08D6E697-DEE5-4962-9CA8-F3D4681AF40F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"593f0866bce22ea13bca464c5dc9d85406a37f92","datavalue":{"value":{"entity-type":"item","numeric-id":3334096,"id":"Q3334096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809614$408EF57E-CB9B-4E62-AA70-94E283B3F447","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2086c51c5b451693bc5353982b9574befa9f9a72","datavalue":{"value":{"entity-type":"item","numeric-id":2817618,"id":"Q2817618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e752b833d46a9ecda6badf8784ad7169ef1dbb0","datavalue":{"value":{"amount":"+0.91162485","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q809614$0451A2B3-D3FA-4F65-A302-12897C5EF795","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"572069e698ce34c1b2f815cf37dff48361f73010","datavalue":{"value":{"entity-type":"item","numeric-id":4507039,"id":"Q4507039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3354b8755639fb3cce07f149fcd6ad27f652cefe","datavalue":{"value":{"amount":"+0.9110668","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q809614$4BEF4CBF-926C-48C5-A0E1-551B09504319","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ddafcc8a24c4d36e24169152c93d0644ad2af9ce","datavalue":{"value":{"entity-type":"item","numeric-id":3974877,"id":"Q3974877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4e3a9e290d6532b21a01b1c09d3fb18f414c18b","datavalue":{"value":{"amount":"+0.8973894","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q809614$D1E6FD0C-8042-46C2-B010-2D5C2C12C9FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23dc0f00bdd4fd94053080684bb35d5ea30e8cf1","datavalue":{"value":{"entity-type":"item","numeric-id":1929721,"id":"Q1929721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"501577505455f0afaa5d47df161471103f7b0802","datavalue":{"value":{"amount":"+0.88499993","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q809614$C3B5298E-AC03-4A9D-98E7-BE926C45E4BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"412a56b419f0fa4772024c551deda9ea7247aa15","datavalue":{"value":{"entity-type":"item","numeric-id":1364775,"id":"Q1364775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8fbd61f6ae02a5e3282fe99569220bf42aa18d6f","datavalue":{"value":{"amount":"+0.8844889","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q809614$2BAF3E78-930E-48A8-BAB0-02CBBCFE24C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5439dee81552412d33652e773f67690cbb0684b5","datavalue":{"value":{"entity-type":"item","numeric-id":3174075,"id":"Q3174075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8cd2a6c3d9f86e1df783e26ace03a34944cd493","datavalue":{"value":{"amount":"+0.8838272","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q809614$77332A8B-5DD5-4326-9CFC-69F26C276968","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6fecd9279ab4d755f9b92215c0809ca6f60a659c","datavalue":{"value":{"entity-type":"item","numeric-id":2896159,"id":"Q2896159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d55bf82a40e32db164286733eaac28ece7b6a9a1","datavalue":{"value":{"amount":"+0.8820792","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q809614$1C25DBE3-F27E-47C7-921B-6472B546CD11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"444798a637a5da3ef3a98181059feb7c8df2cb84","datavalue":{"value":{"entity-type":"item","numeric-id":1784951,"id":"Q1784951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"895eab2c2b99e2d7451f2db5baeb5db1a257bc72","datavalue":{"value":{"amount":"+0.8788352","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q809614$E9F5BECB-06A3-409B-8BD6-F4A80BEC382F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:809614","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:809614"}}}}}