請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/71152完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 薛智文(Chih-Wen Hsueh) | |
| dc.contributor.author | Hung-Jui Chang | en |
| dc.contributor.author | 張紘睿 | zh_TW |
| dc.date.accessioned | 2021-06-17T04:55:44Z | - |
| dc.date.available | 2023-08-01 | |
| dc.date.copyright | 2018-08-01 | |
| dc.date.issued | 2018 | |
| dc.date.submitted | 2018-07-27 | |
| dc.identifier.citation | [1] National health insurance research database. http://nhird.nhri.org.tw/.
[2] National health insurance research database, Taiwan. [3] Shredder computer chess, http://www.shredderchess.com/online-chess/onlinedatabases/endgame-database.html. [4] Lomonosov endgame tablebases, http://chessok.com/?page id=27966, 2017. [5] R. Agrawal and R. Srikant. Fast algorithms for mining association rules. In Proc. 20th int. conf. very large data bases, VLDB, volume 1215, pages 487–499, 1994. [6] I. Althofer. On board-filling games with random-turn order and Monte Carlo perfectness. In Advances in Computer Games, pages 258–269. Springer, 2012. [7] M.-L. P. andH. M. Tsao, C.-C. Hsu, K.-M. Wu, T.-s. Hsu, Y.-T. Wu, and G.-C. Hu. Bidirectional association between obstructive sleep apnea and depression: A population-based longitudinal study. Medicine, 95(37):e4833, 2016. [8] B. Bouzy and B. Helmstetter. Monte-Carlo Go developments. In Advances in computer games, pages 159–174. Springer, 2004. [9] B. Brugmann. Monte Carlo Go. Technical report, 1993. [10] H.-J. Chang and T.-s. Hsu. A quantitative study of 2× 4 Chinese dark chess. In 8th International Conference on Computers and Games (CG 2013), pages 151–162. Springer, 2014. [11] B.-N. Chen and T.-s. Hsu. Automatic generation of Chinese dark chess opening books. In 8th International Conference on Computers and Games (CG 2013). Springer, 2014. [12] B.-N. Chen, B.-J. Shen, and T.-s. Hsu. Chinese dark chess. ICGA Journal, 33(2):93–106, 2010. [13] J.-C. Chen, T.-Y. Lin, B.-N. Chen, and T.-s. Hsu. Equivalence classes in Chinese dark chess endgames. IEEE Transactions on Computational Intelligence and AI in Games, 7(2):109–122, 2015. [14] J.-C. Chen, T.-Y. Lin, S.-C. Hsu, and T.-s. Hsu. Design and implementation of computer Chinese dark chess endgame database. In Proceeding of TCGA Workshop, pages 5–9, 2012. [15] Y.-C. Chen, J.-C. Wu, I. Haschler, A. Majeed, T.-J. Chen, and T. Wetter. Academic impact of a public electronic health database: bibliometric analysis of studies using the general practice research database. PloS one, 6(6):e21404, 2011. [16] S. Chung, C. Lin, J. Ho, J. Ting, H. Lin, and C. Hu. Increased risk of openangle glaucoma following chronic rhinosinusitis: a population-based matchedcohort study. Eye, 28(2):225–230, 2013. [17] P. M. Fenwick. A new data structure for cumulative frequency tables. Software: Practice and Experience, 24(3):327–336, 1994. [18] R. A. Fisher. On the interpretation of χ2 from contingency tables, and the calculation of p. Journal of the Royal Statistical Society, 85(1):87–94, 1922. [19] L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian journal of Mathematics, 8(3):399–404, 1956. [20] A. V. Goldberg and R. E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM (JACM), 35(4):921–940, 1988. [21] D. A. Grimes and K. F. Schulz. Compared to what? finding controls for case-control studies. The Lancet, 365(9468):1429–1433, 2005. [22] M. Guid and I. Bratko. Factors affecting diminishing returns for searching deeper. ICGA Journal, 30(2):75–84, 2007. [23] B. B. Hansen. Full matching in an observational study of coaching for the sat. Journal of the American Statistical Association, 99(467):609–618, 2004. [24] E. A. Heinz. Self-play, deep search and diminishing returns. In ICGA Journal, volume 24, 2001. [25] E. A. Heinz. Follow-up on” self-play, deep search, and diminishing returns”. ICGA Journal, 26(2):75–80, 2003. [26] D. E. Ho, K. Imai, G. King, and E. A. Stuart. Matching as nonparametric preprocessing for reducing model dependence in parametric causal inference. Political analysis, 15(3):199–236, 2007. [27] D. E. Ho, K. Imai, G. King, and E. A. Stuart. Matchit: Nonparametric preprocessing for parametric causal inference. Journal of Statistical Software, 2007. [28] G. Hripcsak and D. J. Albers. Next-generation phenotyping of electronic health records. Journal of the American Medical Informatics Association, 20(1):117–121, 2013. [29] T.-s. Hsu, S.-C. Hsu, J.-C. Che, Y.-T. Chiang, B.-N. Chen, Y.-C. Liu, H.-J. Chang, S.-C. Tsai, T.-Y. Lin, and G.-Y. Fan. Computers and Classical Board Games: An Introduction. National Taiwan University Press, 2017. [30] S.-C. Huang, R. Coulom, and S.-S. Lin. Monte-Carlo simulation balancing in practice. In Computers and Games, pages 81–92. Springer, 2011. [31] N. Jouandeau and T. Cazenave. Small and large mcts playouts applied to Chinese dark chess stochastic game. In Computer Games, pages 78–89. Springer, 2014. [32] R. J. B. Jr. Efficiently mining long patterns from databases. In ACM Sigmod Record, volume 27, pages 85–93. ACM, 1998. [33] A. Junghanns, J. Schaeffer, M. Brockington, Y. Bjornsson, and T. Marsland. Diminishing returns for additional search in chess. In In Advances in Computer Chess 8. Citeseer, 1997. [34] H. Kawabata, M. Tran, and P. Hines. Using SAS R to match cases for case control studies. In Proceeding of the Twenty-Ninth Annual SAS R Users Group International Conference, volume 29, pages 173–29, 2004. [35] D. E. Knuth and R. W. Moore. An analysis of alpha-beta pruning. Artif. Intell., 6(4):293–326, 1975. [36] L. Kocsis and C. Szepesvari. Bandit based Monte-Carlo planning. In ´ Machine Learning: ECML 2006, pages 282–293. Springer, 2006. [37] W.-H. Lin, C.-H. Hsu, H.-F. Chen, C.-C. Liu, and C.-Y. Li. Mortality of patients with type 2 diabetes in Taiwan: A 10-year nationwide follow-up study. Diabetes research and clinical practice, 2014. [38] V. Lisy, V. Kovarik, M. Lanctot, and B. Bosansky. Convergence of Monte Carlo tree search in simultaneous move games. In Advances in Neural Information Processing Systems, pages 2112–2120, 2013. [39] J. Nunn. Extracting information from endgame databases. ICGA Journal, 16(4):191–200, 1993. [40] D. Patnaik, P. Butler, N. Ramakrishnan, L. Parida, B. J. Keller, and D. A. Hanauer. Experiences with mining temporal event sequences from electronic medical records: initial successes and some challenges. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 360–368. ACM, 2011. [41] K. Pearson. On the Criterion that a Given System of Deviations from the Probable in the Case of a Correlated System of Variables is Such that it Can be Reasonably Supposed to have Arisen from Random Sampling, pages 11–28. Springer New York, New York, NY, 1992. [42] P. R. Rosenbaum and D. B. Rubin. Constructing a control group using multivariate matched sampling methods that incorporate the propensity score. The American Statistician, 39(1):33–38, 1985. [43] J. Schaeffer, N. Burch, Y. Bjornsson, A. Kishimoto, M. M ¨ uller, R. Lake, P. Lu, and S. Sutphen. Checkers is solved. science, 317(5844):1518–1522, 2007. [44] C. E. Shannon. Programming a computer for playing chess. In Computer chess compendium, pages 2–13. Springer, 1988. [45] C. E. Shannon. A mathematical theory of communication. ACM SIGMOBILE Mobile Computing and Communications Review, 5(1):3–55, 2001. [46] C. L. Sistrom and C. W. Garvan. Proportions, odds, and risk. Radiology, 230(1):12–19, 2004. [47] R. Srikant and R. Agrawal. Mining sequential patterns: Generalizations and performance improvements. Springer, 1996. [48] G. Strang. Introduction to Linear Algebra. Wellesley-Cambridge Press, 2016. [49] K. Thompson. Computer chess strength. In Advances in Computer Chess 3, 1982. [50] K. Thompson. Retrograde analysis of certain endgames. ICCA Journal, 9(3):131–139, 1986. [51] C.-H. Tseng. Diabetes but not insulin increases the risk of lung cancer: A Taiwanese population-based study. PloS one, 9(7):e101553, 2014. [52] H. K. Ury. Efficiency of case-control studies with multiple controls per case: continuous or dichotomous data. Biometrics, pages 643–649, 1975. [53] F.-J. Wu, S.-Y. Sheu, and H.-C. Lin. Osteoporosis is associated with antiepileptic drugs: a population-based study. Epileptic Disorders, 16(3):333–342, 2014. [54] F. Yates. Contingency tables involving small numbers and the χ2 test. Supplement to the Journal of the Royal Statistical Society, 1(2):217–235, 1934. [55] S. Yen, J.-C. Chen, T.-N. Yang, and S.-C. Hsu. Computer chinese chess. ICGA Journal, 27(1):3–18, 2004. [56] S.-J. Yen, C.-W. Chou, J.-C. Chen, I.-C. Wu, and K.-Y. Kao. The art of the Chinese dark chess program DIABLE. In Advances in Intelligent Systems and Applications - Volume 1, volume 20 of Smart Innovation, Systems and Technologies, pages 231–242. Springer Berlin Heidelberg, 2013. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/71152 | - |
| dc.description.abstract | 在本篇論文中，作者使用資訊理論的分析方法，對時序性資料庫進行分析，藉以研究時序資庫中之資料點於不同時間點的轉換，尋找出隱藏的資訊及因果關係。其中為提高因果關係判斷的精準度，作者提出了兩種篩選資料點的方式：其一是對相同時間點下的不同狀態建立篩選規則，提高同一個時間點下的資料點所形成之資料集之可靠度；其二是對兩個時間點的資料集，透過隨機配對的方式，降低計算因果關係時所可能產生的誤差。除了計算兩個狀態點間的因果關係及轉移機率，作者同時利用時序資料庫中的資料，驗證隨機配對演算法在時序資料庫中的隨機性。同時以時序行資料的觀點分析蒙地卡羅樹搜尋演算法所形成之解集合隨時間變化的收斂性及正確性。在本論文中一共提及了兩種不同類型的資料庫，其一是由人類自然活動所形成的健保資料庫，其二是由電腦所計算出的對局資料庫。作者將此二種不同來源的資料庫，以一般化的時序性模型進行描述，並透過機率分析的方法，對此兩種資料庫進行分析。透過分析，作者從研究的資料庫中，探勘出隱藏在此二種資料庫中的資訊，並將探勘出的資訊應用在建立及強化現有之專家系統。實驗顯示，在健保資料庫中所萃取出的事件組合，符合過去研究中判定為高研究價值的事件組合，藉由快算探勘整個健保資料庫，產生出大量具有研究價值且尚未被領域專家確認發表的事件組合。在對局資料庫中所萃取出的資訊，得以用於修正過去領域專家所忽略的部份，並發展出新的一般性領域知識。實驗顯示藉由應用新發展出的領域知識，可以有效的改善對局系統的效能。於此同時，也藉由此二種資料庫的內容及資訊分析的方法，驗證及改良隨機性演算法在時序性資料庫中的效能，分析的結果顯示出，演算法的初始參數設置，對世代研究的隨機配對法所產生的配對結果穩定度有相當大的影響。改良後的世代研究隨機配對法，可以提高整體候選對照組被配對的隨機性，進而提高配對結果所產生的統計數值的穩定度。而在蒙地卡羅上確界樹搜尋演算法的實驗中顯示出，在隨機性遊戲中蒙地卡羅上確界樹搜尋演算法會以集合為目標，而非以單值為目標收斂，妥善的設置隨機演算法中的參數，可以收斂到特定性質的解集合中。 | zh_TW |
| dc.description.abstract | In this dissertation, the author uses the information theoretical related analysis method to study the sequential database. By observing the transformation of events between different timestamps, hidden information and relations between events are found. In order to increase the precision of judging the casual relationship, two methods are proposed to select data points. The first method focuses on selecting data points within the same group. By removing the unreliable data points, the remaining data points in a state group are more reliable. The second method relies on the randomized matching algorithm. By using the randomized matching algorithm to reduce the bias when judging the casual relationship. Besides finding the transformation probability and the causal relation, the author also uses the sequential database to verify the quality of randomness of the randomized matching algorithms. Meanwhile, the author treats the solution sets of Monte Carlo tree search algorithm as the sequential data, and the correctness and the convergence speed are examined. In this dissertation, two different types of databases are presented and analyzed. The first database is the health insurance database, which records the natural human behavior. The second one is the game-theoretical value database, which is calculated by the computer with a retrograde analysis related algorithm. The author used a general sequential model to describe the two presented databases and applied probability related analysis method to these two databases. The hidden information in these two databases are found, and the founded results are applied to enhance the existed knowledge-based expert systems. The experiment results show that the extracted event pairs in the insurance health database cover most of the critical event pairs, which are published previously. Through the efficient analysis method, more undiscovered event pairs with a high value of research are founded. In the game-theoretical value database, the established result is used to fine-tune the expert system and propose new domain knowledge which is ignored before. The experiment results show the game playing program is highly improved by applying the newly discovered domain knowledge. Meanwhile, the author also used the entropy analysis method to verify and enhence the performance of randomized algorithms, which are used in the sequential databases. The experiment results show the initial settings of parameters are a highly effect factor of the cohort study with randomized matching. The improved randomized matching algorithm of the cohort study can highly improve the randomness of the selected control candidates, and the stabilization of the experiment results are also improved. On the other hand, the experiment results show the Monte-Carlo tree search algorithm will converge to a solution set, instead of a single solution. By carefully setting the parameter of the Monte-Carlo tree search algorithm, the result will converge to specific solutions with specific properties. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-17T04:55:44Z (GMT). No. of bitstreams: 1 ntu-107-D02922019-1.pdf: 2344348 bytes, checksum: 39cac969ececcf8fe4d523e474c0a9b7 (MD5) Previous issue date: 2018 | en |
| dc.description.tableofcontents | 致謝 i
中文摘要 iii Abstract v 1 Introduction 1 1.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Background 5 2.1 Sequential Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.1 Endgame Database . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.2 National Health Insurance Database . . . . . . . . . . . . . . . . 6 2.2 Randomize Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.1 Monte-Carlo Tree Search Algorithm . . . . . . . . . . . . . . . . 7 2.2.2 Random Matching Algorithm . . . . . . . . . . . . . . . . . . . 7 3 Using Chinese Dark Chess Endgame Database to Validate and Fine-Tune Game Evaluation Functions 9 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2.1 The Rules of Chinese Dark Chess . . . . . . . . . . . . . . . . . 12 3.2.2 Structure of CDC Endgame Databases . . . . . . . . . . . . . . . 13 3.2.3 Extracting Information from Endgame Databases . . . . . . . . . 14 3.3 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.3.1 Reasonable State Distribution . . . . . . . . . . . . . . . . . . . 15 3.3.2 Stable Positions . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3.3 Selection Rules for Picking Reasonable Positions . . . . . . . . . 16 3.3.4 Comparing Stable Positions with Reasonable Positions . . . . . . 19 3.3.5 Polynomial Approximation Evaluation Function . . . . . . . . . 21 3.4 Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.4.1 Experiment Setting . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.4.2 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.4.3 Experiment Result of State Distribution . . . . . . . . . . . . . . 23 3.4.4 Experiment results of the Approximation Function Constructed . 23 3.4.5 Rules Found to Revise f . . . . . . . . . . . . . . . . . . . . . . 26 3.4.6 Revising f and Self-Play Experiments . . . . . . . . . . . . . . . 26 3.5 Conclusion and Future Works . . . . . . . . . . . . . . . . . . . . . . . . 27 4 Efficient Randomized Algorithms for Large-scaled Exact Matchings with Multiple Controls: Implementation and Applications 29 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.1.1 Data Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.1.2 Cases and Controls . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.1.3 Causality Inference . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.1.4 Research Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2.2 A Naive Greedy Matching Algorithm . . . . . . . . . . . . . . . 34 4.2.3 Using Graph Maximum Flow . . . . . . . . . . . . . . . . . . . 34 4.2.4 The Proposed Matching Algorithm . . . . . . . . . . . . . . . . 39 4.3 Experiment Results and Discussion . . . . . . . . . . . . . . . . . . . . . 42 4.3.1 Experiment Setting . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.3.2 Results of the Execution Time and Memory Usage . . . . . . . . 44 4.3.3 Successful Matching Rates . . . . . . . . . . . . . . . . . . . . . 46 4.3.4 RR Ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.3.5 Quality of Randomness . . . . . . . . . . . . . . . . . . . . . . . 50 4.4 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5 Convergence and Correctness Analysis of Monte-Carlo Tree Search Algorithms: A Case Study of 2 by 4 Chinese Dark Chess 55 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 5.2 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.2.2 UCT algorithm for Chinese Dark Chess . . . . . . . . . . . . . . 59 5.2.3 Measurement of convergence speed and correctness rate . . . . . 61 5.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.3.1 Experiment setting . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.3.2 Experiment results . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.4.1 Convergence analysis . . . . . . . . . . . . . . . . . . . . . . . . 63 5.4.2 Correctness analysis . . . . . . . . . . . . . . . . . . . . . . . . 63 5.5 Conclusion and Future Works . . . . . . . . . . . . . . . . . . . . . . . . 66 6 Conclusion 69 Bibliography 71 | |
| dc.language.iso | en | |
| dc.subject | 隨機演算法 | zh_TW |
| dc.subject | 序列資料 | zh_TW |
| dc.subject | 資訊理論 | zh_TW |
| dc.subject | 資訊探勘 | zh_TW |
| dc.subject | 專家系統 | zh_TW |
| dc.subject | information retrieval | en |
| dc.subject | expert system | en |
| dc.subject | randomized algorithm | en |
| dc.subject | Sequential data | en |
| dc.subject | information theory | en |
| dc.title | 基於資訊理論分析的序列型資料資料探勘及分析 | zh_TW |
| dc.title | Information Retrieval and Analysis in Sequential Data: An Information Theoretical Approach | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 106-2 | |
| dc.description.degree | 博士 | |
| dc.contributor.coadvisor | 徐讚昇(Tsang-sheng Hsu) | |
| dc.contributor.oralexamcommittee | 王大為(Da-Wei Wang),施吉昇(Chi-Sheng Shih),吳家麟(Ja-Ling Wu) | |
| dc.subject.keyword | 序列資料,資訊理論,資訊探勘,專家系統,隨機演算法, | zh_TW |
| dc.subject.keyword | Sequential data,information theory,information retrieval,expert system,randomized algorithm, | en |
| dc.relation.page | 75 | |
| dc.identifier.doi | 10.6342/NTU201801967 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2018-07-30 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-107-1.pdf 未授權公開取用 | 2.29 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。