More Web Proxy on the site http://driver.im/

research-article

Public Access

Water from Two Rocks: Maximizing the Mutual Information

Authors:

Grant SchoenebeckAuthors Info & Claims

EC '18: Proceedings of the 2018 ACM Conference on Economics and Computation

Pages 177 - 194

https://doi.org/10.1145/3219166.3219194

Published: 11 June 2018 Publication History

Abstract

We build a natural connection between the learning problem, co-training, and forecast elicitation without verification (related to peer-prediction) and address them simultaneously using the same information theoretic approach. In co-training/multiview learning, the goal is to aggregate two views of data into a prediction for a latent label. We show how to optimally combine two views of data by reducing the problem to an optimization problem. Our work gives a unified and rigorous approach to the general setting. In forecast elicitation without verification we seek to design a mechanism that elicits high quality forecasts from agents in the setting where the mechanism does not have access to the ground truth. By assuming the agents' information is independent conditioning on the outcome, we propose mechanisms where truth-telling is a strict equilibrium for both the single-task and multi-task settings. Our multi-task mechanism additionally has the property that the truth-telling equilibrium pays better than any other strategy profile and strictly better than any other "non-permutation" strategy profile.

Supplementary Material

MP4 File (p177.mp4)

Download
469.56 MB

References

[1]

Arpit Agarwal and Shivani Agarwal. 2015. On consistent surrogate risk minimization and property elicitation Conference on Learning Theory. 4--22.

[2]

Syed Mumtaz Ali and Samuel D Silvey. 1966. A general class of coefficients of divergence of one distribution from another. Journal of the Royal Statistical Society. Series B (Methodological) (1966), 131--142.

[3]

Suzanna Becker. 1996. Mutual information maximization: models of cortical self-organization. Network: Computation in neural systems Vol. 7, 1 (1996), 7--31.

[4]

Anthony J Bell and Terrence J Sejnowski. 1995. An information-maximization approach to blind separation and blind deconvolution. Neural computation Vol. 7, 6 (1995), 1129--1159.

Digital Library

[5]

Avrim Blum and Tom Mitchell. 1998. Combining labeled and unlabeled data with co-training Proceedings of the eleventh annual conference on Computational learning theory. ACM, 92--100.

Digital Library

[6]

J-F Cardoso. 1997. Infomax and maximum likelihood for blind source separation. IEEE Signal processing letters Vol. 4, 4 (1997), 112--114.

[7]

Michael Collins and Yoram Singer. 1999. Unsupervised models for named entity classification 1999 Joint SIGDAT Conference on Empirical Methods in Natural Language Processing and Very Large Corpora.

[8]

Thomas M Cover and Joy A Thomas. 2006. Elements of information theory 2nd edition. (2006).

[9]

Imre Csiszár, Paul C Shields, et almbox. 2004. Information theory and statistics: A tutorial. Foundations and Trends® in Communications and Information Theory Vol. 1, 4 (2004), 417--528.

Digital Library

[10]

Anirban Dasgupta and Arpita Ghosh. 2013. Crowdsourced judgement elicitation with endogenous proficiency Proceedings of the 22nd international conference on World Wide Web. 319--330.

Digital Library

[11]

Sanjoy Dasgupta, Michael L Littman, and David A McAllester. 2002. PAC generalization bounds for co-training. In Advances in neural information processing systems. 375--382.

Digital Library

[12]

A. Gao, J. R. Wright, and K. Leyton-Brown. 2016. Incentivizing Evaluation via Limited Access to Ground Truth: Peer-Prediction Makes Things Worse. ArXiv e-prints (June. 2016). {arxiv}cs.GT/1606.07042

[13]

Tilmann Gneiting and Adrian E Raftery. 2007. Strictly proper scoring rules, prediction, and estimation. J. Amer. Statist. Assoc. Vol. 102, 477 (2007), 359--378.

[14]

Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. 2014. Generative adversarial nets. In Advances in neural information processing systems. 2672--2680.

Digital Library

[15]

Sham M Kakade and Dean P Foster. 2007. Multi-view regression via canonical correlation analysis International Conference on Computational Learning Theory. Springer, 82--96.

Digital Library

[16]

Roni Khardon and Gabriel Wachman. 2007. Noise tolerant variants of the perceptron algorithm. Journal of Machine Learning Research Vol. 8, Feb (2007), 227--248.

Digital Library

[17]

Y. Kong and G. Schoenebeck. 2016. An Information Theoretic Framework For Designing Information Elicitation Mechanisms That Reward Truth-telling. ArXiv e-prints (May. 2016). {arxiv}cs.GT/1605.01021

[18]

Y. Kong and G. Schoenebeck. 2018. Eliciting Expertise without Verification. ArXiv e-prints (Feb. 2018). {arxiv}cs.GT/1802.08312

