DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kim, Daesung | ko |
dc.contributor.author | Chung, Hye Won | ko |
dc.date.accessioned | 2021-07-13T05:10:17Z | - |
dc.date.available | 2021-07-13T05:10:17Z | - |
dc.date.created | 2021-07-13 | - |
dc.date.created | 2021-07-13 | - |
dc.date.created | 2021-07-13 | - |
dc.date.issued | 2021-07 | - |
dc.identifier.citation | IEEE TRANSACTIONS ON INFORMATION THEORY, v.67, no.7, pp.4588 - 4612 | - |
dc.identifier.issn | 0018-9448 | - |
dc.identifier.uri | http://hdl.handle.net/10203/286556 | - |
dc.description.abstract | We consider a query-based data acquisition problem for binary classification of unknown labels, which has diverse applications in communications, crowdsourcing, recommender systems and active learning. To ensure reliable recovery of unknown labels with as few number of queries as possible, we consider an effective query type that asks "group attribute" of a chosen subset of objects. In particular, we consider the problem of classifying m binary labels with XOR queries that ask whether the number of objects having a given attribute in the chosen subset of size d is even or odd. The subset size d, which we call query degree, can be varying over queries. We consider a general noise model where the accuracy of answers on queries changes depending both on the worker (the data provider) and query degree d. For this general model, we characterize the information-theoretic limit on the optimal number of queries to reliably recover m labels in terms of a given combination of degree-d queries and noise parameters. Further, we propose an efficient inference algorithm that achieves this limit even when the noise parameters are unknown. | - |
dc.language | English | - |
dc.publisher | IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC | - |
dc.title | Binary Classification With XOR Queries: Fundamental Limits and an Efficient Algorithm | - |
dc.type | Article | - |
dc.identifier.wosid | 000663524000020 | - |
dc.identifier.scopusid | 2-s2.0-85105578926 | - |
dc.type.rims | ART | - |
dc.citation.volume | 67 | - |
dc.citation.issue | 7 | - |
dc.citation.beginningpage | 4588 | - |
dc.citation.endingpage | 4612 | - |
dc.citation.publicationname | IEEE TRANSACTIONS ON INFORMATION THEORY | - |
dc.identifier.doi | 10.1109/TIT.2021.3077461 | - |
dc.contributor.localauthor | Chung, Hye Won | - |
dc.contributor.nonIdAuthor | Kim, Daesung | - |
dc.description.isOpenAccess | N | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | Binary classification | - |
dc.subject.keywordAuthor | XOR query | - |
dc.subject.keywordAuthor | sample complexity | - |
dc.subject.keywordAuthor | message passing | - |
dc.subject.keywordAuthor | weighted majority voting | - |
dc.subject.keywordPlus | CODES | - |
dc.subject.keywordPlus | THRESHOLD | - |
dc.subject.keywordPlus | RECOVERY | - |
dc.subject.keywordPlus | CAPACITY | - |
dc.subject.keywordPlus | CHANNEL | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.