Khoa học máy tính trong kỷ nguyên thông tin: Bài toán kích thước đồ thị và số hóa dữ liệu y tế
Những vấn đề của khoa học máy tính trong kỷ nguyên thông tin đã mở ra một cuộc cách mạng thông tin và những ứng dụng của nó sẽ làm thay đổi tương lai. Ở đây, chúng ta xem xét trên hai khía cạnh ứng dụng quan trọng là bài toán kích thước đồ thị và số hóa dữ liệu y tế.
Các nghiên cứu về đồ thị thưa (“sparse”) cũng phổ biến, ví dụ như mạng các trang web (World Wide Web – WWW) với hàng tỷ đỉnh: Phys.org
Kích thước đồ thị
Vào những năm 1960, các nhà nghiên cứu làm việc với những đồ thị có từ mười đến mười lăm đỉnh. Và khi máy tính xuất hiện người ta có thể nghiên cứu đồ thị có đến 1.000 đỉnh, bây giờ một máy tính nhanh có thể tính toán cho đồ thị có đến hơn một triệu (106) đỉnh. Các nghiên cứu về đồ thị thưa (“sparse”) cũng phổ biến, ví dụ như mạng các trang web (World Wide Web – WWW) với hàng tỷ đỉnh. Ngày nay chúng ta có thể tính toán đến đồ thị với 10100 đỉnh và 10100 cạnh. Nên nhớ là tổng số nguyên tử thấy được trong vũ trụ này cũng chỉ đến con số 10100 mà thôi. Làm sao chúng ta có thể lưu trữ đồ thị với 10100 đỉnh trong máy tính được? Thực ra là không. Người ta có thể thực hiện một bước đi ngẫu nhiên trên biểu đồ mà không lưu trữ nó trong máy tính vì chỉ cần có một thuật toán là có thể tìm ra được các đỉnh liền kề của một đỉnh cho trước. Chúng ta cũng chỉ cần lưu trữ đỉnh hiện tại của bước đi ngẫu nhiên mà thôi. Câu hỏi là cần mất bao lâu để một bước đi ngẫu nhiên hội tụ đến phân phối xác suấtcủa nó? (Khi bước đi ngẫu nhiên hội tụ, xác suất tìm thấy mỗi đỉnh tại mỗi thời điểm không đổi và gọi là xác suất dừng – “stationary probability”). Câu trả lời là nếu đồ thị có tính mở rộng, bước đi ngẫu nhiên sẽ hội tụ về xác suất dừng theo logarit của số đỉnh. Với biểu đồ có 10100 đỉnh chúng ta cần đi trong khoảng 100 lần bước thời gian (nhân một số hằng số).
Các bài toán về kích thước này có thể được tìm thấy trong rất nhiều ứng dụng được xử lý mỗi ngày. Ví dụ như chúng ta coi thành phần nguyên tử hợp chất của một vật liệu là một đỉnh. Có thể có rất nhiều các thành phần này nếu chúng ta có nhiều nguyên tử và thành phần của mỗi nguyên tử là liên tục. Phản ứng hóa học giữa các hợp chất này tạo thành cạnh của một đồ thị. Như vậy chúng ta có được một đồ thị với kích thước lớn và có thể khảo sát nó bằng cách đi ngẫu nhiên (khảo sát phản ứng hóa học giữa các trạng thái). Một ví dụ phổ biến khác là với một bộ bài 52 lá, có thể coi mỗi cách xếp là một đỉnh (52! đỉnh) và mỗi một lần tráo bài (thay đổi giữa hai cách xếp) là một cạnh. Có thể khảo sát đồ thị này mà không cần lưu trữ hết các trạng thái trong một số bước tỷ lệ theo hàm log.
Với bài toán đồ thị nhiều khi chúng ta cần phải lấy mẫu ngẫu nhiên dữ liệu vì hoặc là kích thước quá lớn hoặc là đồ thị biến đổi và không cố định. Chúng ta cần một chuỗi các số ngẫu nhiên có độ dài bằng với số lượng đỉnh và lại đặt ra câu hỏi làm sao lưu trữ được chuỗi này? Một lần nữa chúng ta không lưu trữ mà chỉ tạo ra một chuỗi ngẫu nhiên giả (pseudo random sequence). Câu hỏi tiếp theo là ngẫu nhiên như thế nào là đủ? Thông thường chúng ta chỉ cần ngẫu nhiên hai cấp. Một chuỗi các số 0 và 1 có thể coi là ngẫu nhiên hai cấp nếu mỗi phần tử của chuỗi có thể có giá trị 0 hoặc 1 với xác suất như nhau, và giá trị của mỗi phần tử không phụ thuộc vào giá trị của bất kỳ phần tử nào khác. Nếu tôi cung cấp cho bạn hai yếu tố, tôi có thể cung cấp cho bạn thông tin về tất cả các yếu tố trong chuỗi.
Dữ liệu lớn, công suất tính toán cao, kết nối Internet và các tiến bộ AI đang cùng tạo ra cuộc cách mạng thông tin, trong đó máy móc sẽ thay thế dần những công việc đòi hỏi tri thức và làm thay đổi rất cơ bản lao động trong xã hội. Từ một số ứng dụng chính có thể ảnh hưởng quan trọng trong tương lai, có thể thấy những cá nhân, tổ chức hay quốc gia nắm bắt được xu hướng và công nghệ này sẽ có những thế mạnh vượt trội.
Một ví dụ là khi người ta sử dụng tính ngẫu nhiên để xác định số lượng phần tử riêng biệt trong một chuỗi. Giả sử bạn làm việc cho chuỗi siêu thị Walmart và muốn biết có bao nhiêu khách mua hàng. Bạn có quyền truy cập vào luồng dữ liệu của mọi giao dịch mua trên toàn thế giới cùng với số thẻ tín dụng thanh toán. Đếm số khách hàng có thể coi như đếm số lượng thẻ, mỗi thẻ tương ứng một số gồm 16 chữ số. Bạn có thể tạo một vector nhị phân Boolean dài 1016, hay tạo một chuỗi kết nối (“linked list”), hay một bảng băm, v.v… Tuy nhiên nếu chỉ cần ước lượng tương đối thì có thể làm như sau, và chỉ cần lưu trữ một từ duy nhất. Đó là ghi lại số thẻ nhỏ nhất mà bạn quan sát được. Có thể thấy là nếu bạn viết đều các số từ 1 đến 1016 và đánh dấu các số thẻ tín dụng quan sát được, khoảng cách trung bình giữa các số thẻ sẽ bằng 1016 chia cho số lượng thẻ riêng biệt. Do đó số thẻ nhỏ nhất cũng gần bằng khoảng cách này và xấp xỉ bằng 1016 chia cho số lượng thẻ riêng biệt. Cuối cùng lấy 1016 chia cho số thẻ nhỏ nhất quan sát được chúng ta ước lượng được số lượng thẻ.
Một vấn đề khác là thuật toán giả định các số thẻ phân bố ngẫu nhiên, có khả năng không phải như vậy. Trong trường hợp, đó bạn có thể sử dụng hàm băm để làm cho dữ liệu độc lập một cách thống kê. Không nhất thiết phải phân bố độc lập trên mọi giá trị mà chỉ cần độc lập hai chiều là đủ.
Số hóa dữ liệu y tế
Khi số hóa hồ sơ y tế, chúng ta cần đảm bảo nhu cầu riêng tư và bảo mật của mỗi các nhân. Ví dụ, nếu toàn bộ lịch sử y tế của tôi được số hóa và tôi bị bệnh ở đâu đó trên thế giới thì bác sĩ của tôi cũng có thể đưa ra được phương pháp điều trị tốt nhất. Tuy nhiên tôi lại không muốn công ty bảo hiểm nhìn thấy toàn bộ lịch sử y tế của tôi. Trên thực tế, công ty bảo hiểm cũng hoàn toàn không cần xem hồ sơ bệnh án của từng cá nhân, tất cả những gì họ cần là một số ước lượng khách hàng đó đã chi bao nhiêu cho y tế. (Khác với các nhà nghiên cứu y tế muốn truy cập vào mỗi hồ sơ y tế của một người khác để cải thiện các kỹ thuật chữa trị). Làm sao cung cấp những thông tin thống kê cho bảo hiểm mà không để họ có quyền truy cập vào bất kỳ thông tin cá nhân nào? Hai kỹ thuật đang nổi lên là: bằng chứng kiến thức bằng không (“zero knowledge proofs”) và quyền riêng tư khác biệt (“differential privacy”).
Bằng chứng không kiến thức
Bằng chứng không kiến thức về một tuyên bố nào đó là bằng chứng chứng minh tuyên bố đó là đúng mà không cung cấp bất kỳ thông tin nào khác. Để minh họa, chúng ta xét bài toán tô 3 màu cho đồ thị sao cho không có hai đỉnh liền kề có cùng màu. Đây là một bài toán NP-đầy đủ và không có thuật toán nào chạy với thời gian đa thức đã biết. Giả sử bạn có một biểu đồ với một triệu đỉnh và bạn muốn tô màu cho nó còn tôi có một doanh nghiệp cung cấp dịch vụ tô màu. Tuy nhiên, chúng ta không thể hợp tác vì không tin tưởng nhau: bạn không muốn trả tiền khi không biết tôi có khả năng tô màu cho đồ thị của bạn hay không còn tôi lại không muốn cho bạn xem kết quả tô màu khi bạn chưa trả tiền. Giải pháp là tôi cung cấp cho bạn một bằng chứng rằng tôi đã tô màu được mà không cung cấp cho bạn bất kỳ thông tin nào về cách tô màu. Ở đây chúng ta có thể sử dụng một bằng chứng không kiến thức.
John E. Hopcroft, nhà khoa học máy tính lý thuyết Mỹ. Các cuốn sách về lý thuyết tính toán và các cấu trúc dữ liệu của ông đều được coi như tiêu chuẩn trong những lĩnh vực này. Nguồn: wikipedia
Với mỗi đỉnh trên đồ thị, tôi đặt màu của nó trong một phong bì và dán lại. Bạn có thể yêu cầu xem màu của hai đỉnh liền kề và tôi cho mở hai phong bì ra. Như vậy bạn cũng không có thông tin gì về cách tô màu cả vì có thể hoán vị màu của các đỉnh cho nhau để có được hai màu của hai đỉnh này. Tuy nhiên, nếu tôi cho phép bạn nhìn thấy một đỉnh khác thì tôi sẽ cung cấp cho bạn một số thông tin và tôi không làm vậy. Thay vào đó tôi phá hủy tất cả các phong bì, hoán vị các màu trên đồ thị và tạo lại các phong bì với màu thích hợp cho mỗi đỉnh. Điều này nghe có vẻ phức tạp nhưng chúng ta làm trên máy tính thôi. Khi bạn muốn thấy màu của hai đỉnh tôi sẽ đưa cho bạn chìa khóa để giải mã hai đỉnh đó (dựa trên việc hoán vị màu trước đó). Vì tất cả điều này được thực hiện bằng điện tử nên tôi chỉ mất vài phút để thuyết phục bạn tôi đã có cách tô màu và chúng ta có thể hợp tác. Đây chính là một ví dụ về bằng chứng không kiến thức. Một ví dụ khác có thể thấy là trong tương lai, nếu một hãng chế tạo được máy tính lượng tử, họ sẽ phải chứng minh được điều đó (tính toán dựa trên hiệu ứng cơ học lượng tử) mà không làm lộ chi tiết của thiết kế.
Quyền riêng tư khác biệt
Sự riêng tư rất cần thiết trong các ứng dụng kinh doanh ví dụ như dẫn đường xe hơi, chuỗi cung ứng hay hệ thống vận chuyển. Ví dụ: Hệ thống dẫn đường có thể ghi lại tọa độ GPS của bạn trong tháng trước để hướng dẫn tốt hơn. Tuy nhiên, chúng ta lại không muốn điều đó vì các hệ thống này có thể biết xe của bạn đỗ ở đâu vào ban đêm, bạn đi làm ở đâu, đi chợ ở đâu, v.v. Nếu có thể vừa cung cấp thông tin cho hệ thống lại vừa không mất dữ liệu cá nhân thì sẽ tốt hơn. Một ví dụ khác là chúng ta đều muốn có được dịch vụ Gmail tốt hơn và để làm như vậy Google sẽ cần thu thập hành vi và thậm chí cả nội dung của email. Rõ ràng chúng ta không muốn thế nhưng vẫn muốn có dịch vụ email tốt hơn.
Trong tương lai, sẽ có rất nhiều hệ thống phải đối mặt với vấn đề dữ liệu riêng tư như vậy.
Dữ liệu lớn, công suất tính toán cao, kết nối Internet và các tiến bộ AI đang cùng tạo ra cuộc cách mạng thông tin, trong đó máy móc sẽ thay thế dần những công việc đòi hỏi tri thức và làm thay đổi rất cơ bản lao động trong xã hội. Từ một số ứng dụng chính có thể ảnh hưởng quan trọng trong tương lai, có thể thấy những cá nhân, tổ chức hay quốc gia nắm bắt được xu hướng và công nghệ này sẽ có những thế mạnh vượt trội.
TÀI LIỆU THAM KHẢO
[1] Kun He, Yiwei Sun, David Bindel, John E. Hopcroft and Yixuan Li, “Detecting overlapping communities from local spectral subspaces,” in 15th IEEE International Conference on Data Mining (ICDM), Atlantic City, USA, 2015, pp. 769-774.
[2] Yixuan Li, Kun He, David Bindel and John E. Hopcroft. “Uncovering the small community structure in large networks,” in 24th International Conference on World Wide Web (WWW), Florence, Italy, 2015, pp. 658-668.
[3] Kun He, Sucheta Soundarajan, Xuezhi Cao, John E. Hopcroft and Menglong Huang, “Revealing multiple layers of hidden community structure in networks,” CoRR abs/1501.05700, 2015.
[4] Kun He, Yingru Li, Sucheta Soundarajan and John E. Hopcroft, “Hidden community detection in social networks,” Information Sciences, vol. 425, pp. 92-106, Jan. 2018.
[5] Alan Mislove, Bimal Viswanath, P. Krishna Gummadi, Peter Druschel, “You are who you know: inferring user profiles in online social networks,” in Proceedings of the 3rd International Conference on Web Search and Web Data Mining (WSDM), New York, NY, USA, 2010, pp. 251-260.
[6] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg and Fei-Fei Li, “ImageNet Large Scale Visual Recognition Challenge,” International Journal of Computer Vision, vol. 115, no. 3, pp. 211-252, April 2015.
[7] ImageNet Large Scale Visual Recognition Challenge (ILSVRC), [Online]. Available: http://www.image-net.org/challenges/LSVRC/.
[8] Yixuan Li, Jason Yosinski, Jeff Clune, Hod Lipson, and John E. Hopcroft, “Convergent learning: Do different neural networks learn the same representations? ” in ICLR, 2016.
[9] Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C. Courville, Yoshua Bengio, “Generative adversarial networks,” in Advances in Neural Information Processing Systems(NIPS). Montreal, Quebec, Canada, 2014, pp. 2672-2680.
[10] Anh Nguyen, Jason Yosinski, and Jeff Clune, “Deep neural networks are easily fooled: high confidence predictions for unrecognizable images,” in IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2015
[11] Blum, Manuel, Feldman, Paul; Micali, Silvio. “Non-interactive zero-knowledge and its applications,” in Proceedings of the twentieth annual ACM symposium on Theory of computing (STOC), Chicago,Illinois, USA, 1988, pp. 103–112.
[12] Cynthia Dwork. “Differential Privacy, Automata, Languages and Programming,” in 33rd International Colloquium (ICALP), Venice, Italy, 2006, pp. 1-12.
Nguyễn Quang dịch – https://tiasang.com.vn/
TheMinh1024 