Những ý tưởng kinh điển trong KHMT [1]

Trong nhóm nghiên cứu của tôi có một em đang học năm 2 và đang dần dần tìm hiểu về Vision và Machine Learning. Để bắt đầu, tôi hướng dẫn bạn này đọc slide và lecture notes của 2 course về Xử lí ảnh số. Do mới bắt đầu nên bạn này có những thắc mắc khá ngộ nghĩnh nhưng không biết phải trả lời thế nào cho trọn ý.

Một trong số những câu hỏi như thế đại ý là: “Em thấy hơi rối. Anh có thể nói sơ qua về những ý tưởng cơ bản của Xử lí ảnh số được không”?

Tôi hiểu chữ “ý tưởng cơ bản” ở đây là những ý tưởng, động lực  (motivation) chung nhất, chi phối/ảnh hưởng/xuất hiện trong tất cả các kĩ thuật xử lí ảnh. Và có lẽ cũng vì hiểu như vậy nên lúc đó tôi trả lời là: “Không có ý tưởng nào như vậy đâu em, hoặc nếu có thì anh cũng không biết”.

Xử lí ảnh đã là một phân ngành rất hẹp trong KHMT, nhưng để nói cho trọn vẹn những ý tưởng cơ bản nào đã hình thành nên lĩnh vực này, thì quả là nan giải. Kể cả trong tài liệu kinh điển hình như cũng không đề cập đến, thông thường chỉ là hệ thống hóa các kĩ thuật xử lí ảnh, cùng với hằng hà sa số công thức và phương trình !@#$%^&*()&^%$#@#$%^&*…

Cũng bẵng đi khá lâu, khi lùng sục trong MIT OCW, thì cùng với những course khác, tôi tìm thấy course có tên khá kêu: Những ý tưởng tuyệt cú mèo trong lý thuyết KHMT, của prof. Scott Aaronson.

Nhớ lại lúc học Đại học năm 2, tôi đã hình dung về  KHMT bằng cách dựa vào một vài lĩnh vực nghiên cứu rất hẹp của KHMT. Mãi đến năm 4 và đến tận bây giờ, tôi vẫn còn nghĩ KHMT chuyên nghiên cứu nền tảng lí thuyết cho sự vận hành của máy tính, không hơn, không kém.

Những ngày rảnh rỗi này, sau khi đọc một lượt lecture notes của  prof. Aaronson thì cách nhìn của tôi về KHMT đã rộng hơn đôi chút.

Theo Aaronson, KHMT không chỉ làm việc với máy tính, mà nó là ngành khoa học cung cấp công cụ toán học và hệ thống ý tưởng để hiểu về một hệ thống bất kì: từ máy tính (dĩ nhiên!) cho đến bộ não con người, sinh vật sống và cả vũ trụ.

Ý tưởng này không phải mới, vì tương truyền Edsger Dijkstra có  lần nói “Computer Science is no more about computers than astronomy is about telescopes“.

Một người bạn có lần nói rằng hắn học CNTT chỉ vì muốn lập trình được 1 cái game cỡ Warcraft, và muốn hiểu tại sao người ta làm được game đó. Có lẽ đa phần dân CNTT đều như vậy. Trong trường hợp của tôi là để hiểu làm thế nào để viết chương trình cho máy tính, người ta đã viết hệ điều hành như thế nào v.v… Ngày xưa Galileo chế ra kính viễn vọng chắc cũng không ngoài mục đích muốn hiểu vũ trụ hoạt động như thế nào. Suy cho cùng thì, để có thể làm được Warcraft, nhà sản xuất cũng đã tìm hiểu rất nhiều quy luật của tự nhiên, đồng thời tự đặt ra những quy luật mới: map, game logic v.v… Do đó tìm hiểu Warcraft cũng có cùng cách thức và phương pháp với tìm hiểu tự nhiên và vũ trụ.

Vậy phải chăng chỉ cần học KHMT là đã có thể hiểu vũ trụ? Còn Vật lí thì sao? Đương nhiên Vật lí là con đường khoa học chính thống để tìm hiểu về vũ trụ, nhưng điểm khác biệt là Vật lí đi từ trên xuống theo kiểu top-down, tìm những điểm tương đồng trong sự vật rồi thể hiện bằng các quy luật chung nhất, sau đó lại giải thích các quy luật đó bằng các quy luật thâm sâu hơn.

