tailieunhanh - Báo cáo khoa học: "Discovering Phonotactic Finite-State Automata by Genetic Search"

This paper presents a genetic algorithm based approach to the automatic discovery of finitestate a u t o m a t a (FSAs) from positive data. FSAs are commonly used in computational phonology, but - given the limited learnability of FSAs from arbitrary language subsets - are usually constructed manually. The approach presented here offers a practical automatic method that helps reduce the cost of manual FSA construction. | Discovering Phonotactic Finite-State Automata by Genetic Search Anja Belz School of Cognitive and Computing Sciences University of Sussex Brighton BN1 9QH UK email Abstract This paper presents a genetic algorithm based approach to the automatic discovery of finite-state automata FSAs from positive data. FSAs are commonly used in computational phonology but - given the limited learnability of FSAs from arbitrary language subsets - are usually constructed manually. The approach presented here offers a practical automatic method that helps reduce the cost of manual FSA construction. 1 Background Finite-state techniques have always been central to computational phonology. Definite FSAs are commonly used to encode phonotactic constraints in a variety of NLP contexts. Such FSAs are usually constructed in a timeconsuming manual process. Following notational convention an FSA is a quintuple 5 z Ớ So F in which s is a finite nonempty set of states 7 is a finite nonempty alphabet s is the state transition function So is the initial state and F is a nonempty set of final states in s. The language L accepted by the finite automaton A denoted 7 A is i 5 s0 r 6 -F . Generally the problem considered here is that of identifying a language L from a fixed finite sample D 7 D- where 7 c L and D n L 0 D may be empty . If D is empty and D is structurally complete with regard to L the problem is not complex and there exist a number of algorithms based on first constructing a canonical automaton from the data set which is then reduced or merged in various ways. If D is an arbitrary strict subset of L the problem is less clearly defined. Since any finite sample is consistent with an infinite number of languages L cannot be identified uniquely from D . .the best we can hope to do is to infer a grammar that will describe the strings in D and predict other strings that in some sense are of the same nature as those contained in D . Fu and Booth 1986 p. 345 To constrain

• Báo cáo khoa học
• Discovering Phonotactic
• Finite State Automata
• Genetic Search
• báo cáo khoa học
• mô hình ngôn ngữ
• xử lý ngôn ngữ tự nhiên
• Bài giảng Xử lý ngôn ngữ tự nhiên
• Ngôn ngữ tự nhiên
• Kỹ thuật lập trình
• Xử lý nhập nhằng ngữ nghĩa
• Xử lý ngữ nghĩa
• Xử lý ngôn ngữ
• Natural Language Processing
• Ngôn ngữ lập trình
• Nhập nhằng cấu trúc
• Tri thức về ngôn ngữ
• Mô hình n gram
• Dịch máy
• Phương pháp dịch máy
• Hiểu ngôn ngữ
• Phân tích ngữ nghĩa
• Phân loại tin tự động
• Biểu diễn vị từ
• Thuộc tính về sự kiện
• Thuộc tính về sự kiện
• Mô hình ngôn ngữ Google Book N grams
• Mô hình ngôn ngữ KenLM
• Phương pháp làm mịn
• Tách từ tiếng Việt
• Gán nhãn từ loại
• Phân tích cú pháp
• Nghĩa từ vựng
• Phân giải nhập nhằng từ
• Phân loại văn bản
• Lexical chain
• Phản hồi thông tin
• Bài toán PTCP
• Cấu trúc ngữ pháp
• Phân tích cú pháp xác suất
• CKY kết hợp xác suất
• Văn phạm phi ngữ cảnh xác suất
• Hình thái học