Grokking Newsletter

By Grokking Vietnam

#206 - Technical debt nào tiềm ẩn trong hệ thống Machine Learning?

#208・
10.1K

subscribers

222

issues

Subscribe to our newsletter

By subscribing, you agree with Revue’s Terms of Service and Privacy Policy and understand that Grokking Newsletter will receive your email address.

Grokking Vietnam
Grokking Vietnam
Thân chào quý bạn đọc Newsletter,
Trong các survey phản hồi trước đây, team Grokking có ghi nhận góp ý từ một số bạn đọc là việc tìm lại nội dung của các số newsletter cũ hơi khó.
Nhằm giải quyết vấn đề này, team Grokking đang phát triển một trang chỉ mục online dành cho các bài viết liên quan đến chủ đề Software Engineering nói chung, đặc biệt là các bài viết đã được đăng trên các số newsletter cũ.
Sắp tới, team product đang cần phỏng vấn 4-5 bạn đọc thường xuyên của Newsletter để có thêm ý tưởng giúp hoàn thiện trang chỉ mục này. Buổi phỏng vấn sẽ diễn ra online và dự kiến sẽ kéo dài 1-2 giờ đồng hồ.
Bạn đọc nào quan tâm và có thể tham gia phỏng vấn vui lòng đăng ký vào form này: Form đăng ký , team Grokking sẽ liên hệ để xếp lịch phỏng vấn tùy theo thời gian rảnh của bạn. Team cũng sẽ gửi tặng 1 quyển Dijkstra tập 2 vừa xuất bản đến các bạn tham gia phỏng vấn để cảm ơn.
Rất cảm ơn quý bạn đọc đã ủng hộ Grokking Newsletter thời gian qua, và rất mong sẽ nhận được nhiều sự ủng hộ hơn nữa trong thời gian sắp tới.
Trong số này, chúng ta sẽ cùng tìm hiểu về:
  • Cách WePay phát triển hệ thống model logging;
  • Tại sao một số cryptographic key lại nhỏ hơn các cryptographic key khác;
  • Technical debt tiềm ẩn của các hệ thống Machine Learning;
  • Bài nghiên cứu về FLP Impossibillity;
  • Lời giải bài Number of Matching Subsequences.

Những bài viết hay
Góc Distributed System
FLP Impossibillity là một bài nghiên cứu quan trọng về hệ thống phân tán, trong đó chỉ ra một số giới hạn mà chúng ta không thể vượt qua được. Trong bài, nhóm tác giả đã chứng minh rằng: Không tồn tại consensus protocol cho những hệ thống phân tán không đồng bộ, nếu trong hệ thống đó có thể chứa các process lỗi.
Định nghĩa về consensus
Các thuật toán consensus được dùng để giải quyết bài toán đồng thuận trên hệ thống phân tán. Một thuật toán consensus được coi là hợp lệ nếu thoả mãn ba điều kiện sau đây:
  • Termination: Tất cả các process bình thường đều sẽ đưa ra quyết định trên một giá trị.
  • Agreement: Tất cả những process đưa ra quyết định đều quyết định cùng một giá trị.
  • Validity: Giá trị được đồng thuận phải được đề nghị từ một trong các process trong hệ thống.
Chúng ta mặc định rằng: Thuật toán consensus chỉ chạy đúng khi số lượng process bị lỗi là ít hơn một hằng số được định trước.
Định nghĩa về asynchronous model
Asynchronous là một trong ba giả định về sự đồng bộ trong hệ thống phân tán (hai giả định còn lại là Synchronous và Partially synchronous). Asynchronous model có những tính chất sau:
  • Không xác định được tốc độ xử lý của các process;
  • Message có thể bị deliver trễ với thời gian không xác định;
  • Không sử dụng synchronized clocks;
  • Không thể sử dụng các thuật toán dựa vào time-out;
  • Không thể phân định được hai trường hợp: process này bị lỗi, hay chỉ đơn giản là process đó xử lý rất chậm.
Chứng minh
Nghiên cứu này chứng minh rằng: Không tồn tại thuật toán consensus với những điều kiện sau:
  • Asynchronous model;
  • Chỉ cần duy nhất một process bị lỗi (crash-stop failure);
  • Không xảy ra Byzantine failure;
  • Messages system là đáng tin cậy (Tất cả message đều được deliver đến các process không bị lỗi duy nhất một lần);
  • Consensus: Đồng thuận trên tập giá trị 0, 1; và chỉ cần một số process đồng thuận trên cùng một giá trị (partially correct).
