Luận văn ThS: Mô hình ngôn ngữ sử dụng MapReduce - ĐH Công Nghệ
Luận văn thạc sĩ phân tích mô hình ngôn ngữ sử dụng mapreduce luận văn ths máy tính 60 48 01, đánh giá thực trạng, chỉ ra hạn chế, đề xuất giải pháp khả thi cho thực tiễn.
Trường đại học
Trường Đại Học Công Nghệ - Đại Học Quốc Gia Hà NộiChuyên ngành
Công Nghệ Thông TinNgười đăng
Ẩn danhThể loại
Luận Văn Thạc SĩPhí lưu trữ
30 PointMục lục chi tiết
Tóm tắt
I. Tổng Quan Luận Văn Mô Hình Ngôn Ngữ MapReduce 55 ký tự
Luận văn này nghiên cứu việc áp dụng mô hình ngôn ngữ vào lĩnh vực xử lý ngôn ngữ tự nhiên, đặc biệt là sử dụng mô hình N-gram. Mô hình ngôn ngữ là phân bố xác suất của một đoạn văn bản trên một tập văn bản lớn. Mục tiêu là xây dựng mô hình ngôn ngữ chính xác hơn thông qua việc sử dụng MapReduce để xử lý dữ liệu lớn. Luận văn tập trung vào cải tiến tốc độ xây dựng mô hình ngôn ngữ và ước lượng mô hình. Việc sử dụng Hadoop và MapReduce giúp giải quyết bài toán với dữ liệu huấn luyện lớn. Phương pháp làm mịn Good-Turing được sử dụng trong ứng dụng xây dựng mô hình ngôn ngữ với MapReduce. Các phương pháp làm mịn khác như Kneser-Ney có thể cho kết quả tốt hơn nhưng do thời gian có hạn. Luận văn được trình bày trong bốn chương, bao gồm giới thiệu, các khái niệm cơ bản, ứng dụng MapReduce vào mô hình ngôn ngữ, và kết quả thực nghiệm. Đề tài này có ý nghĩa quan trọng trong việc phát triển các ứng dụng như kiểm tra chính tả, nhận dạng giọng nói, và dịch máy thống kê. Nội dung luận văn tập trung vào việc giải quyết vấn đề xử lý dữ liệu lớn trong xây dựng mô hình ngôn ngữ, tận dụng sức mạnh của Hadoop và MapReduce để cải thiện hiệu suất và độ chính xác. Các nghiên cứu trước đây thường gặp khó khăn khi xử lý dữ liệu lớn, dẫn đến hạn chế về khả năng xây dựng mô hình ngôn ngữ chính xác. Luận văn này đề xuất một phương pháp tiếp cận mới, sử dụng các công cụ và kỹ thuật tiên tiến để vượt qua những hạn chế này.
1.1. Giới thiệu về Mô Hình Ngôn Ngữ N gram 40 ký tự
Mô hình N-gram là một phương pháp phổ biến để mô hình hóa ngôn ngữ. Nó sử dụng các tập dữ liệu văn bản lớn để ước lượng xác suất của mô hình. Nhìn chung, dữ liệu càng lớn thì mô hình sẽ càng tốt hơn. Mô hình N-gram sử dụng xấp xỉ Markov để dự đoán xác suất của một từ khi biết một số từ trước đó. Các loại mô hình N-gram bao gồm Unigram, Bigram, và Trigram. Luận văn sử dụng ước lượng hợp lý hóa cực đại (MLE) để tính xác suất N-gram. Tuy nhiên, việc xây dựng mô hình N-gram gặp phải một số khó khăn, bao gồm sự phân bố không đều và kích thước bộ nhớ lớn. Sự phân bố không đều có thể dẫn đến các ước lượng không chính xác. Khi các N-gram phân bố thưa, nhiều cụm n-gram không xuất hiện hoặc chỉ có số lần xuất hiện nhỏ, việc ước lượng các câu có chứa các cụm n-gram này sẽ có kết quả tồi. Để khắc phục tình trạng này, người ta phải sử dụng một số phương pháp “làm mịn”. Kích thước bộ nhớ cũng là một vấn đề lớn, đặc biệt khi kích thước tập văn bản huấn luyện lớn. Để xây dựng mô hình ngôn ngữ hiệu quả, chúng ta phải giảm kích thước của mô hình ngôn ngữ mà vẫn đảm bảo độ chính xác.
1.2. Mục tiêu và cấu trúc của Luận Văn 42 ký tự
Mục tiêu chính của luận văn là nghiên cứu sử dụng Hadoop và MapReduce vào việc xây dựng mô hình ngôn ngữ nhằm cải tiến tốc độ cho việc xây dựng mô hình ngôn ngữ và ước lượng mô hình để có thể thực hiện với lượng dữ liệu rất lớn để đưa ra mô hình ngôn ngữ chính xác hơn. Nội dung luận văn được trình bày trong bốn chương. Chương 1 trình bày các khái niệm cơ bản về mô hình ngôn ngữ, mô hình N-gram, các phương pháp làm mịn và các độ đo dùng để đánh giá mô hình ngôn ngữ. Chương 2 trình bày các kiến thức cơ bản về Hadoop và MapReduce, giới thiệu về kiến trúc của Hadoop, MapReduce cũng như cơ chế làm việc của chúng. Chương 3 sẽ trình bày về việc ứng dụng Hadoop và MapReduce vào mô hình ngôn ngữ. Chương 4 giới thiệu về công cụ thực nghiệm và kết quả thực nghiệm. Phần kết luận đưa ra kết luận, định hướng phát triển cho đề tài. Cuối cùng là tài liệu tham khảo.
II. Các Phương Pháp Làm Mịn Mô Hình Ngôn Ngữ N gram 59 ký tự
Để khắc phục tình trạng các cụm N-gram phân bố thưa, luận văn trình bày các phương pháp làm mịn. Thuật ngữ làm mịn (smoothing) sử dụng cho việc đánh giá lại xác suất của các cụm N-gram. Các phương pháp làm mịn có thể chia thành các loại như sau: Chiết khấu (Discounting): giảm xác suất của các cụm N-gram có xác suất lớn hơn 0 để bù cho các cụm N-gram không xuất hiện trong tập huấn luyện. Ví dụ: phương pháp Add-one, Good-Turing. Truy hồi (Back-off): tính toán xác suất của các cụm N-gram không xuất hiện trong tập huấn luyện dựa vào các cụm N-gram ngắn hơn có xác suất lớn hơn 0. Ví dụ: Katz back-off. Nội suy (Interpolation): tính toán xác suất của tất cả các cụm N-gram dựa vào xác suất của các cụm N-gram ngắn hơn. Luận văn tập trung vào phương pháp làm mịn Add-one và Good-Turing. Các phương pháp làm mịn giúp cải thiện độ chính xác của mô hình ngôn ngữ, đặc biệt khi dữ liệu huấn luyện bị thưa thớt. Lựa chọn phương pháp làm mịn phù hợp là một yếu tố quan trọng trong việc xây dựng mô hình ngôn ngữ hiệu quả.
2.1. Tìm hiểu Phương Pháp Add one Laplace Smoothing 47 ký tự
Phương pháp làm mịn Add-one, còn gọi là Laplace Smoothing, cộng thêm 1 vào tần số xuất hiện của tất cả các cụm N-gram. Công thức tính xác suất của các cụm 1 từ wi với tần suất xuất hiện là ci là: P(wi) = Ci / N. Phương pháp Add-one thêm 1 vào các ci, với V là số các từ trong bộ dữ liệu từ điển, ta có xác suất như sau: PAdd-one(wi) = (Ci+1) / (N+V). Thuật toán này sẽ làm thay đổi đáng kể xác suất của các cụm N-gram đã xuất hiện trong tập huấn luyện nếu kích thước bộ từ điển V là rất lớn. Trong thực nghiệm, một vài cụm N-gram có xác suất giảm đi gần 10 lần, do kích thước bộ từ điển là lớn trong khi tần số xuất hiện của cụm Ngram đó không cao. Phương pháp Add-one có ưu điểm là dễ cài đặt tính toán. Nhược điểm là làm giảm xác suất của những cụm từ hay xuất hiện trong tập huấn luyện. Nếu tỉ lệ các từ không xuất hiện càng lớn thì xác suất gán cho các từ này sẽ tăng và làm giảm đáng kể xác suất của các từ khác.
2.2. Phương pháp Good Turing Chi tiết thuật toán 50 ký tự
Thuật toán Good-Turing thực hiện ước lượng lại xác suất của những cụm từ (N-gram) có tần suất bằng 0 dựa trên số các từ có tần suất xuất hiện bằng 1. Thuật toán Good-Turing dựa trên việc tính toán Nc, với Nc là số cụm N-gram xuất hiện c lần. Như vậy: N0 là số cụm n-gram có tần số 0 (số cụm N-gram không xuất hiện lần nào), N1 là số cụm n-gram có tần số 1 (số cụm N-gram xuất hiện 1 lần). Với mỗi c, một ước lượng tần số được tính như sau: c* = (c+1) * Nc+1 / Nc. Người ta không tính toán và thay thế mọi tần số c bởi một tần số mới c*. Người ta chọn một ngưỡng k nhất định, và chỉ thay thế tần số c bởi tần số mới c* khi c nhỏ hơn hoặc bằng k, còn nếu c lớn hơn k thì giữ nguyên tần số.
III. Hadoop MapReduce Giải Pháp Cho Dữ Liệu Lớn 55 ký tự
Luận văn giới thiệu về Hadoop và MapReduce như một công cụ để xử lý dữ liệu khổng lồ. Hadoop là framework mã nguồn mở dựa trên Java và sử dụng hệ thống tệp phân tán Hadoop (HDFS). Hadoop hiện thực mô hình Mapreduce, trong đó ứng dụng sẽ được chia nhỏ ra thành nhiều phân đoạn khác nhau và các phần này sẽ được chạy trên nhiều node khác nhau. Kiến trúc Hadoop bao gồm các thành phần chính như HDFS, MapReduce, Hive, HBase, và Pig. HDFS duy trì một cấu trúc cây phân cấp các tệp, lưu trữ dữ liệu bằng các blocks. MapReduce được thiết kế bởi Google như một mô hình lập trình xử lý tập dữ liệu lớn song song. Chương trình MapReduce chạy với hai giai đoạn: Map và Reduce. MapReduce giúp giải quyết bài toán xây dựng mô hình ngôn ngữ với dữ liệu lớn. Quá trình phân tích dữ liệu tập huấn luyện trong Google được chia thành ba bước: Chuyển các từ thành các id, sinh ra các n-gram trên từng câu và tính toán xác xuất của các n-gram.
3.1. Kiến trúc Hadoop HDFS và các thành phần 48 ký tự
Hadoop bao gồm các thành phần sau: HDFS – Hệ thống tệp phân tán, MapReduce: Mô hình xử lý dữ liệu phân tán, Hive: Kho dữ liệu phân tán, cung cấp SQL dựa trên ngôn ngữ truy vấn, HBase: Cơ sở dữ liệu dựa trên cột phân tán, Pig: Ngôn ngữ dòng dữ liệu và môi trường thực thi. HDFS duy trì một cấu trúc cây phân cấp các tệp. Các tệp được lưu trữ bằng một hay nhiều Block. Mỗi block có kích thước là 64MB và có một Id riêng. HDFS có một kiến trúc master/slave, trên một cluster chạy HDFS, có hai loại node là Namenode và Datanode. Một cluster có duy nhất một Namenode và có một hay nhiều Datanode. Namenode đóng vai trò là master, chịu trách nhiệm duy trì thông tin về cấu trúc cây phân cấp các tệp, thư mục của hệ thống tệp và các metadata khác của hệ thống tệp.
3.2. Quy trình MapReduce Chi tiết các giai đoạn 47 ký tự
MapReduce hoạt động như sau: Đầu tiên các tệp đầu vào được chia nhỏ ra thành các khối nhỏ hơn có tên là FileSplits và hàm Map tạo ra các phần song song với từng task trên các FileSplit. Các file đầu vào được coi là một cặp khóa / giá trị và lập trình viên dùng một hàm Map để xử lý các cặp khóa/giá trị để tạo ra một tập các cặp khóa / giá trị trung gian. Khi hàm Map kết thúc đầu ra được đưa tới các Partitioner thường là một hàm băm, tất cả các cặp có cùng khóa sẽ được tập hợp cùng nhau. Sau khi các cặp trung gian được tạo ra một hàm Combine sẽ được gọi để reduce trong mỗi nút để tăng tốc độ xử lý. Sau đó một hàm Reduce trộn tất cả các giá trị cùng key và ghi vào các tệp đầu ra.
IV. Ước Lượng Mô Hình Ngôn Ngữ Với MapReduce Hướng Dẫn 59 ký tự
Để ước lượng mô hình ngôn ngữ được chính xác thì cần phải sử dụng bộ dữ liệu huấn luyện lớn. Hadoop và MapReduce là một công cụ để xử lý dữ liệu khổng lồ. Quá trình phân tích dữ liệu tập huấn trong Google được chia thành ba bước: Chuyển các từ thành các id, sinh ra các n-gram trên từng câu và tính toán xác xuất của các n-gram. Luận văn sử dụng ước lượng làm mịn Good-Turing và một số bước phụ thêm bao gồm tính toán số lượng của các n-gram, lưu các số lượng này trong HDFS và sau đó lấy dữ liệu để điều chỉnh các số lượng. Bước đầu tiên là phân tích dữ liệu huấn luyện, tìm tất cả các n-gram và số lượng của chúng. Hàm map sẽ đọc từng dòng trong dữ liệu đầu vào. Khóa là docid, và giá trị là văn bản.
4.1. Đếm số lần xuất hiện Generate count of counts 50 ký tự
Kỹ thuật làm mịn Good – Turing được dựa trên việc đếm số lượng của các n- gram. Vì vậy cần thiết phải tập hợp tất cả số lượng của số các 1-gram, 2-gram, 3- gram cho đến n-gram. Để làm được việc này thì tất cả các dòng số lượng được đưa vào một MapReduce mới. Cho mỗi n-gram, hàm map sẽ đưa ra một số của dòng số lượng với thứ tự của n-gram và khóa đưa ra sẽ có dạng <n-gram – oder raw-counts> và giá trị là
4.2. Sinh Số Làm Mịn Good Turing Chi tiết công thức 54 ký tự
Với công thức làm mịn Good-Turing chúng ta có thể ước lượng số được làm mịn cho mỗi n-gram. Trong bước này các dữ liệu đầu vào vẫn là các n-gram và các số đếm của chúng, mỗi hàm map sẽ đọc trong từng dòng số của các số, lưu tất cả dữ liệu trong cấu trúc HashMap và tính số được làm mịn. Theo công thức là: Nr+1 r* = (r+1) Nr. Nếu có thể tìm cả Nr+1 và Nr trong HashMap thì công thức trên có thể áp dụng trực tiếp. Ngược lại sẽ thử tìm trong số của số lượng gần nhất, nếu không thể tìm được Nr+1 thì sẽ thử tìm Nr+2, Nr+3, Nr+4, … Trong phần thử nghiệm chúng tôi đã tìm trong hầu hết 5 số Nr+1, …, Nr+5. Nếu không tìm thấy bất kỳ những số này, thì sẽ dùng số đếm thô để thay thế.
4.3. Ước Lượng Xác Suất N gram 40 ký tự
Để ước lượng xác suất của một n-gram w1,w2,…,wn, chúng ta cần số lượng của w1,…,wn và w1… wn-1. Bởi vì một chương trình MapReduce mỗi map hoặc reduce đang làm việc dựa trên một khóa, Thử nghiệm sẽ sử dụng chuỗi w1,w2 ,…,wn-1 như là khóa và tổ hợp từ wn với số lượng của từ đó là giá trị. Việc này hoàn thành trong hàm map ở bước trước. Sau khi làm mịn Good-Turing một vài số có thể khá nhỏ, vì vậy xác suất có thể lớn hơn 1. Trong trường hợp này chúng ta cần điều chỉnh nó xuống 1. Cho một mô hình back-off chúng ta sử dụng một khối đơn giản được cung cấp bởi Google, trong đó số back-off được đặt là 0.4 được chọn dựa trên kinh nghiệm và được phát triển trên các lựa chọn của các bước trước.
V. Bảng Hbase Lưu Trữ Xác Suất Mô Hình Ngôn Ngữ 55 ký tự
Luận văn trình bày về việc sử dụng bảng Hbase để lưu trữ các xác suất mô hình ngôn ngữ. Hbase có thể sử dụng khi đưa đầu vào hoặc ra vào trong các Hadoop và MapReduce. Các sửa đổi là cần thiết bởi vì bảng Hbase được viết theo từng dòng, mỗi khi chúng ta cần sinh ra một khóa với nội dung là các cột. Có một vài lựa chọn ở đây, hoặc đơn giản là cho mỗi n-gram trên một dòng, hoặc nhiều dòng được cấu trúc dựa trên từ hiện tại và nội dung. Có hai vấn đề lớn cần phải quan tâm là tốc độ viết/truy vấn và kích thước bảng lưu trữ. Các cấu trúc bảng Hbase được đề xuất bao gồm cấu trúc dựa trên n-gram, cấu trúc dựa trên từ hiện tại, cấu trúc dựa trên đoạn văn, cấu trúc dựa trên nửa ngram, và cấu trúc dựa trên số nguyên.
5.1. Các cấu trúc bảng Hbase So sánh ưu nhược điểm 55 ký tự
Một cấu trúc khởi tạo là rất đơn giản tương tự như định dạng đầu ra của đoạn văn bản. Mỗi n-gram được lưu trữ trong một dòng riêng biệt, vì vậy bảng có cấu trúc phẳng với một cột. Cho mỗi dòng, khóa là n-gram và cột lưu trữ xác xuất của chúng. Cho tất cả các n-gram w1,w2,…,wn cùng chia sẻ một từ hiện tại wn chúng ta có thể lưu trữ chúng trong một dòng với cùng một khóa wn. Tất cả các ngữ cảnh có khả năng xảy ra sẽ được lưu trữ vào những cột riêng biệt, tên cột được đặt theo định dạng
5.2. Truy Vấn Trực Tiếp Phương Pháp Back off đơn giản 53 ký tự
Quá trình xử lý tiếp theo là kiểm thử. Phương pháp back-off được thực hiện trong câu truy vấn ở đây. Dựa trên mô hình back-off cho mỗi n-gram thử nghiệm chúng ta cần truy vấn n-gram nếu không tìm thấy thì sẽ tìm trong n-1 gram cho đến khi chúng ta gặp 1-gram. Cho cấu trúc bảng khác chúng ta cần sinh ra các dòng khác nhau và đặt tên cho các cột. Ưu điểm của việc sử dụng MapReduce cho việc thử nghiệm là chúng ta có thể đưa nhiều chuỗi thử nghiệm vào HDFS và MapReduce có thể xử lý trong tất cả các chuỗi để đưa ra số đếm thô của chúng. Phương thức này được gọi là truy vấn trực tiếp bởi vì nó truy vấn mỗi n-gram trực tiếp từ bảng Hbase.
VI. Đánh Giá Thực Nghiệm So Sánh Hiệu Năng 50 ký tự
Luận văn trình bày về các phương pháp đánh giá trên sự so sánh về chi phí thời gian và không gian lưu trữ sử dụng các cấu trúc bảng khác nhau. Cũng như độ hỗn loạn mô hình ngôn ngữ cho tập thử nghiệm được đánh giá và so sánh với các công cụ mô hình ngôn ngữ truyền thống. Các phương pháp đánh giá bao gồm đánh giá thời gian và bộ nhớ, và so sánh độ hỗn loạn thông tin mô hình ngôn ngữ. Các thực nghiệm được xây dựng trên một môi trường cluster với hai node và một máy chủ. Node được chạy với Hadoop, HDFS và máy chủ thì kiểm soát tất cả. Phần thực nghiệm được thực hiện với quá trình huấn luyện mô hình.
6.1. Môi Trường Chạy Thực Nghiệm và Dữ Liệu 46 ký tự
Các thực nghiệm được chạy trên công cụ mã nguồn mở và được chạy trên máy có cấu hình như sau: CPU model: Intel ® Core™ i3-2310M CPU@2.00 GB, Hệ điều hành: Ubuntu 15.2. Dữ liệu để thực hiện huấn luyện là dữ liệu trên ngôn ngữ tiếng Anh. Dữ liệu được lấy từ website http://www.org/wmt15/translation-task. Dữ liệu có cấu trúc mỗi câu trên một dòng. Xấp xỉ giữa kích thước dữ liệu và số từ như bảng sau: Dung lượng Số từ, 790MB 159 triệu.
6.2. Đánh Giá Thời Gian Bộ Nhớ cho các Ngram 46 ký tự
Trong phần thực nghiệm của mình, chúng tôi đã chọn thử nghiệm từ 1-gram tới 3-gram. Một số đếm tỉa bằng 1 được áp dụng cho tất cả các mô hình. sẽ chỉ ra số lượng của 1-gram cho các thứ tự trên tập huấn luyện. sẽ cho biết số lượng 1-gram cho tập huấn luyện. Thời gian chạy được đưa ra trong hình 4. Chúng ta có thể xem trong bảng 4.3, khi số lượng các từ nhỏ thì thời gian chạy gần như giống nhau, nhưng khi số lượng các từ lớn hơn, thì sự khác nhau giữa các mô hình 1-gram, 2-gram, 3-gram là tăng lên rất nhiều. Một khía cạnh khác ảnh hưởng đến thời gian chạy trong quá trình huấn luyện đó là job MapReduce thứ hai cần phải ước lượng số lần xuất hiện của các từ cho làm mịn Good-Turing.
23/09/2025
