第1页 / 共285页
第2页 / 共285页
第3页 / 共285页
第4页 / 共285页
第5页 / 共285页
第6页 / 共285页
第7页 / 共285页
第8页 / 共285页
The Beauty of Mathematics in Computer Science.pdf
THE BEAUTY OF
MATHEMATICS IN COMPUTER
SCIENCE
Jun Wu
A Chapman & Hall Book
The Beauty of
Mathematics in
Computer Science
The Beauty of
Mathematics in
Computer Science
Jun Wu
Translated from the Chinese edition by
Rachel Wu and Yuxi Candice Wang
CRC Press
Taylor & Francis Group
6000 Broken Sound Parkway NW, Suite 300
Boca Raton, FL 33487-2742
© 2019 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
Printed on acid-free paper
International Standard Book Number-13: 978-1-138-04960-4 (Paperback)
978-1-138-04967-3 (Hardback)
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,
transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or here-
after 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.
Library of Congress Cataloging-in-Publication Data
Names: Wu, Jun, 1967- author.
Title: The beauty of mathematics in computer science / Jun Wu.
Description: Boca Raton, FL : Taylor & Francis Group, 2019.
Identifiers: LCCN 2018035719| ISBN 9781138049604 paperback | ISBN
9781138049673 hardback
Subjects: LCSH: Computer science--Mathematics. | Machine learning.
Classification: LCC QA76.9.M35 W84 2019 | DDC 004.01/51--dc23
LC record available at https://lccn.loc.gov/2018035719
Visit the Taylor & Francis Web site at
http:==========www.taylorandfrancis.com
and the CRC Press Web site at
http:==========www.crcpress.com
Contents
Foreword . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv
1 Words and languages, numbers and information . . . . . . . . . . . . . . . 1
1.1
Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Words and numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 The mathematics behind language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2 Natural language processing—From rules to statistics . . . . . . . . 13
2.1 Machine intelligence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 From rules to statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Statistical language model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1 Describing language through mathematics . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Extended reading: Implementation caveats . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1 Higher order language models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.2 Training methods, zero-probability problems,
and smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.3 Corpus selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4 Word segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.1 Evolution of Chinese word segmentation . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2 Extended reading: Evaluating results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2.1 Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2.2 Granularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
v
vi
Contents
5 Hidden Markov model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.1 Communication models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.2 Hidden Markov model
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.3 Extended reading: HMM training . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6 Quantifying information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
6.1
Information entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
6.2 Role of information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6.3 Mutual information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
6.4 Extended reading: Relative entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
7 Jelinek and modern language processing . . . . . . . . . . . . . . . . . . . . . . 63
7.1 Early life . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
7.2 From Watergate to Monica Lewinsky . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
7.3 An old man’s miracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
8 Boolean algebra and search engines . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
8.1 Boolean algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
8.2
Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
8.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
9 Graph theory and web crawlers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
9.1 Graph theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
9.2 Web crawlers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
9.3 Extended reading: Two topics in graph theory . . . . . . . . . . . . . . . . . . . 79
9.3.1 Euler’s proof of the Königsberg bridges . . . . . . . . . . . . . . . . . . . 79
9.3.2 The engineering of a web crawler . . . . . . . . . . . . . . . . . . . . . . . . . 80
9.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
10 PageRank: Google’s democratic ranking technology . . . . . . . . . 83
10.1 The PageRank algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
10.2 Extended reading: PageRank calculations . . . . . . . . . . . . . . . . . . . . . 86
10.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
11 Relevance in web search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
11.1 TF-IDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
Contents
vii
11.2 Extended reading: TF-IDF and information theory . . . . . . . . . . . . 92
11.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
12 Finite state machines and dynamic programming:
Navigation in Google Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
12.1 Address analysis and finite state machines . . . . . . . . . . . . . . . . . . . . . 96
12.2 Global navigation and dynamic programming . . . . . . . . . . . . . . . . . 98
12.3 Finite state transducer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .101
12.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .102
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .103
13 Google’s AK-47 designer, Dr. Amit Singhal . . . . . . . . . . . . . . . . . 105
14 Cosines and news classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
14.1 Feature vectors for news . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .109
14.2 Vector distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .111
14.3 Extended reading: The art of computing cosines . . . . . . . . . . . . . .114
14.3.1 Cosines in big data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
14.3.2 Positional weighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
14.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .116
15 Solving classification problems in text processing
with matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
15.1 Matrices of words and texts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .117
15.2 Extended reading: Singular value decomposition
method and applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .120
15.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .121
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .121
16 Information fingerprinting and its application . . . . . . . . . . . . . . 123
16.1
Information fingerprint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .123
16.2 Applications of information fingerprint . . . . . . . . . . . . . . . . . . . . . . .125
16.2.1 Determining identical sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
16.2.2 Detecting similar sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
16.2.3 YouTube’s anti-piracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
16.3 Extended reading: Information fingerprint’s repeatability
and SimHash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .128
16.3.1 Probability of repeated information fingerprint . . . . . . 128
16.3.2 SimHash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
16.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .131
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .132
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
