Freeboard

우리분야에서 필요로 하는 내용이 많은 것 같아서 올립니다.
공부하는데 도움이 될 것 같습니다.

다음은 책의 목차
Dedication iii
Acknowledgments iv
List Of Tables x
List Of Figures xi
Abstract xiv
1 Introduction 1
1.1 Structure in Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Example Problem: Entity Detection and Tracking . . . . . . . . . . . . . 2
1.3 The Role of Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Learning in Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.6 An Overview of This Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Machine Learning 8
2.1 Binary Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.1 Perceptron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.2 Logistic Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.3 Support Vector Machines . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.4 Generalization Bounds . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.5 Summary of Learners . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Structured Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.1 Defining Structured Prediction . . . . . . . . . . . . . . . . . . . . 16
2.2.2 Feature Spaces for Structured Prediction . . . . . . . . . . . . . . 18
2.2.3 Structured Perceptron . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.4 Incremental Perceptron . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.5 Maximum Entropy Markov Models . . . . . . . . . . . . . . . . . . 20
2.2.6 Conditional Random Fields . . . . . . . . . . . . . . . . . . . . . . 21
vi
2.2.7 Maximum Margin Markov Networks . . . . . . . . . . . . . . . . . 22
2.2.8 SVMs for Interdependent and Structured Outputs . . . . . . . . . 23
2.2.9 Reranking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.10 Summary of Learners . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3 Learning Reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.1 Reduction Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.2 Importance Weighted Binary Classification . . . . . . . . . . . . . 27
2.3.3 Cost-sensitive Classification . . . . . . . . . . . . . . . . . . . . . . 28
2.4 Discussion and Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3 Search-based Structured Prediction 30
3.1 Contributions and Methodology . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 Generalized Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Search-based Structured Prediction . . . . . . . . . . . . . . . . . . . . . . 33
3.4 Training . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.4.1 Cost-sensitive Examples . . . . . . . . . . . . . . . . . . . . . . . . 33
3.4.2 Optimal Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4.3 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4.4 Simple Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4.5 Comparison to Local Classifier Techniques . . . . . . . . . . . . . . 37
3.4.6 Feature Computations . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.5 Theoretical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.6 Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.6.1 Optimal Policy Assumption . . . . . . . . . . . . . . . . . . . . . . 41
3.6.2 Search-based Optimal Policies . . . . . . . . . . . . . . . . . . . . . 42
3.6.3 Beyond Greedy Search . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.6.4 Relation to Reinforcement Learning . . . . . . . . . . . . . . . . . 44
3.7 Discussion and Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4 Sequence Labeling 47
4.1 Sequence Labeling Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.1.1 Handwriting Recognition . . . . . . . . . . . . . . . . . . . . . . . 48
4.1.2 Spanish Named Entity Recognition . . . . . . . . . . . . . . . . . . 49
4.1.3 Syntactic Chunking . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.1.4 Joint Chunking and Tagging . . . . . . . . . . . . . . . . . . . . . 50
4.2 Loss Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3 Search and Optimal Policies . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3.1 Sequence Labeling . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3.2 Segmentation and Labeling . . . . . . . . . . . . . . . . . . . . . . 53
4.3.3 Optimal Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.4 Empirical Comparison to Alternative Techniques . . . . . . . . . . . . . . 54
4.5 Empirical Comparison of Tunable Parameters . . . . . . . . . . . . . . . . 56
4.6 Discussion and Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . 59
vii
5 Entity Detection and Tracking 61
5.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.2 Prior Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.2.1 Mention Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.2.2 Coreference Resolution . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.2.2.1 Binary Classification . . . . . . . . . . . . . . . . . . . . . 66
5.2.2.2 Multilabel Classification . . . . . . . . . . . . . . . . . . . 68
5.2.2.3 Random Fields . . . . . . . . . . . . . . . . . . . . . . . . 69
5.2.2.4 Coreference Resolution Features . . . . . . . . . . . . . . 69
5.2.3 Shortcomings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.3 EDT Data Set and Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 71
5.4 Entity Mention Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.4.1 Search Space and Actions . . . . . . . . . . . . . . . . . . . . . . . 72
5.4.2 Optimal Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.4.3 Feature Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.4.3.1 Base Features . . . . . . . . . . . . . . . . . . . . . . . . 73
5.4.3.2 Decision Features . . . . . . . . . . . . . . . . . . . . . . 75
5.4.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.4.5 Error Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.5 Coreference Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.5.1 Search Space and Actions . . . . . . . . . . . . . . . . . . . . . . . 76
5.5.2 Optimal Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.5.3 Feature Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.5.3.1 Base Features . . . . . . . . . . . . . . . . . . . . . . . . 79
5.5.3.2 Decision Features . . . . . . . . . . . . . . . . . . . . . . 81
5.5.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.5.5 Error Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.6 Joint Detection and Coreference . . . . . . . . . . . . . . . . . . . . . . . 83
5.6.1 Search Space and Actions . . . . . . . . . . . . . . . . . . . . . . . 83
5.6.2 Optimal Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.6.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.7 Discussion and Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6 Multidocument Summarization 87
6.1 Vine-Growth Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.2 Search Space and Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.3 Data and Evaluation Criteria . . . . . . . . . . . . . . . . . . . . . . . . . 90
6.4 Optimal Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.5 Feature Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
6.6 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
6.7 Error Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.8 Discussion and Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . 94
viii
7 Conclusions and Future Directions 96
7.1 Weak Feedback Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
7.1.1 Comparison Oracle Model . . . . . . . . . . . . . . . . . . . . . . . 97
7.1.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
7.1.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
7.1.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . 99
7.1.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7.2 Hidden Variable Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7.2.1 Translation Classification . . . . . . . . . . . . . . . . . . . . . . . 101
7.2.2 Search-based Hidden Variable Models . . . . . . . . . . . . . . . . 102
7.2.2.1 Iterative Algorithm . . . . . . . . . . . . . . . . . . . . . 103
7.2.2.2 Optimal Policy . . . . . . . . . . . . . . . . . . . . . . . . 104
7.2.3 Features and Data . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.2.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . 106
7.2.5 Comparison to Expectation Maximization . . . . . . . . . . . . . . 106
7.3 Other Applications for Searn . . . . . . . . . . . . . . . . . . . . . . . . . 108
7.3.1 Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
7.4 Machine Translation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
7.5 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
7.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
Bibliography 113
Appendix A
Summary of Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
A.1 Common Sets and Functions . . . . . . . . . . . . . . . . . . . . . . . . . 130
A.2 Vectors, Matrices and Sums . . . . . . . . . . . . . . . . . . . . . . . . . . 130
A.3 Complexity Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
Appendix B
Proofs of Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
Appendix C
Relevant Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134