Có thể thấy rằng những điều kiện trên yếu hơn các điều kiện thông thường trên hệ thống phân tán (trừ asynchronous model). Do đó, nếu chúng ta chứng minh được không tồn tại thuật toán concensus trong trường hợp này, thì consensus protocol cũng không thể tồn tại trong các trường hợp tổng quát hơn.
Mời các bạn đọc về bài gốc tiếng Anh ở đây, hoặc giải thích chứng minh bằng tiếng Việt ở đây.
Góc Lập Trình
Lời giải đề bài tuần trước:
Với string “s” và một dãy các string “words” đã cho, cho biết có bao nhiêu string trong tập “words” là dãy con của “s”?
Lời giải:
Đây là một bài mở rộng của bài kiểm tra dãy con: Is Subsequence, vì vậy ta có ngay cách tiếp cận là: với mỗi string “word” trong “words”, ta kiểm tra xem “word” có phải là dãy con của “s” hay không? Nếu đúng, ta tăng biến đếm lên 1. Ta có giải mã như sau: https://pastebin.com/vR2EBpxt
Tuỳ vào cách thực hiện hàm “isSubsequence”, giải thuật sẽ có độ phức tạp khác nhau.
Ví dụ: Bằng cách kiểm tra tuyến tính, ta có độ phức tạp giải thuật time complexity là O(W*S), trong đó:
  • W là số string trong “words”,
  • S là độ dài string “s”.
Với cách tiếp cận trên, ta phải duyệt string “s” W lần. Áp dụng vào bài này, string “s” dài hơn rất nhiều so với string trong “words”:
Constraints:
  • - 1 <= s.length <= 5 * 10^4
  • - 1 <= words.length <= 5000
Vì vậy, ta cần một cách tiếp cận khác, tối ưu hơn. Nếu ta có thể chỉ duyệt string “s” một lần, liệu ta có thể có độ phức tạp time complexity tốt hơn so với giải thuật trên không?
Tại mỗi kí tự “sch” của string “s”, ta thử tìm kí tự tương ứng của mỗi string “word” trong tập “words” như sau:
Ví dụ: s = "apppleen", words = ["apple", "pen"]
  1. Ta nhóm string trong “words” theo kí tự đầu tiên: heads = { 'a': ["apple"], 'p': ["pen"] }
  2. Với sch là “a” ([a]pppleen), ta tăng vị trí của các từ trong group ‘a’ lên 1, ta có: heads = { 'p': ["pple", "pen"] }
  3. Với sch là “p” (a[p]ppleen), ta tăng vị trí của các từ trong group ‘p’ lên 1, ta có: heads = { 'p': ["ple"], 'e': ["en"] }
  4. Tiếp tục duyệt string “s” cho tới cuối cùng, ta sẽ có kết quả của bài toán.
Mời bạn xem chi tiết giải thuật tại: https://pastebin.com/fCxcpBNV
Code & Tools
  • kuchiki - Thư viện để thao tác HTML/XML tree bằng Rust.
  • faker - Thư viện JavaScript giúp tạo ra một lượng lớn dữ liệu giả trong browser và Node.js, phục vụ mục đích testing và development.
Góc Sponsors
FPT Smart Cloud (FCI) – a subsidiary of FPT Corporation, is a leading provider of Artificial Intelligence (AI) and Cloud Computing solutions in Vietnam. FCI was established with a mission to offer best-in-class AI & Cloud platforms, creating a breakthrough in business operations. FPT Smart Cloud strives to be a pioneer in AI and Cloud with state-of-the-art technology, a diverse product ecosystem, and global connectivity.
Products and services within the FPT Smart Cloud ecosystem:
  • Infrastructure as a Service (IaaS)
  • Platform as a Service (PaaS)
  • Software as a Service (SaaS)
  • Artificial Intelligence (AI)
Open positions:
Other positions at FPT Smart Cloud Careers Page
Quotes
When they first built the University of California at Irvine they just put the buildings in. They did not put any sidewalks, they just planted grass. The next year, they came back and put the sidewalks where the trails were in the grass. Perl is just that kind of language. It is not designed from first principles. Perl is those sidewalks in the grass.
― Larry Wall
Did you enjoy this issue? Yes No
Grokking Vietnam
Grokking Vietnam

Cảm ơn bạn đã dành thời gian đọc newsletter kỳ này và chúng tôi hi vọng rằng bạn đã khám phá ra một số điều mới mẻ từ các bài viết trên. Các bạn có thể đọc lại các số cũ tại website newsletter.grokking.org

In order to unsubscribe, click here.
If you were forwarded this newsletter and you like it, you can subscribe here.
Created with Revue by Twitter.
Viet Nam