KHMT thì ngược lại.  Chúng ta định nghĩa một hệ thống bằng cách truy hồi: bắt đầu từ một hệ thống đơn giản nhất có thể, sau đó đặt ra một tập luật và giả sử rằng tập luật đó là đúng (đôi khi không cần chứng minh là nó đúng!), rồi tìm hiểu xem dựa trên hệ thống ban đầu, và tập luật đó, ta có thể tạo ra (và không thể tạo ra) những hệ thống phức tạp hơn như thế nào.

Máy tính điện tử được xây dựng dựa trên các cổng logic AND, OR và  NOT. Sau đó các loại cổng khác được định nghĩa: NAND, NOR, XOR… dựa trên 3 loại cổng cơ sở và các luật  Logic trong đại số Boole. Dựa trên những cổng này, ta có thể thiết kế mạch làm những nhiệm vụ từ “đơn giản” như cộng trừ nhân chia số nguyên, số dấu chấm động v.v… cho tới các VXL phức tạp có thể thực thi những lệnh phức tạp như: tính toán số học, logic, mã hóa và giải mã video v.v… Nhưng đó mới chỉ là bộ tính toán logic và số học (ALU).

Để có thể tạo ra một máy tính điện tử thực thụ theo kiến trúc Von Neumann, ta còn phải cần đến bộ nhớ. Bộ nhớ máy tính chỉ có thể lưu trữ 2 trạng thái là 0 và 1. Ban đầu người ta dùng bóng chân không, sau đó là băng từ, rồi đến tụ điện (SRAM, DRAM), bộ nhớ flash, đĩa quang… Từ đây ta có các máy tính từ loại siêu bình dân đến siêu máy tính cỡ như Watson.

Và đó phải chăng chính là ý tưởng cơ bản nhất của KHMT?

Nếu vẫn còn chưa đủ thuyết phục, thì có thể dẫn thêm hàng loạt ví dụ khác trong KHMT. Một ví dụ kinh điển là automata: ta định nghĩa các trạng thái có thể của hệ thống, các bước chuyển từ trạng thái này đến trạng thái khác, sau đó tùy thuộc vào dữ liệu input thì trạng thái của hệ thống sẽ thay đổi. Có thể nói automata là một trong những nền tảng quan trọng nhất của  KHMT. Automata được ứng dụng rộng rãi trong xử lí ngôn ngữ hình thức (xem thêm: kiến trúc Chomsky) và đặc biệt là một lĩnh vực chuyên biệt nhưng rất đẹp trong KHMT là Lý thuyết trình biên dịch. Nếu không có automata cùng những kiến thức liên quan như Push Down Automata, Regular Expression, các thuật toán xử lí  Automata thì đã không thể có ngành nghiên cứu  Trình biên dịch đẹp đẽ đến như vậy, và nếu không có trình biên dịch thì có lẽ ngành Công Nghệ Phần Mềm cũng không thể phát triển đến mức độ trưởng thành cao như vậy (hãy cứ tưởng tưởng lập trình OOP bằng mã máy, lúc đó Design Pattern có lẽ chỉ là giấc mơ xa xỉ! Các lĩnh vực khác của  CNPM như ước lượng, quy trình v.v… chắc cũng không thể có kết quả gì thuyết phục).

(Viết tới đây tôi lại nhớ đến một đoạn ngắn trong sách The Black Swan của  Taleb. Đại ý rằng cho trước một hệ thống đơn giản và một tập luật, thông thường ta luôn quá chú trọng đến việc khám phá những hệ thống nào có thể xây dựng được từ đó, mà rất ít khi quan tâm đến những hệ thống mà ta không thể xây dựng được từ chúng. Thực ra điều này có thể giải thích một cách dễ hiểu: nếu ta biết từ tập luật X không thể xây dựng được hệ thống  Y, thì có nghĩa là bằng cách nào đó hệ thống  Y phải được “biết trước”. Nhưng nếu đã biết trước Y thì cũng có nghĩa là ta đã biết làm thế nào để xây dựng Y. Thành ra để có thể khám phá những hệ thống nào không thể xây dựng được từ tập luật cho trước, thì cách duy nhất là phải tìm hiểu mọi hệ thống có thể xây dựng được từ các tập luật đó. Đây cũng là một chủ đề hay nhưng nếu “thi triển” ở đây thì sẽ làm loãng mất chủ đề chính là các ý tưởng kinh điển trong KHMT, do đó hãy hẹn lại một dịp khác).

