TAILIEUCHUNG - Báo cáo khoa học: "Efficient Staggered Decoding for Sequence Labeling"

The Viterbi algorithm is the conventional decoding algorithm most widely adopted for sequence labeling. Viterbi decoding is, however, prohibitively slow when the label set is large, because its time complexity is quadratic in the number of labels. This paper proposes an exact decoding algorithm that overcomes this problem. A novel property of our algorithm is that it efficiently reduces the labels to be decoded, while still allowing us to check the optimality of the solution. | Efficient Staggered Decoding for Sequence Labeling Nobuhiro Kaji Yasuhiro Fujiwara Naoki Yoshinaga Masaru Kitsuregawa Institute of Industrial Science The University of Tokyo 4-6-1 Komaba Meguro-ku Tokyo 153-8505 Japan kaji fujiwara ynaga kisture @ Abstract The Viterbi algorithm is the conventional decoding algorithm most widely adopted for sequence labeling. Viterbi decoding is however prohibitively slow when the label set is large because its time complexity is quadratic in the number of labels. This paper proposes an exact decoding algorithm that overcomes this problem. A novel property of our algorithm is that it efficiently reduces the labels to be decoded while still allowing us to check the optimality of the solution. Experiments on three tasks POS tagging joint POS tagging and chunking and supertagging show that the new algorithm is several orders of magnitude faster than the basic Viterbi and a state-of-the-art algorithm CarpeDiem Esposito and Radi-cioni 2009 . 1 Introduction In the past decade sequence labeling algorithms such as HMMs CRFs and Collins perceptrons have been extensively studied in the field of NLP Rabiner 1989 Lafferty et al. 2001 Collins 2002 . Now they are indispensable in a wide range of NLP tasks including chunking POS tagging NER and so on Sha and Pereira 2003 Tsuruoka and Tsujii 2005 Lin and Wu 2009 . One important task in sequence labeling is how to find the most probable label sequence from among all possible ones. This task referred to as decoding is usually carried out using the Viterbi algorithm Viterbi 1967 . The Viterbi algorithm has O NL2 time complexity 1 where N is the input size and L is the number of labels. Although the Viterbi algorithm is generally efficient 1The first-order Markov assumption is made throughout this paper although our algorithm is applicable to higher-order Markov models as well. it becomes prohibitively slow when dealing with a large number of labels since its computational cost is

• Báo cáo khoa học
• Efficient Staggered Decoding
• Sequence Labeling
• Nobuhiro Kaji Yasuhiro Fujiwara Naoki Yoshinaga Masaru Kitsuregawa
• báo cáo khoa học
• báo cáo ngôn ngữ
• ngôn ngữ tự nhiên
• Bài giảng Xử lý ngôn ngữ tự nhiên
• Xử lý ngôn ngữ tự nhiên
• Kỹ thuật lập trình
• Mô hình 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 loại tin tự động
• Tạo chí tin học
• Điều khiển học
• Truy vấn ngôn ngữ tự nhiên
• Phép dịch truy vấn ngôn ngữ tự nhiên
• Truy vấn SQL
• Văn phạm ngữ nghĩa
• Xử lý nhập nhằng ngữ nghĩa
• Xử lý ngữ nghĩa
• Phân tích ngữ nghĩa
• Biểu diễn vị từ
• Thuộc tính về sự kiện
• Thuộc tính về sự kiện
• 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 ngôn ngữ Google Book N grams
• Mô hình ngôn ngữ KenLM
• Phương pháp làm mịn
• Bài toán PTCP
• Phân tích cú pháp
• 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
• Gán nhãn từ loại
• Ngôn ngữ tự nhiên trong dịch máy
• Hệ thống dịch máy
• Phương pháp xây dựng bảng từ
• Tác từ
• Conditional random fields
• Nhận dạng thực thể có tên
• Đối tượng vật lý trừu tượng
• Phân lớp văn bản
• Biểu diễn nhị phân
• Ma trận từ văn bản
• Wolfram Alpha
• Trích rút thông tin
• Phương pháp Snowball