TAILIEUCHUNG - Báo cáo khoa học: "Polynomial Learnability and Locality of Formal Grammars"

We apply a complexity theoretic notion of feasible learnability called "polynomial learnabillty" to the evaluation of grammatical formalisms for linguistic description. We show that a novel, nontriviai constraint on the degree of ~locMity" of grammars allows not only context free languages but also a rich d ~ s of mildy context sensitive languages to be polynomiaily learnable. We discuss possible implications, of this result t O the theory of naturai language acquisition. | Polynomial Learnability and Locality of Formal Grammars Naoki Abe Department of Computer and Information Science University of Pennsylvania Philadelphia PA19104. ABSTRACT We apply a complexity theoretic notion of feasible learnability called polynomial learnability to the evaluation of grammatical formalisms for linguistic description. We show that a novel nontrivial constraint on the degree of locality of grammars allows not only context free languages but also a rich class of mildy context sensitive languages to be polynomially learnable. We discuss possible implications of this result to the theory of natural language acquisition. 1 Introduction Much of the formal modeling of natural language acquisition has been within the classic paradigm of identification in the limit from positive examples proposed by Gold 7 . A relatively restricted class of formal languages has been shown to be unlearnable in this sense and the problem of learning formal grammars has long been considered intractable. 1 The following two controversial aspects of this paradigm however leave the implications of these negative results to the computational theory of language acquisition inconclusive. First it places a very high demand on the accuracy of the learning that takes place - the hypothesized language must be exactly equal to the target language for it to be considered correct . Second it places a very permissive demand on the time and amount of data that may be requừed for the learning - all that is required of the learner is that it converge to the correct language in the Of the many alternative paradigms of learning proposed the notion of polynomial learnability recently formulated by Blumer et al. 6 is of particular interest because it addresses both of these problems in a unified Supported by an IBM graduate fellowship. The author gratefully acknowledges his advisor Scott Weinstein for his guidance and encouragement throughout this research. 1Some interesting learnable .

• Báo cáo khoa học
• Polynomial Learnability
• Locality of Formal Grammars
• Naoki Abe
• 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