以樹狀批次模式的增強式學習建立聚焦爬蟲

Abstract

如何從環境獲得資訊一直是增強式學習的主要議題。在過去Q-learning以表格來示Q-函式 (Q-函式定義了狀態-行為的空間，並用來找到最佳的策). 但是當狀態和行為的空間是連續的或數量很大時，Q-函式即無法再以表格來表示。在樹狀批次模式的增強式學習，我們以四-元素組合所建立的整體樹來表示Q-函式。在過去的一些相關研究，解決以四-元素組合近似Q-函式的supervised learning問題。我們將研究以extremely randomized tree 演算法來建立focused crawler. 增強式學習有許多相關的應用，例如最佳化控制、game playing和web crawler。 Web crawler是一種瀏覽網際網路的程式，主要負責複製網頁，可提供即時的資料。因為有相當大數量的頁面需要被下載、備份和處理，我們需要良好的策略來完成。 聚焦爬蟲主要負責搜尋一特定主題的頁面。在我們的研究，以 樹狀批次模式增強式學習 來建立聚焦爬蟲，並且也和其它的方法進行效能的比較，並試著找到其優、缺點。 本論文取材自國科會計劃NSC 94-2213-E-002-105，題目與解答為指導教授所授，程式製作及網站設計為學生完成。

The main issue of reinforcement learning is to find an optimal control policy by getting information from environment. In the past, Q-learning used tabular form to represent the Q-function (Q-function is defined on the state-action space and can be derived to find the optimal policy). When the state or action space is continuous or very large, the Q-function can not be represented in tabular form. In tree-based batch mode reinforcement learning, we can approximate the Q-function based on the ensemble trees which are constructed by a set of four-tuples (xt, ut, rt, xt+1) where xt is the current state, ut is the next state, rt is the instantaneous reward and xt+1 is the next state. In the past, we could find some related work that try to approximate the Q-function from a set of four-tuples by solving the supervised learning problem. We study how to use the extremely randomized tree algorithm and reinforcement learning to build the focused crawler. There are many application of reinforcement learning, including some optimal control topic, game playing and web crawler (also know as Web crawler or Web robot) crawler is a program which browses the World Wide Web. The main work of the Web crawler is crating a copy of the visited page which will be processed by search engine. Because there are a huge number of pages needs to choose and download in a given time, we must have a policy that states which page we need. Focused crawler aims to search the relevant document on a given specific topic. In this paper, we constructed and built focused crawler by tree-based batch mode reinforcement learning and we also compared the performance with other methods. We aim to practice tree-based batch mode reinforcement and find its strength and shortcoming from experiment. We used the dataset of World Wide knowledge-based project (WebKB project) and also provide the analysis of the experiment result. This work was partially supported by National Science Council, ROC under contract number NSC 94-2213-E-002-105 Keywords: tree-based batch mode reinforcement learning, ensemble tree algorithm, supervised learning, Q-learning, optimal control, Web crawler, focused crawler.