Computational Trust Models and Machine Learning K22497_FM.indd 1 9/26/14 10:10 AM Chapman & Hall/CRC Machine Learning & Pattern Recognition Series SERIES EDITORS Ralf Herbrich Thore Graepel Amazon Development Center Microsoft Research Ltd. Berlin, Germany Cambridge, UK AIMS AND SCOPE This series reflects the latest advances and applications in machine learning and pattern recog- nition through the publication of a broad range of reference works, textbooks, and handbooks. The inclusion of concrete examples, applications, and methods is highly encouraged. The scope of the series includes, but is not limited to, titles in the areas of machine learning, pattern rec- ognition, computational intelligence, robotics, computational/statistical learning theory, natural language processing, computer vision, game AI, game theory, neural networks, computational neuroscience, and other relevant topics, such as machine learning applied to bioinformatics or cognitive science, which might be proposed by potential contributors. PUBLISHED TITLES BAYESIAN PROGRAMMING Pierre Bessière, Emmanuel Mazer, Juan-Manuel Ahuactzin, and Kamel Mekhnacha UTILITY-BASED LEARNING FROM DATA Craig Friedman and Sven Sandow HANDBOOK OF NATURAL LANGUAGE PROCESSING, SECOND EDITION Nitin Indurkhya and Fred J. Damerau COST-SENSITIVE MACHINE LEARNING Balaji Krishnapuram, Shipeng Yu, and Bharat Rao COMPUTATIONAL TRUST MODELS AND MACHINE LEARNING Xin Liu, Anwitaman Datta, and Ee-Peng Lim MULTILINEAR SUBSPACE LEARNING: DIMENSIONALITY REDUCTION OF MULTIDIMENSIONAL DATA Haiping Lu, Konstantinos N. Plataniotis, and Anastasios N. Venetsanopoulos MACHINE LEARNING: An Algorithmic Perspective Stephen Marsland A FIRST COURSE IN MACHINE LEARNING Simon Rogers and Mark Girolami MULTI-LABEL DIMENSIONALITY REDUCTION Liang Sun, Shuiwang Ji, and Jieping Ye ENSEMBLE METHODS: FOUNDATIONS AND ALGORITHMS Zhi-Hua Zhou K22497_FM.indd 2 9/26/14 10:10 AM Chapman & Hall/CRC Machine Learning & Pattern Recognition Series Computational Trust Models and Machine Learning Edited by Xin Liu EPFL Lausanne, Switzerland Anwitaman Datta Nanyang Technological University Singapore Ee-Peng Lim Singapore Management University K22497_FM.indd 3 9/26/14 10:10 AM CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2015 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Version Date: 20140728 International Standard Book Number-13: 978-1-4822-2667-6 (eBook - PDF) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmit- ted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copyright. com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com To my parents and my wife — Xin Liu v Contents List of Figures xiii List of Tables xv Preface xvii About the Editors xxi Contributors xxiii 1 Introduction 1 1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 What Is Trust? . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Computational Trust . . . . . . . . . . . . . . . . . . . . . . 4 1.3.1 Computational Trust Modeling: A Review . . . . . . . 4 1.3.1.1 Summation and Average . . . . . . . . . . . 6 1.3.1.2 BayesianInference . . . . . . . . . . . . . . . 7 1.3.1.3 Web of Trust . . . . . . . . . . . . . . . . . . 8 1.3.1.4 Iterative Methods . . . . . . . . . . . . . . . 10 1.3.2 Machine Learning for Trust Modeling . . . . . . . . . 11 1.3.2.1 A Little Bit about Machine Learning . . . . 11 1.3.2.2 Machine Learning for Trust . . . . . . . . . . 12 1.4 Structure of the Book . . . . . . . . . . . . . . . . . . . . . . 17 2 Trust in Online Communities 19 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 Trust in E-Commerce Environments . . . . . . . . . . . . . . 20 2.3 Trust in Search Engines . . . . . . . . . . . . . . . . . . . . . 25 2.4 Trust in P2P Information Sharing Networks . . . . . . . . . 27 2.5 Trust in Service-OrientedEnvironments . . . . . . . . . . . . 31 2.6 Trust in Social Networks . . . . . . . . . . . . . . . . . . . . 33 2.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 vii viii Contents 3 Judging the Veracity of Claims and Reliability of Sources 39 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.2.1 Foundations of Trust . . . . . . . . . . . . . . . . . . . 43 3.2.2 Consistency in Information Extraction . . . . . . . . . 44 3.2.2.1 Local Consistency . . . . . . . . . . . . . . . 44 3.2.2.2 Global Consistency . . . . . . . . . . . . . . 44 3.2.3 Source Dependence . . . . . . . . . . . . . . . . . . . . 45 3.2.3.1 Comparisonto Credibility Analysis . . . . . 45 3.2.4 Comparison to Other Trust Mechanisms . . . . . . . . 46 3.3 Fact-Finding . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.3.1 Priors . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.3.2 Fact-Finding Algorithms . . . . . . . . . . . . . . . . . 48 3.3.2.1 Sums (Hubs and Authorities) . . . . . . . . . 48 3.3.2.2 Average·Log . . . . . . . . . . . . . . . . . . 48 3.3.2.3 Investment . . . . . . . . . . . . . . . . . . . 48 3.3.2.4 PooledInvestment . . . . . . . . . . . . . . . 49 3.3.2.5 TruthFinder . . . . . . . . . . . . . . . . . . 49 3.3.2.6 3-Estimates . . . . . . . . . . . . . . . . . . . 49 3.4 Generalized Constrained Fact-Finding . . . . . . . . . . . . . 50 3.5 Generalized Fact-Finding . . . . . . . . . . . . . . . . . . . . 50 3.5.1 Rewriting Fact-Finders for Assertion Weights . . . . . 51 3.5.1.1 Generalized Sums (Hubs and Authorities) . . 51 3.5.1.2 Generalized Average·Log . . . . . . . . . . . 51 3.5.1.3 Generalized Investment . . . . . . . . . . . . 52 3.5.1.4 Generalized PooledInvestment . . . . . . . . 52 3.5.1.5 Generalized TruthFinder . . . . . . . . . . . 52 3.5.1.6 Generalized 3-Estimates . . . . . . . . . . . . 52 3.5.2 Encoding Information in Weighted Assertions . . . . . 53 3.5.2.1 Uncertainty in Information Extraction. . . . 53 3.5.2.2 Uncertainty of the Source . . . . . . . . . . . 53 3.5.2.3 Similarity between Claims . . . . . . . . . . 54 3.5.2.4 Group Membership via Weighted Assertions 54 3.5.3 Encoding Groups and Attributes as Layers of Graph Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.5.3.1 Source Domain Expertise . . . . . . . . . . . 56 3.5.3.2 Additional Layers versus Weighted Edges . . 58 3.6 Constrained Fact-Finding . . . . . . . . . . . . . . . . . . . . 58 3.6.1 Propositional Linear Programming . . . . . . . . . . . 58 3.6.2 Cost Function. . . . . . . . . . . . . . . . . . . . . . . 59 3.6.3 Values → Votes → Belief . . . . . . . . . . . . . . . . 60 3.6.4 LP Decomposition . . . . . . . . . . . . . . . . . . . . 60 3.6.5 Tie Breaking . . . . . . . . . . . . . . . . . . . . . . . 61 3.6.6 “Unknown” Augmentation . . . . . . . . . . . . . . . 61 Contents ix 3.7 Experimental Results . . . . . . . . . . . . . . . . . . . . . . 62 3.7.1 Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.7.1.1 Population . . . . . . . . . . . . . . . . . . . 62 3.7.1.2 Books . . . . . . . . . . . . . . . . . . . . . . 63 3.7.1.3 Biography . . . . . . . . . . . . . . . . . . . 63 3.7.1.4 American vs. British Spelling . . . . . . . . . 63 3.7.2 Experimental Setup . . . . . . . . . . . . . . . . . . . 63 3.7.3 Generalized Fact-Finding . . . . . . . . . . . . . . . . 64 3.7.3.1 Tuned Assertion Certainty . . . . . . . . . . 64 3.7.3.2 Uncertainty in Information Extraction. . . . 65 3.7.3.3 Groups as Weighted Assertions . . . . . . . . 65 3.7.3.4 Groups as Additional Layers . . . . . . . . . 66 3.7.4 Constrained Fact-Finding . . . . . . . . . . . . . . . . 67 3.7.4.1 IBT vs. L+I . . . . . . . . . . . . . . . . . . 67 3.7.4.2 City Population . . . . . . . . . . . . . . . . 67 3.7.4.3 Synthetic City Population. . . . . . . . . . . 68 3.7.4.4 Basic Biographies . . . . . . . . . . . . . . . 69 3.7.4.5 American vs. British Spelling . . . . . . . . . 69 3.7.5 TheJointGeneralizedConstrainedFact-FindingFrame- work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4 Web Credibility Assessment 73 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.2 Web Credibility Overview . . . . . . . . . . . . . . . . . . . . 75 4.2.1 What Is Web Credibility? . . . . . . . . . . . . . . . . 75 4.2.2 Introduction to Research on Credibility . . . . . . . . 76 4.2.3 Current Research . . . . . . . . . . . . . . . . . . . . . 77 4.2.4 Definitions Used in This Chapter . . . . . . . . . . . . 79 4.2.4.1 Information Credibility . . . . . . . . . . . . 79 4.2.4.2 Information Controversy . . . . . . . . . . . 79 4.2.4.3 Credibility Support for Various Types of In- formation . . . . . . . . . . . . . . . . . . . . 80 4.3 Data Collection . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.3.1 Collection Means . . . . . . . . . . . . . . . . . . . . . 81 4.3.1.1 Existing Datasets . . . . . . . . . . . . . . . 81 4.3.1.2 Data from Tools Supporting Credibility Eval- uation . . . . . . . . . . . . . . . . . . . . . . 82 4.3.1.3 Data from Labelers . . . . . . . . . . . . . . 82 4.3.2 Supporting Web Credibility Evaluation . . . . . . . . 83 4.3.2.1 Support User’s Expertise . . . . . . . . . . . 84 4.3.2.2 CrowdsourcingSystems . . . . . . . . . . . . 84 4.3.2.3 Databases, Search Engines, Antiviruses and Lists of Pre-Scanned Sites. . . . . . . . . . . 85