[19]

Yingming Li, Ming Yang, and Zhongfei Zhang. 2016. Multi-view representation learning: A survey from shallow methods to deep methods. arXiv preprint arXiv:1610.01206 (2016).

[20]

Yang Liu and Yiling Chen. 2017. Machine-Learning Aided Peer Prediction. In Proceedings of the 2017 ACM Conference on Economics and Computation (EC '17). ACM, New York, NY, USA, 63--80.

Digital Library

[21]

Yang Liu and Yiling Chen. 2018. Surrogate Scoring Rules and a Dominant Truth Serum for Information Elicitation. CoRR Vol. abs/1802.09158 (2018). {arxiv}1802.09158 http://arxiv.org/abs/1802.09158

[22]

D. McAllester. 2018. Information Theoretic Co-Training. ArXiv e-prints (Feb. 2018). {arxiv}cs.LG/1802.07572

[23]

N. Miller, P. Resnick, and R. Zeckhauser. 2005. Eliciting informative feedback: The peer-prediction method. Management Science (2005), 1359--1373.

Digital Library

[24]

Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. 2013. Learning with noisy labels. In Advances in neural information processing systems. 1196--1204.

Digital Library

[25]

XuanLong Nguyen, Martin J Wainwright, and Michael I Jordan. 2009. On surrogate loss functions and f-divergences. The Annals of Statistics (2009), 876--904.

[26]

XuanLong Nguyen, Martin J Wainwright, and Michael I Jordan. 2010. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory Vol. 56, 11 (2010), 5847--5861.

Digital Library

[27]

Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. 2016. f-gan: Training generative neural samplers using variational divergence minimization Advances in Neural Information Processing Systems. 271--279.

Digital Library

[28]

D. Prelec. 2004. A Bayesian Truth Serum for subjective data. Science Vol. 306, 5695 (2004), 462--466.

[29]

Alexander J Ratner, Christopher M De Sa, Sen Wu, Daniel Selsam, and Christopher Ré. 2016. Data programming: Creating large training sets, quickly Advances in Neural Information Processing Systems. 3567--3575.

Digital Library

[30]

Vikas C Raykar, Shipeng Yu, Linda H Zhao, Gerardo Hermosillo Valadez, Charles Florin, Luca Bogoni, and Linda Moy. 2010. Learning from crowds. Journal of Machine Learning Research Vol. 11, Apr (2010), 1297--1322.

Digital Library

[31]

R Tyrrell Rockafellar et almbox. 1966. Extension of Fenchel'duality theorem for convex functions. Duke mathematical journal Vol. 33, 1 (1966), 81--89.

[32]

Clayton Scott, Gilles Blanchard, and Gregory Handy. 2013. Classification with asymmetric label noise: Consistency and maximal denoising Conference On Learning Theory. 489--511.

[33]

Victor Shnayder, Arpit Agarwal, Rafael Frongillo, and David C Parkes. 2016. Informed truthfulness in multi-task peer prediction Proceedings of the 2016 ACM Conference on Economics and Computation. ACM, 179--196.

Digital Library

[34]

Sainbayar Sukhbaatar and Rob Fergus. 2014. Learning from noisy labels with deep neural networks. arXiv preprint arXiv:1406.2080 Vol. 2, 3 (2014), 4.

[35]

Robert L Winkler. 1969. Scoring rules and the evaluation of probability assessors. J. Amer. Statist. Assoc. Vol. 64, 327 (1969), 1073--1078.

[36]

Jens Witkowski, Pavel Atanasov, Lyle H Ungar, and Andreas Krause. 2017. Proper Proxy Scoring Rules. In AAAI. 743--749.

[37]

Chang Xu, Dacheng Tao, and Chao Xu. 2013. A survey on multi-view learning. arXiv preprint arXiv:1304.5634 (2013).

[38]

Yuchen Zhang, Xi Chen, Denny Zhou, and Michael I Jordan. 2014. Spectral methods meet EM: A provably optimal algorithm for crowdsourcing Advances in neural information processing systems. 1260--1268.

Digital Library

Cited By

Kong Y(2024)Dominantly Truthful Peer Prediction Mechanisms with a Finite Number of TasksJournal of the ACM10.1145/363823971:2(1-49)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3638239
Xu SZhang YResnick PSchoenebeck GChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Spot Check Equivalence: An Interpretable Metric for Information Elicitation MechanismsProceedings of the ACM Web Conference 202410.1145/3589334.3645679(276-287)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645679
Shan LZhang SZhang JWang ZChua TNgo CKa-Wei Lee RKumar RLauw H(2024)On Truthful Item-Acquiring Mechanisms for Reward MaximizationProceedings of the ACM Web Conference 202410.1145/3589334.3645345(25-35)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645345
Show More Cited By

Index Terms

Water from Two Rocks: Maximizing the Mutual Information
1. Information systems
  1. World Wide Web
    1. Web applications
      1. Crowdsourcing
        Incentive schemes
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design
      1. Algorithmic mechanism design
    2. Machine learning theory
      1. Unsupervised learning and clustering

Recommendations

Dominantly Truthful Peer Prediction Mechanisms with a Finite Number of Tasks
¹ In the setting where participants are asked multiple similar possibly subjective multi-choice questions (e.g., Do you like Panda Express? Y/N; Do you like Chick-fil-A? Y/N), a series of peer prediction mechanisms have been designed to incentivize honest ...
Informed Truthfulness in Multi-Task Peer Prediction
EC '16: Proceedings of the 2016 ACM Conference on Economics and Computation

The problem of peer prediction is to elicit information from agents in settings without any objective ground truth against which to score reports. Peer prediction mechanisms seek to exploit correlations between signals to align incentives with truthful ...
Eliciting Expertise without Verification
EC '18: Proceedings of the 2018 ACM Conference on Economics and Computation

A central question of crowdsourcing is how to elicit expertise from agents. This is even more difficult when answers cannot be directly verified. A key challenge is that sophisticated agents may strategically withhold effort or information when they ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '18: Proceedings of the 2018 ACM Conference on Economics and Computation

June 2018

713 pages

ISBN:9781450358293

DOI:10.1145/3219166

General Chair:
Eva Tardos
Cornell University, USA
,
Program Chairs:
Edith Elkind
University of Oxford, UK
,
Rakesh Vohra
University of Pennsylvania, USA

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

EC '18

Sponsor:

SIGecom

EC '18: ACM Conference on Economics and Computation

June 18 - 22, 2018

NY, Ithaca, USA

Acceptance Rates

EC '18 Paper Acceptance Rate 70 of 269 submissions, 26%;

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Upcoming Conference

EC '25

Sponsor:
sigecom

The 25th ACM Conference on Economics and Computation

July 7 - 11, 2025

Stanford , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
559
Total Downloads

Downloads (Last 12 months)141
Downloads (Last 6 weeks)12

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kong Y(2024)Dominantly Truthful Peer Prediction Mechanisms with a Finite Number of TasksJournal of the ACM10.1145/363823971:2(1-49)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3638239
Xu SZhang YResnick PSchoenebeck GChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Spot Check Equivalence: An Interpretable Metric for Information Elicitation MechanismsProceedings of the ACM Web Conference 202410.1145/3589334.3645679(276-287)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645679
Shan LZhang SZhang JWang ZChua TNgo CKa-Wei Lee RKumar RLauw H(2024)On Truthful Item-Acquiring Mechanisms for Reward MaximizationProceedings of the ACM Web Conference 202410.1145/3589334.3645345(25-35)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645345
Faltings BElkind E(2023)Game-theoretic mechanisms for eliciting accurate informationProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/740(6601-6609)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/740
Schoenebeck GYu F(2023)Two Strongly Truthful Mechanisms for Three Heterogeneous Agents Answering One QuestionACM Transactions on Economics and Computation10.1145/356556010:4(1-26)Online publication date: 21-Feb-2023
https://dl.acm.org/doi/10.1145/3565560
Liu YWang JChen Y(2023)Surrogate Scoring RulesACM Transactions on Economics and Computation10.1145/356555910:3(1-36)Online publication date: 15-Feb-2023
https://dl.acm.org/doi/10.1145/3565559
Huang CYu HHuang JBerry R(2023)Strategic Information Revelation Mechanism in Crowdsourcing Applications Without VerificationIEEE Transactions on Mobile Computing10.1109/TMC.2021.313144522:5(2989-3003)Online publication date: 1-May-2023
https://doi.org/10.1109/TMC.2021.3131445
Tian NWu MJiang JZhang J(2022)Learning from Crowds with Mutual Correction-Based Co-Training2022 IEEE International Conference on Knowledge Graph (ICKG)10.1109/ICKG55886.2022.00040(257-264)Online publication date: Nov-2022
https://doi.org/10.1109/ICKG55886.2022.00040
Zheng SYu FChen YBiró PChawla SEchenique F(2021)The Limits of Multi-task Peer PredictionProceedings of the 22nd ACM Conference on Economics and Computation10.1145/3465456.3467642(907-926)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3465456.3467642
Huang CYu HHuang JBerry R(2021)Strategic Information Revelation in Crowdsourcing Systems Without VerificationIEEE INFOCOM 2021 - IEEE Conference on Computer Communications10.1109/INFOCOM42981.2021.9488853(1-10)Online publication date: 10-May-2021
https://doi.org/10.1109/INFOCOM42981.2021.9488853
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents