☕ Nhàn đàm ICT: MapReduce ⦀

Phác họa bài post:

ⓐ BigFiles, Clusters.

ⓑ Ý tưởng MapReduce.

ⓒ Implementation (cài đặt thực thi).

ⓓ Dataflow (dòng chảy dữ liệu).

ⓔ Performance (Hiệu suất).

ⓕ Experience (trải nghiệm MapReduce tại Google).

ⓖ Hadoop, Spark

~

Để giúp anh/chị quyết định có đọc tiếp hay không, tôi xin phép cung cấp các thông tin liên quan đến bài post này như sau:

·       Chủ đề: Mô hình lập trình, điện toán phân tán, hệ điều hành.

·       Tính thời sự: Năm 2004 (có đề cập vài thông tin gần đây: 2020, 2021).

·       Thời gian đọc: 7 phút, lồng vào thời gian uống cà phê (uống cà phê xong là đọc xong).

-

Xin phép anh/chị hôm nay chúng ta nhàn đàm về mô hình lập trình phân tán không đồng bộ MapReduce. Đối với anh/chị lâu năm trong nghề thì mô hình này đã trở thành “kinh điển”, không có gì mới để đàm luận. Riêng cá nhân tôi, khi đọc lại bài báo (đăng năm 2004) của Jeffrey Dean và Sanjay Ghemawat, tôi vẫn cảm nhận được tính đột phá của ý tưởng. Hơn nữa, ý tưởng này lại được trình bày đơn giản, dễ hiểu đến mức bất ngờ thú vị. Vì vậy, dành thời gian khoảng 5-7 phút để vừa nhâm nhi cà phê vừa “ôn lại” ý tưởng làm nền cho Big Data cất cánh thì có lẽ cũng “đáng lắm”. 😊

⦀

ⓐ BigFiles, Clusters.

Trước khi bàn đến MapReduce, mời anh/chị tham khảo lại ý tưởng BigFiles do Larry Page và Sergey Brin, hai đồng sáng lập viên công ty Google, đề xuất. BigFiles còn có một tên khác là GFS, viết tắt của cụm từ Google File System. Ý tưởng rất đơn giản. Nếu mỗi một máy tính có một hệ thống file thì một cụm máy tính (cluster) cũng có một hệ thống file của nó. Đấy chính là hệ thống tổng hợp của toàn bộ các file trên các máy tính đơn lẻ của cụm gộp lại. Mỗi một file là tổ hợp của nhiều đoạn (Chunk) 64MB hợp thành. Mỗi một Chunk có một ID riêng, ID là một dãy 64 bit. Một file có thể gồm nhiều đoạn nằm rải rác ở nhiều máy trong cụm. GFS có cấu trúc phân cấp và có cơ chế nhân bản (replicate) nhằm đảm bảo mức độ an toàn của nội dung lưu. Mức replicate mặc định bằng 3 (có thể cấu hình thay bằng một mức khác). Tức là nội dung trên đĩa luôn luôn có 3 bản sao nằm ở 3 vị trí khác nhau. Xác suất để nội dung ở 3 vị trí này cùng đồng thời bị hỏng là cực nhỏ.

Cụm máy tính của Google có 2 loại máy là Master server (gọi là nút Master) và Chunk server (gọi là nút lưu). Nút Master không lưu file, chỉ làm nhiệm vụ quản lý: bảng ánh xạ (mapping) các ID đến các nút lưu.

Một tiến trình (process) muốn truy cập file, trước hết cần nút Master cấp phép. Sau khi được cấp phép, tiến trình đó được phép liên lạc với nút lưu trong một khoảng thời gian nhất định. Việc thay đổi nội dung của một Chunk nào đó được thực hiện giống như một giao dịch trong các phép toán của cơ sở dữ liệu: giao dịch nguyên tử (atomic transaction) ACID (Atomicity, Consistency, Isolation, Durability). Nghĩa là dữ liệu của GFS luôn luôn được đảm bảo tính toàn vẹn (integrity).

Do có replication (cơ chế nhân bản tự động) nên GFS có mức độ an toàn dữ liệu rất cao, mặc dù các máy Chunk server (nút lưu) có thể chỉ là các loại máy thông thường, giá rẻ.

⦀

ⓑ Ý tưởng MapReduce.

Để hiểu bối cảnh ra đời của MapReduce, chúng ta quay trở lại thời gian các năm xung quanh năm 2000 (1998-2002), lúc mà Google chỉ mới là công ty Startup trong lĩnh vực tìm kiếm trên mạng Internet (Web Search). Mỗi một ngày, sau khi đi lục tìm trên Internet các trang web (web crawling), kho dữ liệu của Google lớn lên từng giờ mà kết quả tìm kiếm phải đảm bảo thời gian chỉ trên dưới 0.5 giây cho mỗi yêu cầu của lệnh tìm kiếm. Không một máy tính đơn lẻ nào đủ mạnh để thực hiện việc này, vì dữ liệu tích tụ càng ngày càng nhiều. Cần phải có một cơ chế tính toán song song hoặc xử lý phân tán nào đó trên nhiều máy (cụm máy) để giải bài toán nan giải này. Đó là bối cảnh ra đời của MapReduce: phân tán xử lý cùng một công việc nhưng được chia ra cho nhiều máy. Cũng cần nói thêm là ở Google, họ đã xử lý phân tán trước MapReduce rồi nhưng các phần mềm đó “tự chịu trách nhiệm” xử lý phân tán, chưa sử dụng chung một khung mô hình.

-

Lấy một ví dụ, giả thiết cụm máy tính của Google có 1,000 máy, hệ thống file được tổ chức theo mô hình GFS (xem ở mục trước). Giả thiết rằng hệ thống có hàng triệu tài liệu nằm rải rác trên 1,000 máy này. Một bài toán đơn giản như tính số lần xuất hiện của các từ (word) trong hàng triệu tài liệu đó đòi hỏi phần mềm phải quét hết tất cả các file trên hệ thống. Cách mà MapReduce tiếp cận là chia công việc này cho tất cả 1,000 máy “cùng thực hiện”. Mỗi máy chủ yếu chỉ “quét” các file lưu trên đĩa cứng của máy đó hoặc các máy “bên cạnh”. Bằng cách này, các máy tiết kiệm thời gian truyền tin từ máy này sang máy khác và vì các máy song hành nên thời gian xử lý = max (thời gian xử lý của từng máy trong 1,000 máy). Chúng ta dễ dàng nhận ra rằng thời gian xử lý này ngắn hơn nhiều so với tổng thời gian xử lý của 1,000 máy.
⚠ Bất đẳng thức: max (x₁, x₂, …, x_n) ≤ x₁ + x₂ + … + x_n, trong đó x_i > 0.

-

➡ Mô hình MapReduce chia việc xử lý tính toán thành 2 hàm: Map và Reduce.

·       Map (k1, v1)                ⟶ list (k2, v2)

·       Reduce (k2, list(v2))   ⟶ list (v2)

-

Quy ước ký hiệu: k: key (khóa); v: value (giá trị); các từ viết tắt k1, v1, k2, v2: là ký hiệu loại dữ liệu (type).

-

Mã lệnh của hai hàm Map và Reduce do người dùng viết. Điều đó có nghĩa là người dùng chỉ định công việc cho Map và cho Reduce thực thi.

Chú ý là đầu ra của Map, list (k2, v2), được sắp xếp theo khóa k2; sau đó trở thành đầu vào của Reduce: (k2, list(v2)).

⚠ Chúng ta chú ý thêm đặc điểm của hàm Reduce. Hàm Reduce thông thường chỉ làm phép toán tổng hợp. Thế nào là một phép toán tổng hợp? Là một phép toán trên toàn bộ các bản ghi. Ví dụ: đếm số bản ghi, tổng của N con số, đếm số lần xuất hiện của một từ nào đó trong N bản ghi, …

-

❓   Thế vai trò của hệ thống là gì? Vai trò của hệ thống là phân chia công việc của Map cho M Worker và công việc của Reduce cho R Worker. Worker là chương trình chạy trên một máy tính. Như vậy, vai trò của hệ thống là chia việc cho nhiều Worker cùng thực hiện. Công việc phân chia này được hệ thống “ẩn” đi, người lập trình khỏi phải bận tâm.
-
Ngoài ra, hệ thống trộn đầu ra của hàm Map thành đầu vào cho hàm Reduce (xem đầu vào và đầu ra của các hàm Map và Reduce).

Ngôn ngữ lập trình của MapReduce là C++. Việc điều hành phân chia công việc, trộn, sắp xếp dữ liệu trung chuyển được thực hiện thông qua một thư viện (library).

⚠ Khi lập trình cho các hàm Map và Reduce, các hàm này nằm trong một lớp (Class) nào đó do người dùng định nghĩa nhưng lớp này phải thừa kế các lớp của thư viện MapReduce. Ví dụ: hàm Map nằm trong lớp thừa kế lớp Mapper, hàm Reduce nằm trong lớp thừa kế lớp Reducer. Anh/chị nào là dân kỹ thuật lập trình thì nên tham khảo Phụ lục A của bài báo (cuối bài).

⦀

ⓒ Implementation (cài đặt thực thi).

Bối cảnh để cài đặt MapReduce là hệ thống máy của Google vào khoảng năm 2000: cụm máy tính gồm hàng ngàn máy PC (giá rẻ: 4GB RAM, đĩa cứng 160GB IDE), các máy được nối với nhau bằng các bộ switch Ethernet tốc độ 100/1000 Gigabit/s. Vì là các máy PC thông thường nên hệ thống cần tính đến trường hợp máy bị “treo” hoặc đĩa cứng “trục trặc”. File của cụm máy được tổ chức theo hệ thống GFS (xem mục ⓐ). Các máy chạy hệ điều hành Linux.

-

Để tránh bị hiểu nhầm, xin phép anh/chị chúng ta thống nhất dùng từ tiếng Anh. Các tiến trình/chương trình đang chạy trên các máy trong mạng được gọi là “Worker”. Các công việc mà Map hay Reduce thực hiện được gọi là “Task” (tác vụ).

-

➡ Nhìn một cách tổng quan: đầu vào của Map được chia thành M mảnh, việc xử lý các mảnh này được các Worker thực hiện song song. Tương tự như vậy, công việc của Reduce cũng được chia thành R vùng, được các Worker cùng thực hiện song song.

1.     MapReduce đầu tiên chia đầu vào của hàm Map thành M mảnh và đồng thời cho khởi động các Worker trên các máy trạm. (Trong HĐH Linux, lệnh này là fork).

2.     Trong số này có một Worker đặc biệt, có tên là Master, điều hành các Worker còn lại. Lúc này, Map có M Task, Reduce có R Task.

3.     Một Worker tương ứng với Map xử lý đầu vào từ 1 phân mảnh trong tổng số M phân mảnh. (Thực chất: Worker này gọi hàm đã được người dùng định nghĩa.) Đầu ra của Map được lưu tạm thời trong RAM.

4.     Một cách định kỳ, căn cứ vào giá trị của khóa k2, Worker (của Map) sẽ xác định được vùng tương ứng trong số R vùng và ghi dữ liệu lên đĩa cứng của máy trạm. (Thuật toán “xác định vùng” thường được dùng là hàm băm modulo R: hash(k2) Mod R.) Sau đó Worker này báo cho Master biết vị trí tương ứng của đĩa cứng. Tiếp theo, Master báo cho Worker của Reduce biết vị trí này.

5.     Khi một Worker của Reduce biết được vị trí trên, Worker này sẽ sử dụng hàm RPC (Remote Procedure Call: máy này gọi một hàm trên máy kia) để đọc dữ liệu về máy của mình. Sau khi đọc xong, Worker của Reduce phải sắp xếp dữ liệu (Sort) theo khóa k2, nhằm sắp xếp tất cả các giá trị cùng một khóa theo cùng một danh mục.

6.     Tiếp theo, Worker của Reduce lập một vòng lặp: lần lượt đọc tất các các khóa k2 và danh mục giá trị tương ứng, gọi hàm Reduce do người dùng định nghĩa. Đầu ra của hàm Reduce này sẽ được nối thành một file, tương ứng với một vùng của Reduce.

7.     Sau khi toàn bộ các Worker của Map và Reduce hoàn thành công việc, Master sẽ trả lại điều khiển cho chương trình người dùng.

Cuối cùng, người dùng được cái gì? Đó là R file (tương ứng với R vùng của Reduce)! Việc sử dụng R file đó như thế nào là việc của người dùng.

-

Tóm tắt: {Map} ⟶ [M x R file trung gian] ⟶ {Trộn} ⟶ {Reduce} ⟶ [R file kết quả]

-

➡ Thế Master điều khiển hệ thống như thế nào?

Master có bảng ghi tình trạng của tất cả các Task, có tất cả 3 trạng thái:
- Idle (chưa bắt đầu),
- In-progress (đang thực thi),
- Completed (đã hoàn thành).

Master đồng thời chịu trách nhiệm trung chuyển dữ liệu đầu ra của Map thành dữ liệu đầu vào của Reduce (k2, v2). Để thực thi việc này, mỗi khi một Task của Map hoàn thành (Completed), Master ghi lại vị trí và chiều dài của R file đã thực hiện. Sau đó Master sẽ báo cho các Worker của Reduce biết để Worker đó đọc thông tin (bằng RPC - Remote Procedure Call – xem ở trên).

-

➡ Làm thế nào để Master biết một Worker nào đó “chết”?

Đơn giản là sử dụng lệnh Ping. Nếu sau một khoảng thời gian mà không thấy Worker phản hồi thì coi như Worker đó “chết”. Lúc đó, các Task tương ứng với Worker này sẽ được ghi là Idle (chưa bắt đầu) và Master sẽ chuyển Task này cho một Worker khác thực hiện lại từ đầu.

-

➡ Nếu Master “chết” thì sao?

Cách của Google rất đơn giản: báo là quy trình MapReduce đã bị “hỏng” (failed). Người dùng có quyết định gọi lại MapReduce hay không là quyền của người dùng. Tất nhiên, người ta cấu hình cụm máy tính sao cho xác suất Master hỏng là cực thấp.

Các tác giả trong bài báo có đề cập là họ có thể thay thế bằng phương pháp checkpoint, nhưng vào thời điểm đó, họ chọn giải pháp đơn giản và hiệu quả như trên.

<Mở ngoặc>

❓   Thế phương pháp checkpoint là gì?

Trước mỗi lần Master thay đổi bảng trạng thái, Master ghi giá trị trước đó của bảng trạng thái ra một bản ghi dự phòng. Trong trường hợp Master “chết” thì người ta có thể khởi động lại từ bảng trạng thái ngay trước đó bằng một Master dự phòng thứ cấp (Backup).
Master thứ cấp chạy song song với Master sơ cấp và định kỳ “ping” Master sơ cấp để kiểm tra xem Master sơ cấp có bị “chết” hay không. Khi phát hiện thấy Master sơ cấp “chết”, Master thứ cấp sẽ điều khiển thay thế và điểm khởi đầu cho Master thứ cấp chính là bảng trạng thái gần nhất mà Master sơ cấp đã ghi ra bản ghi dự phòng ở trên.

</Đóng ngoặc>

-

➡ Làm thế nào để đảm bảo tính toàn vẹn khi có Worker bị “chết”?

Chúng ta phân biệt trường hợp Worker thực hiện một Task của Map và Task của Reduce.

·       Trường hợp Map: Worker ghi ra R file trên đĩa cứng cục bộ (local disk) ngay trên máy của Worker. Lưu ý rằng file trên đĩa cứng cục bộ khác file hệ thống GFS. Hệ thống GFS cấp phép truy cập tổng thể. Bất cứ một máy nào trong cụm đều có thể truy cập GFS. Ngược lại, trong hệ thống cục bộ (local) máy này không thể truy cập đĩa cứng cục bộ của máy khác. Nếu Worker của Map bị “chết” giữa chừng thì một số hoặc toàn bộ R file trên máy này không ai truy cập được. Vì vậy, Worker của Map phải “sống” cho đến hết chu kỳ của MapReduce. Nếu không (“chết” giữa chừng), hệ thống bắt buộc phải chuyển Task này cho một Worker khác làm lại từ đầu. Như vậy, đầu ra của Map là dạng giao dịch nguyên tử (atomic commit): hoặc là thành công, dữ liệu có tính toàn vẹn hoặc phải ghi là “hỏng”.

·       Trường hợp Reduce: Worker có đầu ra chỉ là một file. Khi Task của Reduce hoàn thành thì Worker đặt lại tên file: từ tên cục bộ thành tên tổng thể (GFS). Khi nhiều máy cùng thực hiện một Task thì riêng việc đặt lại tên file này cũng cần đảm bảo tính nguyên tử (atomic commit).

-

➡ Làm thế nào để tối ưu hóa thời gian xử lý MapReduce?

Có 3 yếu tố liên quan đến tốc độ xử lý của MapReduce: thời gian truy cập đĩa cứng, tốc độ mạng, cách phân mảnh M, R và số các máy tính có trong cụm máy.

·       Tối ưu hóa Worker và tối ưu hóa truy cập đĩa cứng. Nếu hệ thống có cách phân chia các Worker sao cho Worker đó khi truy cập đĩa cứng thì chủ yếu là truy cập đĩa cứng trên máy cục bộ chứ không truy cập đĩa cứng trên máy khác. MapReduce tìm cách chia Task của Map cho các Worker sao cho “mảnh” đầu vào của Map tương ứng với khối 64MB trên đĩa cứng cục bộ (local disk) của chính máy đó.

·       Tối ưu hóa việc phân mảnh M, R và số Worker. Quan hệ giữa M, R và số các Worker nên như thế nào cho tối ưu? Chúng ta biết rằng các tiến trình (process) có nhiều truy cập I/O thì mỗi một Worker cần xử lý đa nhiệm với số Task khá lớn mới đạt tối ưu. Lý do: khi truy cập I/O thì phép ngắt (Interrupt) trả điều khiển lại ngay cho tiến trình; tiến trình lúc đó có thời gian để xử lý một Task khác. Nếu số Task quá nhỏ thì khoảng thời gian “rỗi” dạng này nhiều, vì vậy, không tối ưu.

Mặt khác, việc chọn hàm để ra được con số R liên quan trực tiếp đến cân bằng tải (load-balancing) của Reduce. Nếu chọn không tối ưu thì dẫn đến tình trạng một số Task của Reduce làm việc rất nặng trong lúc số khác lại “nhàn rỗi” không có nhiều việc để làm. Hàm mặc định của họ là hàm băm modulo R: hash(k2) Mod R.

⚠ Con số tối ưu là con số nào? Con số bài báo đưa ra là: M=200,000; R=5,000; số Worker=2,000. Nghĩa là, trung bình một Worker có thể đảm nhận 100 Task của Map và 2.5 Task của Reduce.

-

➡ Thêm các Task dự phòng thứ cấp (Backup Tasks).

Theo bài báo, hệ thống MapReduce hay gặp phải hiện tượng Worker bị “lạc” (Straggler). Nghĩa là có Worker mất rất nhiều thời gian một cách bất thường để thực thi một Task nào đó vào cuối chu trình. Có một số lý do cho hiện tượng này:

·       Đĩa cứng sắp bị hỏng. Worker vẫn đọc/ghi được nhưng thay vì tốc độ 30 MB/s bây giờ chỉ truy cập được với tốc độ 1 MB/s.

·       Xảy ra tranh chấp giữa các Task được chỉ định trên cùng một máy: tranh chấp truy cập đĩa cứng, tranh chấp truyền tin qua mạng, …

Để giải quyết vấn đề này, vào khoảng thời gian cuối chu trình MapReduce, họ thêm cho mỗi Task đang thực thi (In-progress) một Task dự phòng thứ cấp (Backup). Nghĩa là vào thời điểm đó, có 2 Worker cùng thực hiện một Task. Khi một trong 2 Worker (sơ cấp hoặc thứ cấp) thông báo Task này đã thực thi xong (Completed) thì coi như Task này đã hoàn tất.

Các tác giả cho biết, bằng kỹ thuật này, họ đã làm cho hệ thống MapReduce giảm thời gian thực thi một cách đáng kể. (Trong một thử nghiệm, khi họ tắt chức năng Backup, tổng thời gian xử lý của MapReduce đã tăng lên tới 44%.)

⦀

ⓓ Dataflow (dòng chảy dữ liệu).

Để giúp anh/chị bớt nhức đầu với các chi tiết cài đặt hệ thống như được diễn giải ở phần trước, một cách tổng quan, tôi sắp xếp lại dòng chảy dữ liệu của mô hình MapReduce như trong liệt kê sau đây.

·       Input reader (bộ đọc đầu vào): Thời điểm này hệ thống MapReduce chia đầu vào thành từng mảnh (‘split’), có độ dài thông thường là 64MB, chỉ định mảnh cho các hàm Map tương ứng. Bộ đọc tạo các cặp (k1, v1).

·       Map function (hàm Map): Hàm này do người dùng định nghĩa dưới dạng:
Map (k1, v1) ⟶ list (k2, v2)

·       Partition function (hàm chia vùng): Căn cứ vào số vùng R (mặc định từ hệ thống hoặc do người dùng chỉ định), MapReduce dùng một hàm để chia vùng căn cứ theo giá trị của khóa k2. (Thuật toán “xác định vùng” hay được dùng là hàm băm modulo R: hash(k2) Mod R. Trong kiến trúc của MapReduce, người dùng có thể định nghĩa “hàm chia vùng”.) Hệ thống MapReduce tổ hợp (sắp xếp theo khóa k2) đầu ra của Map và chia thành R vùng làm đầu vào cho Reduce. Vì vậy, hàm chia vùng cần đảm bảo tính cân bằng tải của hệ thống. Nghĩa là R vùng cần được chia tương đối đều, tránh hiện tượng vùng có rất nhiều dữ liệu, vùng khác lại rất ít.

·       Compare function (hàm so sánh): Đây là hàm dùng cho việc sắp xếp dữ liệu khi trộn M mảnh của Map thành R vùng của Reduce.

·       Reduce function (hàm Reduce): Hàm này do người dùng định nghĩa dưới dạng:
Reduce (k2, list(v2))   ⟶ list (v2)

·       Output writer (ghi đầu ra): Đây là thời điểm hệ thống MapReduce ghi đầu ra lên GFS.

-

Một cách cô đọng hơn nữa, chúng ta hình dung dòng chảy của MapReduce là:

Map ⟶ Trộn dữ liệu (sắp xếp) ⟶ Reduce.

Tất cả các công việc trên được xử lý song song, với tính toàn vẹn của dữ liệu, hệ thống xử lý có dự phòng, không ngắt.

⦀

ⓔ Performance (Hiệu suất).

➡ Hiệu suất rõ nhất của mô hình MapReduce là lập trình. Rất dễ dàng. Người lập trình chỉ việc định nghĩa hàm Map và hàm Reduce.

➡ Việc mở rộng hệ thống thì thế nào? Cũng rất dễ! Cứ mua bổ sung thêm máy, kết nối vào cụm (cluster), khai báo các tham số của thư viện MapReduce. Thế là xong.

-

❓   Làm thế nào để đo được mức độ hiệu suất của hệ thống? Liệu các máy có chạy song song không? Có máy nào hoạt động quá tải trong lúc các máy khác lại “nhàn rỗi” không? Có cách nào “ép” hệ thống hoạt động ở mức tối đa để phát hiện ra các “bug” mà bình thường hệ thống không thể hiện? Đo hiệu suất hệ thống là vấn đề rất thú vị, đúng không anh/chị!?

-

➡ Để hỗ trợ người dùng đọc được thông tin trạng thái (status information), Master chạy một http server (một trang web) kết xuất các loại thông tin như: số Task đã hoàn tất (Completed), số Task đang thực thi (In-progress), lượng đầu vào (Input), lượng trung chuyển (từ Map sang Reduce), lượng đầu ra (Output), Worker nào bị “chết”, Task nào do Worker bị “chết” thực hiện, …

Bằng cách quan sát bảng trạng thái này, người dùng có thể dự đoán lúc nào thì chương trình kết thúc, liệu có cần tăng/giảm nguồn lực để chạy chương trình một cách tối ưu, …

<Mở ngoặc>

Đối với anh/chị đã từng trải nghiệm lập trình hệ thống (đặc biệt trên hệ vi xử lý 8 bit), khi anh/chị thử nghiệm “chạy mù” chương trình, lúc đó mới thấm thía giá trị bảng quan sát trạng thái như thế nào!

</Đóng ngoặc>

-

➡ Các tác giả bài báo cho biết, họ đã làm một thử nghiệm MapReduce với dung lượng 10¹⁰ bản ghi 100 byte (~ 1 terabyte) để tìm kiếm chuỗi ký tự (dùng lệnh grep) và sắp xếp (sort) toàn bộ các bản ghi (trong bản ghi 100 byte: 10 byte đầu tiên được sử dụng làm khóa). Người ta sử dụng cụm 1,800 máy PC, mỗi máy chạy Inel Xeon 2GHz, RAM: 4GB, đĩa cứng: 160GB IDE, đường truyền mạng: Ethernet 1 gigabit/s.

·       Chương trình Grep: Người ta cấu hình M=15,000 và R=1. Khi tìm kiếm chuỗi ký tự, chủ yếu là Map thực thi còn Reduce chỉ việc chép lại kết quả. Toàn bộ chương trình chạy mất 150 giây, trong đó Map mất khoảng 80 giây (anh/chị nào quan tâm thì xem đồ thị trong bài báo). Thời điểm mà hệ thống huy động nguồn lực cao nhất là 1,764 Worker ở trạng thái thực thi (trên tổng số 1,800 Worker). Quan sát trạng thái hệ thống, người ta thấy MapReduce mất khoảng 1 phút (60 giây) để khởi động: đây là quãng thời gian Master “giao việc” cho các Worker, mở file (file của Map) và “tối ưu hóa” giữa Worker và đĩa cứng cục bộ (Worker trên máy nào thì truy cập đĩa cứng trên máy đó).

·       Chương trình Sort: cấu hình M=15,000; R=4,000. Người ta quan sát thấy Map mất khoảng 200 giây để đọc dữ liệu. Sau thời điểm Map khởi động khoảng 20 giây thì phần “trộn” (gửi dữ liệu từ Map sang Reduce) bắt đầu. Có sự giao thoa giữa Map và công đoạn “trộn”: một số Task của Map đọc dữ liệu trong khi một số khác đã chuyển sang gửi dữ liệu. Tổng thời gian “trộn” là khoảng 600 giây. Tương tự, cũng có giao thoa giữa công đoạn “trộn” và Reduce. Reduce của Sort ghi kết quả lên 2 bản sao giống hệt nhau. Đây cũng là lý do vì sao thời gian Reduce của Sort dài hơn thời gian Reduce của Grep. Tổng thời gian cho chương trình Sort là 891 giây. So sánh, điểm chuẩn TeraSort (TeraSort Benchmark) để sắp xếp 1 terabyte vào thời điểm đó là 1,057 giây. (Anh/chị có thể tham khảo thêm sortbenchmark.org.)

⦀

ⓕ Experience (trải nghiệm MapReduce tại Google).

“Trải nghiệm” là cụm từ dùng trong bài báo. Trên thực tế, đây là các ứng dụng của mô hình MapReduce vào các công việc trong nội bộ Google:

·       Ứng dụng trong Machine Learning (Google khởi động Machine Learning từ năm 2001)

·       Ứng dụng trong Google News và Froogle. (Google News: tổng hợp tin tức từ các báo. Froogle: tìm kiếm các sản phẩm được bán trực tuyến và so sánh giá các mặt hàng.)

·       Trích xuất dữ liệu của các truy vấn trực tuyến (online queries)

·       Trích xuất thuộc tính của các trang Web

·       …

·       Lập chỉ số toàn bộ nội dung World Wide Web

-

Xin có thêm một vài bình luận về lập chỉ số toàn bộ nội dung World Wide Web. Google là công ty cung cấp dịch vụ tìm kiếm World Wide Web nên việc tìm kiếm phải đảm bảo đủ nhanh để thu hút người dùng. Để tăng tốc độ tìm kiếm, một trong các thủ thuật cơ bản là phải định kỳ lập chỉ số (indexing) của kho dữ liệu khổng lồ này. Chương trình Sort (sắp xếp) được sử dụng cho công việc này.

Bao lâu thì họ lập chỉ số một lần? Một cách chính thức thì Google không cung cấp thông tin này. Trong bài báo, các tác giả nói là họ chạy chỉ số vào cuối tuần – như vậy có thể suy ra tần suất lập chỉ số vào thời điểm đó là khoảng 1 tuần / lần. Càng về sau thì tần suất lập chỉ số càng dày đặc, từ vài ngày đến vài giờ một lần. Khi Google chuyển từ cấu trúc file GFS sang Colossus thì việc lập chỉ số định kỳ không còn cần thiết nữa vì trong cấu trúc Colossus, khi họ cập nhật thông tin từ các trang Web, cấu trúc này tự động lập chỉ số (tham khảo).

-

ⓖ Hadoop, Spark

Được truyền cảm hứng từ MapReduce, tháng 1/2006, Doug Cutting và Mike Cafarella khởi động dự án mã nguồn mở Hadoop. Trang chủ của dự án ở đây. Tôi tin là trên diễn đàn này, rất nhiều anh/chị “thạo” Hadoop, thậm chí là đã triển khai Hadoop tại cơ quan/doanh nghiệp của mình.

Một cách cô đọng, chúng ta có thể so sánh Hadoop với MapReduce như sau:

·       Ngôn ngữ lập trình: Hadoop sử dụng Java, còn MapReduce sử dụng C++

·       Hệ thống file: Hadoop sử dụng HDFS (Hadoop Distributed File System), còn MapReduce sử dụng GFS (Google File System)

·       Mô hình lập trình: sử dụng cùng tên là MapReduce! 😊

Xem kỹ, thì HDFS cũng rất giống GFS!

Có lẽ sự khác biệt lớn nhất giữa MapReduce và Hadoop là: Hadoop là open source nên nếu thiên hạ muốn sử dụng thì chỉ cần đọc tài liệu rồi tải phiên bản mới nhất về mà dùng. Có rất nhiều tên tuổi lớn sử dụng Hadoop, xin liệt kê một số: Yahoo, Facebook, Adobe, Alibaba, AOL, eBay, LinkedIn, Powerset/Microsoft, Spotify, Twitter.

-

Năm 2014, dự án Spark ra đời. Spark rất giống Hadoop, nhưng có một cải tiến rất đáng kể: đó là thay vì truy cập đĩa (như Hadoop và MapReduce), Spark truy cập RAM, nếu có thể. Ý tưởng là sử dụng kỹ thuật bộ nhớ chia sẻ: nhiều tiến trình (process) cùng truy cập một khối bộ nhớ RAM, giống như các tiến trình đó cùng truy cập đĩa cứng vậy. Ngoài ra, Spark còn thêm một số tính năng khác. Với quy mô dữ liệu nhỏ, Spark chạy nhanh hơn Hadoop khoảng 100 lần, còn với quy mô dữ liệu lớn, Spark chạy nhanh hơn Hadoop khoảng 3 lần.

⦀

➕ Đọc thêm.

Khi Google (và các Tech Giants khác) có hàng trăm Datacenters khổng lồ nằm rải rác nhiều nơi trên thế giới, hẳn anh/chị đoán là Google phải sử dụng một hệ thống file tân tiến hơn GFS? Đúng thế, thưa anh/chị, hệ thống file đó có tên là Colossus. Tuy nhiên, có rất ít tài liệu nói về Colossus. Chỉ mới gần đây, vào ngày 19/04/2021 có một bài báo giới thiệu một cách sơ lược về Colossus. Thế mới hay, để cạnh tranh, không phải lúc nào cũng mở hết “ruột gan” ra được. 😊

Và để điều hành các chương trình chạy trên hàng triệu máy tại các Datacenters thì phải có một cách điều hành khác chứ? Đúng thế, hệ điều hành đó có tên là Borg. Tôi tìm thấy 2 bài post nói về Borg. Bài thứ nhất, đăng vào tháng 4/2015: Large-scale cluster management at Google with Borg. Bài thứ hai, mới đăng gần đây, vào tháng 7/2020: Borg: the Next Generation. Nếu anh/chị là dân lập trình hệ điều hành thì tôi đoán là anh/chị đã đọc các bài này rồi. Còn nếu anh/chị chưa đọc thì tôi nghĩ anh/chị cũng nên lướt qua để cảm nhận các ý tưởng về cách vận hành các cụm máy tính khổng lồ vào thời điểm hiện nay. Đương nhiên là phải thêm một vài tách cà phê nữa … 😊

 

(\_/)
( •_•)
/ >☕

 

☕ Nhàn đàm ICT: Image Classification ▥

Phác họa bài post:

ⓐ Image (Ảnh)?

ⓑ Approach (Phương pháp tiếp cận)?

ⓒ Model (mô hình)?

ⓓ Data (dữ liệu).

ⓔ ImageNet Challenge (Thử thách ImageNet).

ⓕ CNN Architectures (Các biến thể kiến trúc CNN).

ⓖ Vision Transformer (ViT).

ⓗ Transfer Learning (Chuyển giao kiến thức mô hình).

-

Để giúp anh/chị quyết định có đọc tiếp hay không, tôi xin phép cung cấp các thông tin liên quan đến bài post này như sau:

·       Chủ đề: Machine Learning

·       Tính thời sự: Từ năm 1998 đến tháng 5 năm 2021.

·       Thời gian đọc: 12 phút, không tính thời gian uống cà phê.

-

Trước hết, tôi xin luận bàn một chút về từ Image Classification. Có thể tạm dịch sang tiếng Việt từ này có nghĩa là “phân loại ảnh”. Đối với các anh/chị “rất thạo” lĩnh vực Computer Vision (thị giác máy tính) thì chủ đề tôi đề cập ở đây có cảm giác là rất nhỏ. Tuy nhiên, với một vài dòng nhàn đàm thì riêng chủ đề này đã là quá rộng. Vả lại, khi đọc lại “sử” của nhận dạng thì hóa ra Image Classification là điểm khởi đầu, là công nghệ cốt lõi của nhận dạng. Nhiều vấn đề tưởng không liên quan như object detection (phát hiện đối tượng) hay segmentation (phân đoạn) lại có thể được giải quyết bằng kỹ thuật “phân loại ảnh”. Đấy, tôi phải giới thiệu thế để anh/chị không bỏ qua bài post này! 😊

-

▥

ⓐ Image (Ảnh)?

Vì chủ đề của chúng ta là phân loại ảnh nên trước hết chúng ta cần định nghĩa chính xác ảnh là gì.

·       Quan sát bằng mắt thường, ảnh chụp sau khi được số hóa là bảng các điểm gồm h hàng và w cột. Nếu là ảnh đen – trắng thì mỗi một điểm (pixel) là một số 8 bit thể hiện mã màu (mức xám) của điểm đó: nếu mã màu = 0 thì màu của điểm là màu đen, còn nếu mã màu = 255 thì màu của điểm là màu trắng. Nếu mã màu nằm ở giữa 0 và 255 thì mức xám phụ thuộc vào giá trị của nó: gần với 0 thì màu sẽ tối, còn gần với 255 thì màu sáng hơn. Nếu là ảnh màu thì mỗi một mã màu là tổ hợp của 3 con số của 3 kênh màu: Red (đỏ), Green (xanh lá cây) và Blue (xanh dương). Các màu này được ký hiệu một cách vắn tắt là RGB.

·       Khi lưu trong máy tính, ảnh là một ma trận 2 chiều có (w*h) điểm. Nếu là ảnh đen trắng thì mỗi một mã màu tương ứng với 1 byte. Nếu là ảnh màu thì mỗi một mã màu tương ứng với 3 byte. Như vậy, máy tính nhìn thấy ảnh là một mảng 3 chiều w*h*c – trong đó c hoặc bằng 1 hoặc bằng 3. Nếu chúng ta chụp ảnh màu cái cốc cà phê anh/chị đang nhâm nhi và giả thiết ảnh có chiều rộng 400 pixel, chiều cao 300 pixel thì phần mềm máy tính “nhìn thấy” ảnh là một mảng gồm 400*300*3 = 360,000 con số.
Đấy, trong bộ nhớ máy tính, ảnh là một dãy các con số như thế!

-

Lại nói về việc chụp ảnh. Ảnh có thể biến dạng theo nhiều cách khác nhau. Ví dụ:

·       Viewpoint variation (thay đổi góc chụp): Cùng một vật, máy ảnh có thể chụp theo nhiều góc khác nhau.

·       Scale variation (biến đổi kích cỡ): Có 2 loại biến đổi kích cỡ: kích cỡ thay đổi do máy ảnh chụp gần, chụp xa hoặc chính bản thân vật được quan sát cũng có nhiều kích cỡ khác nhau. Ví dụ, cốc cà phê có loại bé, có loại to.

·       Deformation (biến dạng): Vật được quan sát có thể biến dạng (ví dụ: cái khẩu trang).

·       Occlusion (khuất): Vật được quan sát có thể bị khuất (lấp) một phần. Ví dụ, khi chụp ảnh cái cốc, chúng ta có thể chỉ chụp phần miệng cốc.

·       Illumination conditions (điều kiện chiếu sáng): Ảnh lúc tỏ lúc mờ tùy vào điều kiện chiếu sáng.

·       Background clutter (nền lộn xộn): Nếu bàn làm việc của anh/chị có nền hoa văn thì ảnh chụp vật cần quan sát có thể bị nền làm lóa, làm cho vật bị biến dạng theo nền.

·       Intra-class variation (đa mẫu cùng chủng loại): Ví dụ, cùng cốc cà phê nhưng cái thì to màu nâu, cái thì bé màu đỏ, cái thì cao màu trắng sứ, …

-

▥

ⓑ Approach (Phương pháp tiếp cận)?

Liệu có tồn tại một chương trình phần mềm dùng để nhận dạng ảnh hoặc phân lớp ảnh? Cũng có thể. Tuy nhiên, có một thực tế: giới nghiên cứu vẫn chưa tìm ra chương trình dạng như thế. Từ lâu, người ta tìm cách giải quyết vấn đề bằng một cách khác: mô phỏng quy trình nhận dạng của con người. Từ bé, rõ ràng là chúng ta chưa biết đến khái niệm “cốc cà phê”. Sau nhiều lần được người lớn chỉ cho chúng ta rằng “vật như thế” là “cốc cà phê”. Có thể chúng ta lật qua lật lại, ngắm nghía nhiều góc và ghi vào bộ nhớ của chúng ta. Lần sau, nếu có một cái vật từa tựa như chúng ta đã từng biết – lúc đó chúng ta nhận ra: à, đó là “cốc cà phê”. Cách tiếp cận này có tên gọi là data-driven approach – tạm dịch là phương pháp tiếp cận dựa vào dữ liệu. Nghĩa là, thay vì đi tìm một thuật toán, người ta đi tìm một mô hình (model). Mô hình này sẽ bắt chước cách nhận dạng của con người: học nhận dạng qua một loạt ảnh bằng cách bảo với máy rằng: ảnh này là “cốc cà phê”, ảnh kia là “chiếc điện thoại”, ảnh kìa là “cái khẩu trang”, … Sau khi học xong, nếu cho máy “nhìn” ảnh cốc cà phê của anh/chị đang nhâm nhi, máy sẽ biết đó là cốc cà phê. Đại ý thế.

Mặc dù không muốn làm anh/chị “nhức đầu”, tôi cũng đành phải viết ra đây hơi kỹ thuật một chút. Mô hình mà chúng ta cần tìm có tên gọi là Classifier (bộ phân loại):

·       Input (đầu vào): có N ảnh được dán nhãn, mỗi một nhãn chỉ thuộc vào 1 trong K loại khác nhau. Chúng ta gọi bộ dữ liệu này là bộ dữ liệu huấn luyện. Chúng được dùng để huấn luyện mô hình. Nhắc lại: ảnh = mảng các điểm (đề cập ở trên).
-

·       Learning (học): Nhiệm vụ chính của công đoạn này là huấn luyện cho máy biết cách phân loại ảnh. Bước này có tên gọi là training a classifier (huấn luyện bộ phân loại). Qua huấn luyện, mô hình sẽ học (learning).
-
❓ Về mặt bản chất, học (learning) ở đây là gì vậy? Trả lời: là điều chỉnh các tham số (parameters/hyper-parameters) của mô hình sao cho mô hình thích nghi tối ưu nhất đối với dữ liệu đã huấn luyện. Cụ thể, trong trường hợp mô hình là mạng nơ-ron thì learning chính là thay đổi các trọng số (weights) của mạng.
-

·       Evaluation (đánh giá): Nhiệm vụ của công đoạn này là đánh giá chất lượng mô hình. Cách đánh giá: cho một ảnh mới (không thuộc bộ ảnh huấn luyện ở trên) và xem mô hình có cho kết quả đúng với đáp án hay không. Tỷ lệ cho đáp án đúng chính là chất lượng của mô hình.
-

Có thể diễn giải cách tiếp cận này như sau:

1.     Mỗi một bước huấn luyện có đầu vào của mô hình là cặp thông tin (ảnh: nhãn). Ví dụ: (ảnh 1: “cốc cà phê”), (ảnh 2: “chiếc điện thoại”), (ảnh 3: “cái khẩu trang”), (ảnh 4: “chiếc điện thoại”), (ảnh 5: “cái khẩu trang”), …

2.     Sau khi “nhập” dữ liệu đầu vào, mô hình “học” nhận dạng ảnh. Tức là mô hình tự điều chỉnh các tham số sao cho nó có thể nhớ được “ảnh như thế” là “nhãn như kia”.

3.     Quy trình trên (huấn luyện) được lặp đi lặp lại nhiều lần. Khi huấn luyện, người ta sử dụng nhiều kỹ thuật huấn luyện (ở đây tôi không đi sâu vì như vậy sẽ làm cho anh/chị “nhức đầu” thêm 😊). Sau mỗi đợt huấn luyện, người ta phải kiểm tra xem mô hình đã “nhớ” tốt chưa, có còn nhiều “nhầm lẫn” không. Nếu sau nhiều đợt huấn luyện mà mô hình không “tiến bộ” thêm thì họ cho dừng huấn luyện.

4.     Sau khi dừng huấn luyện, đó là thời điểm để đánh giá chất lượng của mô hình: kiểm tra thực địa (ground truth). Lúc này, người ta cho đầu vào hàng loạt ảnh mới - ảnh mà mô hình chưa nhìn thấy bao giờ - và kiểm tra xem mô hình có phân loại được không, bao nhiêu ảnh phân loại đúng, bao nhiêu ảnh phân loại sai. Tỷ lệ phân loại đúng cao – có nghĩa là mô hình có chất lượng tốt. Ngược lại, tỷ lệ sai còn nhiều thì mô hình chưa tốt.
-
⚠ Khi anh/chị đọc các bài báo, trong phần thực nghiệm người ta thường nêu tỷ lệ % lỗi (Error Rate): tỷ lệ % lỗi càng thấp thì mô hình có chất lượng càng cao.

-

▥

ⓒ Model (mô hình)?

Kiến trúc mô hình mạng nơ-ron nào là phù hợp cho phân loại ảnh? Câu trả lời, ở vào thời điểm hiện nay, thì gần như “ai cũng biết”: CNN.

-

Người đi tiên phong trong vấn đề phân loại ảnh là ông Yann LeCun với mô hình LeNet-5 (1998). Trong bài báo, tác giả đặt tên mô hình là “Convolutional Neural Networks” (viết tắt là CNN hoặc ConvNet). Có thể dịch CNN là mạng nơ-ron tích chập, do toán tử Convolution được dịch là “tích chập”. Tuy nhiên, theo tôi chúng ta cứ dùng luôn từ viết tắt CNN vì khi dùng từ đó, “cả tây lẫn ta” đều hiểu và không bị nhầm sang nghĩa khác.

-

Tài liệu hướng dẫn về CNN có rất nhiều trên mạng Internet, anh/chị nào quan tâm chi tiết chỉ cần “Google” cái là ra một danh sách dài các đường link.

Đối với dân “kỹ thuật” như chúng ta (ICT_VNers), có lẽ nhiều người sẽ đặt câu hỏi: cái “magic” của kiến trúc CNN nằm ở chỗ nào? Khi tham khảo trên mạng, anh/chị có thể thấy nhiều bài viết với nhiều góc nhìn khác nhau. Cá nhân tôi, tôi thấy có vài điểm làm nên “magic” của CNN như sau:

-
✪ Toán tử Convolution. Nếu anh/chị đã từng có dịp “nghiền ngẫm” làm thế nào để “chiết” ra được đặc tính của một vùng ảnh thì hẳn về mặt toán học anh/chị sẽ nghĩ đến một phép toán. Vấn đề là phép toán nào? Ông Iann LeCun đưa vào toán tử Convolution. Tò mò thêm một chút, chúng ta thấy định nghĩa của toán tử Convolution là:

(f*g)(t) = ∫ f(t - τ) * g(τ) d(τ)

Vì chúng ta đang làm việc với “số hóa” nên trong trường hợp số rời rạc (discrete), công thức trên biến thành:

(f*g)[n] = ∑ f[n - m]g[m]

Nếu áp dụng công thức trên trong không gian 2 chiều thì đó đơn thuần chỉ là phép nhân ma trận (Matrix Multiplication - Dot Product)!

-

Tiếp theo, toán tử Convolution được thực hiện như thế nào? Trong bài báo gốc (LeNet-5), tác giả Iann LeCun đề cập đến khái niệm receptive field – tạm dịch là vùng cảm nhận. Ngoài ra, bài báo còn đưa vào khái niệm shared weights (chia sẻ trọng số). Chia sẻ trọng số là gì? Là nhiều nút trong mạng nơ ron có cùng giá trị trọng số. Nếu anh/chị đọc các bài báo vào thời điểm hiện nay thì người ta thay tổ hợp hai khái niệm receptive field với shared weights bằng bằng từ mới là filter – bộ lọc. Tôi thấy họ dùng từ filter hợp lý vì khái niệm bộ lọc rất trực quan. Khi chúng ta nhìn vào ảnh, thường chúng ta chú ý vào một vùng nhỏ nào đó. Lúc chúng ta lướt qua ảnh, là lúc chúng ta “quét ảnh” bằng vùng cảm nhận. Khi lướt ảnh, chúng ta nhận diện ảnh bằng cách phát hiện các đặc tính (feature). Các đặc tính của ảnh là gì? Chúng có thể là các cạnh, các điểm, các góc, hoa văn, …

Trong CNN, bộ lọc (filter) là hình vuông F*F pixel. Giả thiết F=5 thì bộ lọc có 5*5 = 25 điểm. Một cách trực quan, chúng ta có thể xem toán tử Convolution là “xoắn” 25 điểm liền nhau trên ảnh thành một điểm. Chú ý rằng phép “xoắn” này sau đó quét (scan) toàn bộ ảnh, là quét một cách “xoắn lợp ngói” lên nhau, từ trái sang phải, từ trên xuống dưới. Kết quả chúng ta được gì? Mỗi một filter, theo tác giả Iann LeCun, phát hiện ra một “đặc tính”. Chú ý thêm rằng, việc phát hiện ra một “đặc tính” chỉ phụ thuộc vào kích cỡ của F (bộ lọc), hoàn toàn độc lập với kích cỡ của ảnh!

⚠ Chú ý: Các bài báo hiện nay người ta dùng từ kernel (nhân) thay cho từ feature (đặc tính).

Ảnh, hẳn nhiên chứa nhiều đặc tính. Và điều đó đồng nghĩa với việc người ta cần nhiều kernel. Nhưng cần bao nhiêu kernel cho một ảnh? Đây là vấn đề gắn liền với “nghệ thuật” kiến trúc mô hình. Ảnh trong bài báo LeNet-5 có kích thước là 32x32 pixel, tác giả thiết kế 6 kernel cho lớp Convolution thứ nhất, 16 kernel cho lớp Convolution thứ 2, 120 kernel cho lớp Convolution thứ 3.

⚠ Chú ý: Trong bài báo, tác giả Iann LeCun không dùng từ kernel mà dùng từ feature map.

-

✪ Lớp Pooling (trong bài LeNet-5, ông Iann LeCun gọi là lớp sub-sampling). Đây là phép toán “gộp” 4 điểm của lớp trước thành 1 điểm của lớp sau. Nghĩa là giảm độ phân giải từ 100% thành 25%. Một cách trực quan: đây là việc thu nhỏ ảnh! Dưới góc độ tính toán thì đây là giảm độ phức tạp xuống chỉ còn ¼.

Theo các phân tích sau này, người ta gọi cách làm trên là biến lớp ảnh từ độ phân giải cao (high resolution) thành lớp ảnh có độ phân giải thấp (low resolution). Ưu điểm của cách làm này là giảm dần độ phức tạp nhưng nhược điểm là các lớp về sau “mất thông tin”. Lý do mất thông tin là do chập 4 điểm thành 1 điểm.

-

▥

ⓓ Data (dữ liệu).

Dữ liệu bao giờ cũng là nguồn nguyên liệu chính của Machine Learning. Điều này càng đúng với bài toán “phân loại ảnh”: nguyên liệu chính là nguồn ảnh có dán nhãn dùng để huấn luyện mô hình. Nhân chủ đề về dữ liệu dùng để phân loại ảnh, xin có đôi lời bàn sâu hơn về dữ liệu.

-

① Dữ liệu có quan trọng không? Để thuyết phục về mức độ quan trọng của dữ liệu, chúng ta hãy lấy ví dụ. Trong một lần nhàn đàm trước, với chủ đề “Machine Translation”, chúng ta thấy các mô hình như SMT (Statistical Machine Translation) hay NMT (Neural Machine Translation) đều phụ thuộc 100% vào dữ liệu đã được xây dựng từ trước. Không có dữ liệu tốt thì các mô hình SMT, NMT chẳng có ý nghĩa gì cả!

-

② Dữ liệu có ảnh hưởng đến mô hình không? Đây là trường hợp khi chúng ta dù có dữ liệu tốt, nếu dữ liệu không phủ hết các trường hợp thì mô hình cũng sẽ không có chất lượng tốt. Hãy lấy một ví dụ. Giả thiết chúng ta cần nhận diện một vật với tập ảnh cần 50 góc chụp ảnh khác nhau và chúng ta có 500 ảnh. Nếu tập ảnh này chỉ loanh quanh trong 5 góc chụp, chúng ta dễ dàng nhận thấy dù có sử dụng mô hình nào đi nữa thì chắc chắn mô hình đó không nhận dạng đúng ảnh của 45 góc còn lại.

-

③ Giới nghiên cứu sử dụng các tập dữ liệu mẫu nào? Các tập dữ liệu mà tôi đề cập ở đây thuộc nhóm “Open Datasets” – là các tập dữ liệu mở: tự do sử dụng, miễn phí cho mục tiêu nghiên cứu, giảng dạy. Các tập dữ liệu mẫu này thường được sử dụng cho đào tạo Machine Learning, được các bài báo khoa học tham chiếu, so sánh để thuyết phục người đọc, học về các mô hình mà họ đề xuất.

MNIST (Modified National Institute of Standards and Technology database). CSDL ảnh dùng để nhận dạng chữ số viết tay (0, 1, …, 9): gồm 70,000 ảnh đen trắng kích cỡ 28x28 pixel.

CIFAR-10 (Canadian Institute For Advanced Research). CSDL ảnh dùng để huấn luyện các mô hình Machine Learning nói chung và thị giác máy tính nói riêng: gồm 60,000 ảnh màu kích cỡ 32x32 của 10 loại ảnh (airplanes - máy bay, cars - ô tô, birds - chim, cats - mèo, deer - hươu, dogs - chó, frogs - ếch, horses - ngựa, ships - tàu, trucks - xe tải). Mỗi loại có 6,000 ảnh.

CIFAR-100. CSDL này tương tự như CIFAR-10, nhưng có 100 loại ảnh, tổng 60,000 ảnh màu kích cỡ 32x32. Mỗi loại chỉ có 600 ảnh.

ImageNet. Là một CSDL hình ảnh được tổ chức theo hệ thống phân cấp học theo cách của WordNet. Mỗi một nút tương ứng với một khái niệm (concept) và khái niệm này được mô tả bằng hàng trăm đến hàng nghìn hình ảnh. “Khái niệm” có thể là một từ hoặc cụm từ. Như vậy, các ảnh mô tả một khái niệm được “dán nhãn” bằng chính khái niệm đó. Trong WordNet, họ gọi các khái niệm này là “synonym set” (tập từ đồng nghĩa), viết tắt là synset. Một synset đồng nghĩa với một loại ảnh. Tất cả các ảnh đều có cơ chế kiểm soát chất lượng và được dán nhãn một cách thủ công. Vào thời điểm của bài viết này, ImageNet có 14,197,122 ảnh và 21,841 synset. Người ta thường phân biệt 2 tập dữ liệu của ImageNet, đặt tên là ImageNet-1K và ImageNet-21K.

·       ImageNet-1K: CSDL này có đúng 1,000 synset, người ta gán cho mỗi synset khoảng 1,000 ảnh. Mỗi một ảnh trong ImageNet-1K chỉ thuộc vào một synset duy nhất. ImageNet-1K là tập con của CSDL ImageNet. Thông thường khi các báo cáo khoa học nói sử dụng tập dữ liệu mẫu ImageNet, chính là họ nói đến ImageNet-1K.

·       ImageNet-21K: Đây là CSDL đầy đủ của ImageNet. Sở dĩ có đuôi là 21K là do có tổng số synset là 21,841. Do cấu trúc phân cấp của ImageNet, một ảnh có thể tương ứng với nhiều synset. Ví dụ: ảnh của cái ghế tương ứng với từ “ghế” và từ “đồ nội thất”. Tập dữ liệu mẫu ImageNet-21K ít được sử dụng hơn so với ImageNet-1K trong các nghiên cứu phân loại ảnh.

-

▥

ⓔ ImageNet Challenge (Thử thách ImageNet).

Tên đầy đủ của cuộc thi này là “ImageNet Large Scale Visual Recognition Challenge” viết tắt là ILSVRC, tạm dịch: “Thử thách nhận dạng hình ảnh quy mô lớn ImageNet”. Tôi xin có vài dòng đề cập đến cuộc thi này vì nó đóng vai trò rất lớn trong sự phát triển của nhận dạng hình ảnh nói riêng và trong Machine Learning nói chung.

-

Cuộc thi này được tổ chức hàng năm, từ năm 2010 đến năm 2017 (8 năm). Cách thi như sau:

1.     Người ta cho một tập mẫu ảnh có dán nhãn và một tập ảnh chưa dán nhãn.

2.     Tập ảnh đã được dán nhãn là để cho nhóm dự thi dùng để huấn luyện mô hình: có khoảng 1 triệu ảnh phân thành 1 nghìn loại. Như vậy trung bình mỗi loại có 1 nghìn ảnh. Trong số 1 triệu ảnh này, người ta tách ra khoảng 50 nghìn ảnh để validation (thẩm định) và khoảng 150 ảnh dùng để test (kiểm tra). (Validation và test là các công đoạn trong huấn luyện mô hình.)

3.     Mô hình dự thi phải dự đoán tập ảnh chưa dán nhãn. Đối với mỗi một ảnh, mô hình có quyền đưa ra 5 dự đoán, sắp xếp theo mức độ tự tin (confidence) giảm dần. Trên cơ sở này, phần mềm “giám khảo” sẽ so sánh với nhãn đúng của ảnh và có công thức chấm điểm phù hợp.

4.     Nhóm dự thi sau đó trình bày phương pháp luận của mô hình và kết quả thực nghiệm tại hội thảo được tổ chức sau khi có kết quả chung cuộc. Mục tiêu của hội thảo là xúc tiến, quảng bá và chia sẻ thành công của các giải pháp đã đoạt giải.

Các giải pháp đạt giải của cuộc thi này được coi là các “benchmark” (kiểm chuẩn mô hình) trong nghiên cứu phân loại ảnh và thị giác máy tính.

-

Ảnh hưởng của ImageNet Challenge. Một điểm mốc có ảnh hưởng sâu sắc đến Machine Learning gắn liến với ImageNet Challenge là mô hình AlexNet, dự thi năm 2012. Nhóm dự thi gồm GS. Geoffrey Hinton, Ilya Sutskever và Alex Krizhevsky đến từ trường ĐH Toronto (Canada). Mô hình AlexNet nhận dạng ảnh đạt được độ chính xác ~ 75%, bỏ xa nhóm về nhì hơn 10.8 điểm. Nhiều người coi đây là điểm khởi đầu sự bùng nổ của Deep Learning và và qua đó, lôi kéo các tinh hoa của thế giới vào Artificial Intelligence.

Về mặt kỹ thuật, nhóm này đưa vào nhiều điểm mới. Nhóm này là nhóm đầu tiên sử dụng GPU để huấn luyện, sử dụng kỹ thuật Dropout để giảm overfitting.

Về hàm phi tuyến, nhóm này lần đầu tiên sử dụng hàm ReLU (Rectified Linear Unit), một hàm có công thức rất đơn giản và đạt được tính hiệu quả cao khi tính toán.

Các năm tiếp theo, tất cả các đội dự thi đều mang đến cuộc thi các mô hình có độ chính xác tăng lên một cách đều đặn. Ví dụ, năm 2013, gần như tất cả các mô hình đều đạt độ chính xác từ 75% trở lên. Đến năm 2017, 29/38 đội dự thi có mô hình đạt độ chính xác trên 95%. Lưu ý rằng mắt người nhận dạng ảnh với độ chính xác khoảng 95%. Như vậy mô hình của 29 đội dự thi lúc đó đã vượt qua ngưỡng của con người!

-

▥

ⓕ CNN Architectures (Các biến thể kiến trúc CNN).

Sau mô hình LeNet-5, có “hằng hà sa số” các mô hình khác, cùng có kiến trúc CNN nhưng có nhiều cải tiến, thay đổi nhằm đạt được độ chính xác cao hơn đồng thời sử dụng nguồn lực tính toán tối ưu hơn. Mời anh/chị tham khảo một số mô hình tiêu biểu trong bảng sau.

Mô hình	Độ sâu (số lớp)	Dữ liệu mẫu	Error rate (%)	Năm
AlexNet	8	ImageNet	16.4	2012
NIN	3	CIFAR-10, CIFAR-100, MNIST	10.41, 35.68, 0.45	2013
ZfNet	8	ImageNet	11.7	2014
VGG	16, 19	ImageNet	7.3	2014
GoogLeNet	22	ImageNet	6.7	2015
Highway	19, 32	CIFAR-10	7.76	2015
Inception-V4	70	ImageNet	3.08	2016
ResNet	152	ImageNet	3.57	2016
WideResNet	28	CIFAR-10, CIFAR-100	3.89, 18.85	2016
Xception	71	ImageNet	0.055	2017
Residual attention neural network	452	CIFAR-10, CIFAR-100	3.90, 20.4	2017
Squeeze-and-excitation networks	152	ImageNet	2.25	2017
DenseNet	201	CIFAR-10, CIFAR-100, ImageNet	3.46, 17.18, 5.54	2017
Competitive squeeze and excitation network	152	CIFAR-10, CIFAR-100	3.58, 18.47	2018
CapsuleNet	3	MNIST	0.00855	2018

-

Nếu anh/chị có thời gian lướt qua các bài báo, thì có thể nhận ra là giải pháp của các cuộc thi sau học hỏi, cải tiến giải pháp của các cuộc thi trước. Tất nhiên, đây là việc thường thấy trong nghiên cứu khoa học. Một vài ví dụ:

·       ZfNet thắng giải ILSVRC năm 2013, là cải tiến, sửa đổi của mạng AlexNet năm 2012.

·       GoogleNet đoạt giải nhất ILSVRC năm 2014, VGG đoạt giải nhì cùng năm.

·       ResNet thắng giải ILSVRC năm 2015. Về mặt kỹ thuật kiến trúc mô hình, ResNet đưa vào kiến trúc có tên là Skip Connection hoặc Residual Neural Network. Kiến trúc này mang tính đột phá vì nó cho phép thiết kế CNN với số lớp cực lớn (hàng trăm, thậm chí hàng nghìn lớp). Ngoài ra, trong nghiên cứu phân lớp ảnh, ResNet thường được coi là gold-standard (chuẩn mực vàng) của CNN.

-

▥

ⓖ Vision Transformer (ViT).

Kiến trúc CNN có tính bao trùm đến mức, khi người ta nghĩ đến nhận dạng hình ảnh, thì “bắt buộc” phải nghĩ đến một biến thể nào đó của CNN. Mãi cho đến tháng 10/2020, Google mới “trình làng” một cách tiếp cận khác: sử dụng Transformer.

<Mở ngoặc>

Trong lần nhàn đàm trước về chủ đề “Machine Translation”, tôi có đề cập đến Transformer. Transformer lúc đó được sử dụng để dịch một đoạn văn bản trong ngôn ngữ nguồn sang ngôn ngữ đích.

Xin phép nhắc lại, cách tiếp cận của Neural Machine Translation là sử dụng encode-context-decoder:

[Văn bản ngôn ngữ nguồn]→{mã hóa}→[context]→{giải mã}→[văn bản ngôn ngữ đích]

Nếu sử dụng mạng RNN, văn bản được cắt đoạn thành các câu. Mỗi một lần dịch, máy chỉ dịch 1 câu. Nếu ký hiệu câu nguồn gồm các từ [x₁, x₂, …, x_m] và câu đích gồm các từ [y₁, y₂, …, y_n] thì có thể thấy mô hình này vận hành như sau:

[x₁, x₂, …, x_m]→{mã hóa}→[context]→{giải mã}→[y₁, y₂, …, y_n]

Mỗi một nhịp, máy chỉ đọc 1 từ đầu vào. Trong ví dụ trên, máy cần m nhịp. Sau khi mã hóa và giải mã, mỗi một nhịp, máy cũng chỉ dịch được một từ đầu ra. Trong ví dụ trên, máy cần n nhịp.

-

Transformer không sử dụng mô hình mạng RNN mà chỉ sử dụng cơ chế Attention. Vì không sử dụng mạng RNN nên ngoài việc mã hóa các đoạn văn bản [x₁, x₂, …, x_m] và [y₁, y₂, …, y_n], Transformer cũng mã hóa cả vị trí của các phần tử trong các văn bản đó (1, 2, …, n và 1, 2, …, m) để biết được thứ tự của các phần tử.

</Đóng ngoặc>

-

💡 Thế ViT biến một ảnh thành chuỗi các phần tử [x₁, x₂, …, x_m] bằng cách nào? Rất bất ngờ và thú vị: họ chia ảnh thành các ô bàn cờ có kích thước bằng nhau, đánh số thứ tự các ô đó, làm “phẳng hóa” các ô ảnh, xếp chúng thành chuỗi các phần tử và biến chúng thành chuỗi đầu vào [x₁, x₂, …, x_m]. Khác hẳn với cách tiếp cận của CNN, ViT “băm” nhỏ ảnh thành các “mảnh vụn”, rồi xếp chúng thành một dãy theo thứ tự. “Nghiền ngẫm” về cách làm này, có cảm giác là ViT không xử lý ảnh theo đặc trưng riêng của ảnh. ViT xem ảnh cũng giống hệt như chuỗi các phần tử bất kỳ!

Ngoại trừ điểm đặc biệt này, các quy trình khác tuân theo các quy tắc thông thường khi huấn luyện mô hình.

Họ chia mô hình của họ theo 3 kích cỡ:

·       ViT-Base: có 12 lớp, 86 triệu tham số

·       ViT-Large: có 24 lớp, 307 triệu tham số

·       ViT-Huge: có 32 lớp, 632 triệu tham số

⚠ Chú ý rằng, mô hình nào có số tham số càng nhiều thì mô hình đó đạt độ chính xác càng cao. Tuy nhiên, mô hình có nhiều tham số đòi hỏi phải huấn luyện lâu hơn và sử dụng “nguồn lực” nhiều hơn, đắt hơn.

