Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


ucin1037999729.pdf (707.61 KB)

ETD Abstract Container

Abstract Header

LEARNING DETERMINISTIC FINITE AUTOMATA TO CAPTURE TEMPORAL PATTERNS

VETTEL, LYNNE ANN
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1037999729

Abstract Details

2002, MS, University of Cincinnati, Engineering : Computer Science.
This thesis considers the problem of discovering temporal patterns in time series data using deterministic finite automata (DFAs) as a description of temporal hypotheses. The objective is to identify trends, cycles, or common subsequences from a set of time series data. The approach described here uses membership and equivalence queries to learn a DFA that models the target temporal pattern. Query-based DFA learning algorithms require an oracle that can be asked about a particular string and return a response indicating whether the string contains the target pattern. These queries can include strings that are not in the original dataset, which in the case of temporal learning is typically composed of a limited number of positive examples. The challenge addressed in this thesis is the need to augment the original dataset in order to provide the oracle with enough information so that it can accurately answer queries. The systematic nature of trends and cycles allows some logical assumptions in order to supplement the original data. Lacking this systematic quality, subsequences do not lend themselves to similar assumptions. Instead, two strategies for discovering subsequence patterns are explored. The first strategy employs the idea that the target subsequence common to all episodes consists of smaller subsequences that are also common to all episodes. The oracle can use the occurrence of these short common subsequences as a basis for determining the membership of a queried string. This strategy does not always yield the exact target concept, since the oracle still does not have all the information necessary to answer every query correctly. So the oracle needs a means to answer queries when the correct answer cannot be determined from the available data. The second strategy for discovering subsequence patterns takes into consideration that there is some error in the oracle's answers.
Dr. Raj Bhatnagar (Advisor)
110 p.
Computer Science
temporal patterns; machine learning; fallible teacher; incomplete knowledge

Recommended Citations

Citations

  • VETTEL, L. A. (2002). LEARNING DETERMINISTIC FINITE AUTOMATA TO CAPTURE TEMPORAL PATTERNS [Master's thesis, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1037999729

    APA Style (7th edition)

  • VETTEL, LYNNE. LEARNING DETERMINISTIC FINITE AUTOMATA TO CAPTURE TEMPORAL PATTERNS. 2002. University of Cincinnati, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1037999729.

    MLA Style (8th edition)

  • VETTEL, LYNNE. "LEARNING DETERMINISTIC FINITE AUTOMATA TO CAPTURE TEMPORAL PATTERNS." Master's thesis, University of Cincinnati, 2002. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1037999729

    Chicago Manual of Style (17th edition)

ucin1037999729
607
© 2002, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.