南開科技大學圖書館 |

Language: 繁體中文

說明(常見問題)

南開科技大學

圖書館首頁

編目中圖書申請

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

Context-free graph grammar induction...

Jonyer, Istvan.

Context-free graph grammar induction using the minimum description length principle.

紀錄類型:	書目-電子資源 : 單行本
正題名/作者:	Context-free graph grammar induction using the minimum description length principle./
作者:	Jonyer, Istvan.
面頁冊數:	179 p.
附註:	Source: Dissertation Abstracts International, Volume: 64-09, Section: B, page: 4459.
Contained By:	Dissertation Abstracts International64-09B.
標題:	Computer Science. -
電子資源:	Download fulltext (下載全文)
ISBN:	0496544136

Context-free graph grammar induction using the minimum description length principle.
Jonyer, Istvan.

Context-free graph grammar induction using the minimum description length principle. - 179 p.

Source: Dissertation Abstracts International, Volume: 64-09, Section: B, page: 4459.

Thesis (Ph.D.)--The University of Texas at Arlington, 2003.

This work is concerned with developing a machine learning algorithm for inducing context-free graph grammars, which is guided by the minimum description length principle. Recognizing the representational power of graphs and the ability of graph grammars to generalize, we develop an approach that extends the expressive power of hypotheses learned from examples over algorithms that learn static patterns only, to equal the expressive power of graph grammars. The induced graph grammar is our hypothesis for concepts. We motivate our work from different angles. First, we point to the need for representing more complex concepts, those that include recursion, variability and relationships among data points. Second, we point out the lack of existing graph-based systems to address these concerns. Third, we recognize the ability of other machine learning approaches to address some of these concerns, and that the combination of graph-based systems with these features will have practical utility. We survey related work, among which are graph-based and inductive logic programming systems. These systems are the closest to our approach, either because they represent data in graph format, or they are able to learn recursive concepts. We describe our approach in detail, which includes the ability to learn recursive concepts, concepts that include variable data points, and those that include relationships among data points. We extend our approach for both discovery and concept learning modes. We find that the class of graph grammars learned by our algorithm is equivalent to the class of regular graph grammars. The algorithm is implemented as an extension to the Subdue knowledge discovery system, and is named SubdueGL. We present a rigorous evaluation methodology used to validate the new algorithm. We find that the system tolerates noise to a certain degree. We also evaluate the system on several real-world examples, among which are an anti-terrorism domain, protein sequences of primary and secondary structure, and a breast cancer domain. We compare the system to prominent competing approaches on further examples, which are commonly used in the literature to for the purpose of evaluating machine learning systems. We find that our approach performs better than competing ILP systems on the domains tested, and does better that some statistical and connectionist approaches reported in the literature.

ISBN: 0496544136Subjects--Topical Terms:

1000005419
Computer Science.

Context-free graph grammar induction using the minimum description length principle.
LDR:03381nmm 2200277 4500 001 1000004231
005 20051102155236.5
008 141201s2003 eng d
020 $a 0496544136
035 $a (UnM)AAI3106849
035 $a AAI3106849
040 $a UnM $c UnM{me_controlnum}
100 1 $a Jonyer, Istvan. $3 1000005480
245 1 0 $a Context-free graph grammar induction using the minimum description length principle.
300 $a 179 p.
500 $a Source: Dissertation Abstracts International, Volume: 64-09, Section: B, page: 4459.
500 $a Adviser: Lawrence B. Holder.
502 $a Thesis (Ph.D.)--The University of Texas at Arlington, 2003.
520 $a This work is concerned with developing a machine learning algorithm for inducing context-free graph grammars, which is guided by the minimum description length principle. Recognizing the representational power of graphs and the ability of graph grammars to generalize, we develop an approach that extends the expressive power of hypotheses learned from examples over algorithms that learn static patterns only, to equal the expressive power of graph grammars. The induced graph grammar is our hypothesis for concepts. We motivate our work from different angles. First, we point to the need for representing more complex concepts, those that include recursion, variability and relationships among data points. Second, we point out the lack of existing graph-based systems to address these concerns. Third, we recognize the ability of other machine learning approaches to address some of these concerns, and that the combination of graph-based systems with these features will have practical utility. We survey related work, among which are graph-based and inductive logic programming systems. These systems are the closest to our approach, either because they represent data in graph format, or they are able to learn recursive concepts. We describe our approach in detail, which includes the ability to learn recursive concepts, concepts that include variable data points, and those that include relationships among data points. We extend our approach for both discovery and concept learning modes. We find that the class of graph grammars learned by our algorithm is equivalent to the class of regular graph grammars. The algorithm is implemented as an extension to the Subdue knowledge discovery system, and is named SubdueGL. We present a rigorous evaluation methodology used to validate the new algorithm. We find that the system tolerates noise to a certain degree. We also evaluate the system on several real-world examples, among which are an anti-terrorism domain, protein sequences of primary and secondary structure, and a breast cancer domain. We compare the system to prominent competing approaches on further examples, which are commonly used in the literature to for the purpose of evaluating machine learning systems. We find that our approach performs better than competing ILP systems on the domains tested, and does better that some statistical and connectionist approaches reported in the literature.
590 $a School code: 2502.
650 4 $a Computer Science. $3 1000005419
650 4 $a Artificial Intelligence. $3 165300
690 $a 0984
690 $a 0800
710 2 0 $a The University of Texas at Arlington. $3 1000005481
773 0 $t Dissertation Abstracts International $g 64-09B.
790 1 0 $a Holder, Lawrence B., $e advisor
790 $a 2502
791 $a Ph.D.
792 $a 2003
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3106849 $z Download fulltext (下載全文)