Trở lại với các ý tưởng đẹp trong KHMT. Không phải chỉ có trong KHMT mới có cách tiếp cận bottom-up như vậy. Một ví dụ kinh điển của cách làm này là phương pháp dựng hình của người Hy Lạp cổ ( thời đó, người Hy Lạp rất giỏi hình học – và các môn nghệ thuật nói chung, trong khi người Ai Cập rất giỏi Số học): cho trước một thước thẳng và một compa. Những hình nào có thể dựng được chỉ bằng 2 công cụ này, cùng với tập luật sau:

– Ta có 2 điểm trên mặt phẳng, khoảng cách giữa 2 điểm này định nghĩa một đơn vị khoảng cách.

– Có thể vẽ đường thẳng nối 2 điểm bất kì (bằng thước thẳng).

– Có thể vẽ đường tròn nếu cho trước tâm và một điểm trên đường tròn đó (bằng compa).

– Có thể tạo một điểm tại vi trái giao nhau của 2 đường bất kì đã vẽ trước đó.

Chỉ bằng những luật này, có thể vẽ mọi thứ trong hình học phẳng (những bạn đã học Hình học cấp 2 Phổ thông chắc hẳn còn nhớ những bài toán dựng hình kiểu này). Friedrich Gauss khi mới 19 tuổi đã chứng minh được bằng các công cụ này có thể vẽ một đa giác đều 17 cạnh. Thậm chí nghe đồn lúc chết Gauss còn đòi khắc hình này lên bia mộ cho mình, nhưng người làm bia mộ từ chối, vì cho rằng nó chẳng khác gì hình tròn.

Tuy nhiên điều quan trọng không phải là những hệ thống/luật cụ thể, mà quan trọng là tính module hóa  (modularity) của ý tưởng này. Chẳng hạn nếu ta có cách dựng được đường vuông góc của một đoạn thẳng, thì ta có thể coi nó như một “hàm”, và lần sau nếu muốn dựng một đường vuông góc, thay vì chứng minh lại, ta có thể tái sử dụng hàm này. Rõ ràng ý tưởng này cũng đã được sử dụng rộng rãi trong lập trình hướng thủ tục cũng như hướng đối tượng. Và đó đôi khi cũng thể hiện “con đường tư duy” của con người: Chúng ta dựa trên những thành tựu có sẵn để sáng tạo nên cái mới. Trong nghiên cứu khoa học, có thể gọi đó là tính kế thừa (mặc dù dựa quá nhiều vào việc kế thừa thành tựu của tiền nhân có thể dẫn đến triệt tiêu khả năng sáng tạo).

Bản thân cách làm việc bottom-up cũng không phải là cách hay. Người châu Á thường làm việc theo cách này: tổng hợp những sự kiện, hiện tượng rời rạc rồi đúc kết lại bằng kinh nghiệm. Bói toán là mộ ví dụ rõ ràng. Ngoài ra còn có thể kể đến những kinh nghiệm của tiền nhân được đúc kết qua quá trình quan sát tự nhiên theo kiểu “Chuồn chuồn bay thấp thì mưa/Bay cao thì nắng bay vừa thì râm” v.v… Ngược lại người châu Âu có tư duy phân tích: cố gắng phát hiện các quy luật phổ quát, giải thích, chứng minh nó bằng thực nghiệm, rồi áp dụng cho các trường hợp tương tự. Nhờ đó mà dẫn đến những ví dụ có vẻ buồn cười như: người Trung Quốc phát minh ra giấy nhưng nghề in lại phát triển ở châu Âu (mà theo V. Hugo trong Nhà thờ Đức Bà Paris thì nghề in là một bước tiến nhảy vọt trong lịch sử văn minh loài người, đã tiêu diệt cả một ngành nghệ thuật cực thịnh là kiến trúc – có lẽ sẽ có bài viết riêng về chủ đề này), người Trung Quốc phát minh ra thuốc nổ nhưng chỉ để làm pháo đốt ngày Tết, còn người châu Âu dùng nó để chế ra thuốc nổ, súng thần công, đại bác v.v… (Cách đây mấy năm có sách này cũng hơi nổi tiếng, nhưng tôi chưa đọc nên không biết thế nào).