-

Trong các thử nghiệm của nhóm nghiên cứu, có một điểm rất đáng chú ý.

·       Khi huấn luyện với ít dữ liệu (ImageNet-1K: 1.2 triệu ảnh, 1 nghìn loại), các biến thể của CNN cho độ chính xác cao hơn ViT.

·       Khi tăng lượng dữ liệu huấn luyện lên (ImageNet-21K: 14 triệu ảnh, 21 nghìn loại) thì mô hình ViT lại cho độ chính xác tương đương CNN.

·       Khi tăng tiếp số lượng ảnh huấn luyện (JFT: 300 triệu ảnh, 18 nghìn loại), độ chính xác của ViT vượt CNN.

-

Bài báo kết luận: Tuy kiến trúc CNN đã làm nên cuộc cách mạng trong lĩnh vực thị giác máy tính, kết quả nghiên cứu và thử nghiệm của bài báo chỉ ra rằng một “kiến trúc đặc trưng cho nhận dạng ảnh” chưa chắc cần thiết, thậm chí không phải là tối ưu! Chìa khóa vấn đề nằm ở ⚠ số lượng dữ liệu huấn luyện: càng nhiều càng tốt.

Nghĩa là, độ chính xác không nằm ở kiến trúc mô hình mà nó phụ thuộc vào chất lượng dữ liệu và số lượng dữ liệu dùng để huấn luyện.

-

🌞 Vào tháng 5/2021, xuất hiện một bài báo về phân lớp ảnh. Bài này đề xuất mô hình có tên là MLP-Mixer. Mô hình này không sử dụng Convolution và cũng không sử dụng Transformer, chỉ sử dụng cấu trúc nguyên thủy của mạng nơ-ron là MLP (Multilayer perceptron)! MLP mà họ sử dụng là MLP “nguyên tử”, tức là MLP tối giản: lớp đầu vào, lớp ẩn và lớp đầu ra. Kết quả thực nghiệm cho thấy mô hình này cũng chẳng kém gì ViT. Rất ngạc nhiên thú vị!

-

▥

ⓗ Transfer Learning (Chuyển giao kiến thức mô hình).

Như đã được đề cập ở mục trên, các mô hình Deep Learning hiện nay đều cần lượng dữ liệu cực lớn (hàng chục triệu mẫu, hàng chục nghìn nhãn) và thời gian huấn luyện khá dài (vài tuần đến vài ba tháng). Việc này chỉ có một số không nhiều các công ty với nguồn lực đủ mạnh mới có thể thực hiện được. Vấn đề trong thực tế: chúng ta có một ít ảnh được dán nhãn (số nhãn cũng không nhiều), liệu chúng ta có cách nào đó tận dụng mô hình phân loại hình ảnh đã được các “siêu công ty” kia thực hiện?

-

Trả lời: Cách tiếp cận được khuyến cáo hiện nay là Transfer Learning. Tôi tạm dịch là “Chuyển giao kiến thức mô hình”. Chúng ta biết rằng khi huấn luyện mô hình thì thực chất là người ta điều chỉnh các tham số của mô hình sao cho mô hình “đoán” được đầu ra chính xác nhất. Đến một thời điểm người ta thấy mô hình ổn định thì họ dừng lại, không huấn luyện tiếp. Ai muốn thừa kế sử dụng mô hình thì người ta chuyển giao (transfer). Chuyển giao ở đây là người ta cho chúng ta tập hợp các tham số của mô hình sau khi được họ huấn luyện trước. Tập hợp các tham số (kiến trúc mô hình + các trọng số (weights)) chính là kiến thức hiểu biết về mô hình. Từ tập hợp các tham số này, chúng ta sẽ điều chỉnh tiếp các tham số để phù hợp với bài toán cụ thể của chúng ta. “Bài toán cụ thể” này thường là một bài toán nhỏ hơn nhiều so với bài toán lớn – mà bài toán lớn đã được huấn luyện và đang sẵn sàng chuyển giao.

Một vài cụm từ hay được dùng trên các bài báo khoa học vào thời điểm hiện nay:

·       Mô hình lớn, tổng quan, sẵn sàng cho việc chuyển giao có tên là Upstream (thượng nguồn).

·       Mô hình nhỏ, ứng dụng mô hình chuyển giao vào một bài toán cụ thể, có tên là Downstream (hạ lưu).

·       Một cách hình tượng: từ mô hình tổng thể - thượng nguồn – nước chảy xuôi với rất nhiều rẽ nhánh – hạ lưu – chính là các ứng dụng khác nhau của mô hình tổng thể.

Cách làm này có thể được hiểu một cách nôm na như sau:

1.     Người ta chọn một mô hình có tính bao quát nhất về vấn đề cần quan tâm (trong trường hợp của bài post này là “phân loại ảnh”).

2.     Người ta huấn luyện mô hình với tập dữ liệu mẫu cực lớn. Bước này gọi là pre-training. Đến đây, chúng ta được mô hình cơ sở (Upstream). Mô hình cơ sở này cung cấp cho chúng ta lời giải tổng quát.

3.     Việc còn lại của chúng ta là tinh chỉnh (fine-tuning) mô hình cơ sở đó để giải bài toán cụ thể của mình (Downstream).

-

Cụ thể, đối với bài toán phân loại ảnh, xin giới thiệu với anh/chị giải pháp Transfer Learning của Google dưới dạng “Open Source” gồm bài giới thiệu, bài báo, mô hình chuyển giao và mã nguồn cho các framework TensorFlow2, Jax, PyTorch.  Bài báo xuất bản vào tháng 5 năm 2020 với tiêu đề “Big Transfer (BiT): General Visual Representation Learning” (Chuyển giao lớn (BiT): Kiến trúc nhận dạng hình ảnh tổng quát).

-

Mục tiêu của nhóm nghiên cứu là tạo ra một mô hình tổng quan về nhận dạng hình ảnh, huấn luyện mô hình với khối lượng tập mẫu dữ liệu cực lớn và “open source” cho bất cứ ai có nhu cầu sử dụng.

o   Việc đầu tiên là họ chọn mô hình, một biến thể của CNN: ResNet. Vì sao Resnet được chọn mà không phải là mô hình khác? ResNet là mô hình phân loại ảnh với độ chính xác rất cao (error rate là 3.57 tương đương độ chính xác là 96.43%), có kiến trúc đơn giản, dễ module hóa, dễ tái tạo. Họ chọn các mô hình với nhiều kích cỡ khác nhau gồm R50x1 (sâu: 50 x rộng: 1), R50x3 (sâu: 50 x rộng: 3), R101x1 (sâu: 101 x rộng: 1), R101x3 (sâu: 101 x rộng: 3) và R152x4 (sâu: 152 x rộng: 4).
-

o   Bước tiếp theo là Pre-training (tạo Upstream). Các nghiên cứu gần đây chỉ ra rằng muốn có mô hình có độ chính xác cao, bắt buộc phải huấn luyện với nhiều dữ liệu. Tuy nhiên, nhiều dữ liệu chỉ thích hợp với mô hình lớn (tức là số tham số phải lớn). Vì vậy, ngoài việc chia kích cỡ mô hình, người ta cũng chia kích cỡ huấn luyện.

o   BiT-S: Tập mẫu huấn luyện là ImageNet-1K (1 nghìn loại, ~1.28 triệu ảnh)

o   BiT-M: Tập mẫu huấn luyện là ImageNet-21K (~21 nghìn loại, ~140 triệu ảnh)

o   BiT-L: Tập mẫu huấn luyện là JFT-300M (~18 nghìn loại, ~300 triệu ảnh)
-

o   Tiếp theo là bước tinh chỉnh (Fine-Tuning hay Downstream). Để biết rõ hơn tính khả dụng của mô hình, người ta thử fine-tuning với nhiều tập mẫu dữ liệu mang tính đại diện với số lượng rất ít ảnh được dán nhãn. Cùng với kết quả thử nghiệm ở bước pre-training, người ta đưa ra khuyến cáo với bộ quy tắc có tên là “BiT-HyperRule” dùng cho việc huấn luyện Downstream.

-

▥

Trong nhận dạng ảnh, và đặc biệt là trong phân loại ảnh, mặc dù Google có giới thiệu ViT, nhưng kiến trúc CNN, theo ý kiến cá nhân tôi, vẫn là kiến trúc “bao trùm” cho các mô hình với độ chính xác cao.

Có một xu thế có thể gây cho chúng ta không thật sự dễ chịu: đó là dữ liệu càng nhiều, mô hình càng lớn (số parameters lớn) thì mô hình có chất lượng càng tốt, độ chính xác càng cao. Điểm này làm cho các đơn vị, cá nhân có nguồn lực nhỏ ngày càng xa vời, ngày càng phụ thuộc vào các “Giant Techs” (siêu công ty công nghệ).

-

Tất nhiên, đó chỉ là các ý kiến cá nhân, mang tính chủ quan và có thể phiến diện. Nhưng dù có gây tranh cãi thì tôi tin rằng với vài dòng đàm luận này sẽ làm cho cốc cà phê của anh chị có “vị” hơn, lôi kéo tư duy của anh/chị hướng về công nghệ! 😊

 

(\_/)
( •_•)
/ >☕