Trở lại với KHMT, những ví dụ đơn giản như vậy có thể cho ta thấy vai trò to lớn của  KHMT: đó không chỉ là hệ thống tư tưởng để làm việc với máy tính, mà nếu đi đến kiệt cùng thì nó cung cấp phương tiện để lí giải và hiểu mọi hệ thống trong cuộc sống: từ quá trình sinh trưởng của sinh vật cho đến cả vũ trụ.

Một cách cụ thể hơn, prof. Aaronson đã liệt kê một số vấn đề sau, coi đó là những ý tưởng cơ bản (vĩ đại) của  KHMT:

  • Toán logic – Định lí về sự không đầy đủ của Godel.
  • Automata, máy Turing.
  • Độ phức tạp thuật toán: P, NP, NP đầy đủ v.v…
  • Các thuật toán ngẫu nhiên, lí thuyết xác suất.
  • Mã hóa công cộng
  • Máy học (may quá!)
  • Quantum computing/algorithms

Hi vọng là sau này tôi sẽ có thời gian điểm qua một vài trong các vấn đề trên. Việc tìm hiểu những tư tưởng chính của  KHMT có lẽ cũng là một chủ đề thú vị cho những người làm việc trong lĩnh vực này. (Một điều hay là Aaronson không quá sa đà vào chi tiết toán, do đó rất dễ đọc).

Nếu giờ có người hỏi “ý tưởng chính của KHMT” thì có lẽ tôi đã có thể trả lời được, nhưng nếu hỏi về ý tưởng chính của Xử lí ảnh số, thì đó hẵng còn là vấn đề nan giải.

Advertisements

3 comments

  1. Các nhà triết học luôn đặt câu hỏi về việc liệu phát kiến/chế tạo một thứ gì đó có đúng theo quy luật của tự nhiên không. Các nhà kỹ sư thì chỉ quan tâm làm sao chế tạo được những thứ có thể làm được những điều tương tự trong tự nhiên, đôi khi không cần quan tâm sự kỳ dị của nó so với tự nhiên.

    Lấy ví dụ, từ xưa loài người mơ bay được như chim, với đôi cánh và lông vũ. Nhưng mọi ý tưởng như vậy đều thất bại trong quá khứ. Chiếc máy bay bây giờ không vỗ cánh như chim được, không chuyền cành được, cũng không đẻ trứng được. Nhưng nó bay xa hàng vạn dặm và chở hàng trăm tấn hàng hóa, tốc độ thì không con chim nào bằng.

    Nói một cách khác, theo ý kiên của anh, mục đích của khoa học do loài người tạo ra là để phục vụ loài người là chính, để hiểu thiên nhiên chỉ là một phương tiện, không phải là động cơ.

  2. Nhưng làm ra máy bay xuất phát từ “ham muốn” bắt chước tự nhiên mà, hehe 😀 Trong ngành CS thì cũng có thể kể ra hàng loạt idea bắt chước tự nhiên như thế, nhưng kết quả vẫn không đến đâu: lập trình tiến hóa, mạng neural… (tất cả đều là mô hình, và cũng có nhữnh ưu/khuyết điểm như mọi mô hình khác). Đương nhiên ý tưởng “bắt chước tự nhiên” có thể dẫn đến thất bại, nhưng từ thất bại đó mới dẫn đến cách tiếp cận khác, thành ra việc mô phỏng tự nhiên cũng có thể coi là động lực chứ 😀
    Tuy nhiên điểm chính ở đây không phải như vậy. Ý em (và có lẽ của course đó) chỉ là cái cách làm việc bottom-up của KHMT. Và nữa, KHMT không coi máy tính là đối tượng nghiên cứu, mà chỉ là công cụ (như kính thiên văn đối với thiên văn học).
    Việc “đồng nhất” và “tổng quát hóa” cách làm việc của KHMT thành cách hiểu hoạt động của tự nhiên cũng có vẻ hơi “tự sướng” tí 😀

  3. Hi anh Vũ ^^
    Theo bản thân em thì em hiểu đơn giản là: “Xử lý ảnh chính là đem từng pixel trên ảnh ra và “xử” nó” ^^

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s