Blog Khoa Học Máy Tính

Một bài viết rất hay của tờ Economist nói về sự phát triển và suy tàn của cấu trúc tài trợ cho nghiên cứu và phát triển (R&D) khoa học và công nghệ Mỹ từ sau thế chiến.

Đại khái, mô hình “tách biệt nghiên cứu khoa học cơ bản và phát triển ứng dụng công nghệ” là do Vannevar Bush, cố vấn khoa học của tổng thống Franklin Roosevelt, đề nghị trong báo cáo năm 1945:

Under Bush’s plan, universities researched basic science and then industry developed these findings to the point where they could get to market. The idea of R&D as two distinct activities was born. Firms soon organised themselves along similar lines, keeping white-coated scientists safely apart from scruffy engineers.

Mô hình này đã cực kỳ thành công trong vòng 50, 60 năm qua

This approach was a stunning success. AT&T’s Bell Labs (pictured above) earned six Nobel prizes for inventions such as the laser and the transistor. IBM picked up three, two from its Zurich Research Laboratory alone. And Xerox’s Palo Alto Research Centre (PARC) devised the personal computer’s distinctive elements, including the mouse, the graphical user interface and the Ethernet protocol for computer networking (although it was criticised for failing to commercialise such leaps forward).

Thời gian gần đây, cấu trúc tài trợ của NSF, DARPA cho nghiên cứu khoa học cơ bản đã bị “lên án” mạnh mẽ bởi các nhà khoc học trong giới academics là không có tầm nhìn xa. Các công ty, dưới sức ép của kinh tế thị trường càng lúc càng rời xa nghiên cứu cơ bản mà tập trung vào nghiên cứu ứng dụng, hoặc ít nhất luôn luôn dùng thị trường làm thước đo tối hậu cho các phát kiến mới.

Now the big corporate laboratories are either gone or a shadow of what they were. Companies tinker with today’s products rather than pay researchers to think big thoughts. More often than not, firms hungry for innovation look to mergers and acquisitions with their peers, partnerships with universities and takeovers of venture-capital-backed start-ups. The traditional separation of research and development enshrined by Bush in 1945 is rapidly disappearing, especially in the information-technology industry.

Chuyện này không nhất thiết là tồi tệ nếu một số câu hỏi lớn của khoa học tính toán đã được trả lời tương đối thỏa đáng và rất cần nghiên cứu ứng dụng để thương mại hóa. Bài báo của Economist đưa ra lập luận này:

One reason for the shift towards more commercially minded research in technology companies is that the nature of IT has changed so much. In Bush’s time the science that went into computing was itself closer to basic research. By contrast, many of the big scientific questions in computing have been answered—at least well enough for companies to find that innovation emerges from new ways of arranging today’s technologies rather than inventing new ones. Dell’s innovation was a business model that used extreme supply-chain efficiency to create bespoke computers. Likewise, Apple’s iPod is a new interface atop standard industry parts.

Trong thời khoảng ngắn hạn (5-10 năm đổ lại) thì lập luận này có chỗ đứng, nhưng nó chắc chắn sẽ đổ khi các ứng dụng của nghiên cứu cơ bản từ hồi thập niên 60 trở nên bão hòa. Vì dụ, cấu hình hiện tại của Internet có quá nhiều khiếm khuyết, cần nghiên cứu cơ bản để thiết kế lại. Tôi cũng hoàn toàn không đồng ý là “many of the big scientific questions in computing have been answered”, mặc dù tôi đồng ý [trong vài năm tới] với câu thứ hai thòng theo “at least well enough for companies to find that innovation emerges from new ways of arranging today’s technologies rather than inventing new ones”.

Tôi thật sự tiếc về sự ra đi của Bell Labs nguyên thủy. Cơ man nào là nghiên cứu cơ bản thay đổi toàn bộ thế giới đã hình thành từ đó. Đến hiện nay tôi vẫn thường xuyên đọc các bài báo từ “đời tám hoánh” của Bell Labs nguyên thủy.

Chủ đề: CNTT các nước và VN | Bình luận (6) »

Theo Guardian

It’s official: beer is the most popular beverage on the planet. As a photography exhibition opens in celebration, Roger Protz takes us on a guided tour of pale ales and pilsners - and nominates the best beer in the world

Bia tôi thích nhất: Corona.

Chủ đề: Vui - Giải Trí | Bình luận »

74. Phân hoạch tập hợp thành hai tập A và B sao cho tổng các phần tử trong A bằng tổng các phần tử trong B và tổng bình phương các phần tử của A và B bằng nhau và tổng lập phương của các phần tử của A và B bằng nhau.
75. Một lão nông qua đời để lại cho 3 con 17 con trâu. Trong di chúc, ông muốn cho con trưởng 1/2, con kế 1/3, và con út 1/9 số trâu. Ba người con phân chia thế nào?

Chủ đề: Dành cho du học sinh & Vui - Giải Trí | Bình luận (3) »

Quyển sách Mindset: The New Psychology of Success của giáo sư tâm lý Carol Dweck (Standford) sẽ nói về điều này. Tờ New York Magazine có một bài rất hay tóm tắt các kết luận chính của nghiên cứu của Dweck:

1. Khen “cháu thông minh” quá nhiều (cho dù nó thông minh thật) có thể làm hại tính tự tin của đứa trẻ. Những đứa trẻ nghĩ là mình thông minh có xu hướng sợ thử giải quyết các vấn đề khó khăn, vì nếu nó thất bại nó sẽ nghĩ rằng do nó kém thông minh nên thất bại.
   

   When students transition into junior high, some who’d done well in elementary school inevitably struggle in the larger and more demanding environment. Those who equated their earlier success with their innate ability surmise they’ve been dumb all along. Their grades never recover because the likely key to their recovery—increasing effort—they view as just further proof of their failure. In interviews many confess they would “seriously consider cheating.”

   Students turn to cheating because they haven’t developed a strategy for handling failure. The problem is compounded when a parent ignores a child’s failures and insists he’ll do better next time. Michigan scholar Jennifer Crocker studies this exact scenario and explains that the child may come to believe failure is something so terrible, the family can’t acknowledge its existence. A child deprived of the opportunity to discuss mistakes can’t learn from them.

   Kết luận này làm tôi nhớ đến vụ có nên học chuyên toán hay không hồi nào. Đối diện và chấp nhận thất bại là một đức tính rất cần thiết cho mọi người, bao gồm học sinh, sinh viên, và đặc biệt là những người làm khoa học. Tôi thất bại hàng ngày hàng giờ trong việc giải quyết các bài toán nảy sinh trong nghiên cứu của mình. Khác với một số ngành nghề khác, những người làm khoa học có khả năng thất bại (không tìm ra lời giải cho một bài toán nào đó) trong một thời gian dài. Andrew Wiles thất niên diện bích mới giải được bài toán Fermat lớn. So với việc lập trình hay xây nhà, ngày nào ta cũng có một thành tựu nhất định nào đó (ví dụ như viết được thêm 1000 dòng lệnh hay xây thêm được một bức tường nhà), thì việc quen chịu đựng được thất bại cả mấy tháng hay mấy năm liền của dân làm khoa học nói chung là một đặc tính khá đặc thù. Học sinh chuyên toán rất quen với thất bại. Có rất nhiều bài toán họ không giải được, và quá trình học chuyên toán luyện cho họ một khả năng “chịu đựng” và “cần cù” tấn công một bài toán trong một thời gian dài. Tôi cho rằng đặc trưng này cực kỳ có lợi cho họ về lâu về dài nếu họ theo đuổi con đường nghiên cứu khoa học. (Có lẽ hơi thừa, nhưng phải nhấn mạnh rằng “chuyên toán” không phải là con đường duy nhất, ngoài Thiếu Lâm còn có Võ Đang, Vịnh Xuân, Hồng Gia Quyền, Karate, Taekwondo, … để luyện não.)

2. Khen “cháu làm việc cần cù” (cho nên mang lại một thành quả nào đó) là lời khen rất có ích! Những đứa trẻ tin rằng thành quả của nó là do nó lao động mà có sẽ cố gắng lao động nhiều hơn nữa khi nó thất bại. Lười lao động là cái có thể sửa được, kém thông minh thì (bọn nhỏ nghĩ là) trời sinh ra thế.
3. Một thông điệp rất quan trọng là bộ não cũng như một bộ cơ bắp, rèn luyện nhiều thì não sẽ làm việc tốt hơn! Tôi hoàn toàn nhất trí với kết luận này. Dĩ nhiên là có một ngưỡng trần cho chiến lược “cần cù bù thông minh”, ví dụ tôi có lao động cả đời cũng không nghĩ ra được thuyết tương đối, nhưng ngưỡng trần này cao hơn vạn lần cái ta tưởng.

   Nhân đây cũng nói luôn là thành ngữ “cần cù bù thông minh” mang hàm ý xấu cho “cần cù” (nghĩa là anh không thông minh lắm nên mới phải làm việc nhiều như thế để bù lại). Ẩn ý này trong thành ngữ là sai lầm nghiêm trọng!

   Cần cù chắc chắn sẽ làm cho bạn và tôi thông minh hơn! Ít nhất, nếu bạn không tin điều này thì có thể hiểu nó theo cách khác: cần cù sẽ làm cho bạn và tôi khai thác trí thông minh của mình triệt để hơn nhiều lần.

   Bên Cosmic Variance có một bài viết rất hay về cần cù, thông minh, và thiên tài. Tôi cũng đã post bài về thiên tài là do rèn luyện. Thomas Edison có câu nói nổi tiếng là “Genius is 1% inspiration and 99% perspiration!”

4. Những lời khen càng cụ thể thì càng có ích. Ví dụ: khen là con đá bóng không tham bóng, hay chuyền bóng cho bạn, sẽ làm cho con bạn trở thành tiền vệ tốt hơn; thay vì khen chung chung “con đá bóng giỏi quá”. Những lời khen chung chung làm đứa trẻ không biết nó cần phát huy khả năng gì.
5. Những lời khen “động viên” thiếu tính chân thực sẽ có tác dụng ngược. Ví dụ:
   

   According to Meyer’s findings, by the age of 12, children believe that earning praise from a teacher is not a sign you did well—it’s actually a sign you lack ability and the teacher thinks you need extra encouragement. And teens, Meyer found, discounted praise to such an extent that they believed it’s a teacher’s criticism—not praise at all—that really conveys a positive belief in a student’s aptitude.

Bài báo ở tờ tạp chí New York kết luận rất tốt. Hãy nghĩ về bộ não của bạn như một bộ cơ bắp và luyện tập nó thường xuyên, sẽ rất có lợi về lâu dài.

Chủ đề: Giáo dục & Giới thiệu sách | Bình luận (7) »

Chủ đề: Vui - Giải Trí | Bình luận (1) »

Machine learning hay statistics?
Quá nhiều terminologies làm cho tôi headache
Tôi khoái learning machines, bạn lại thích models
Bạn hỏi tôi về covariates, tôi nói chuyện features

Machine learning hay statistics?
Thứ nào nghe sexy hơn thứ nào boring sh*t?
Một câu hỏi nhỏ, nếu bạn vẫn gà mờ …
Xin chịu khó đọc thêm blog Ka Hờ Mờ Tờ

Tiếp theo bài blog hôm trước, tôi xin nói thêm về sự hỗn độn về thuật ngữ trong machine learning. Dân làm machine learning nói riêng và KHMT nói chung rất sáng tạo trong việc đặt tên cho sản phẩm thuật toán của mình. Mỗi một tít bài báo ở hội nghị thường có kèm tên một thuật toán (hay system, hay architecture mới), cho dù ý tưởng của bài báo chỉ là một thay đổi epsilon của một bài báo trước đó.

Trong machine learning, mỗi một thuật toán máy học mới thường có cái tên là một machine gì đấy, làm ta liên tưởng đến một cậu HAL đang được thai nghén. Vậy nên có cả một vườn thú các learning machines, ví dụ có thể tìm thấy ở Journal of Machine Learning Gossip (một website hóm hỉnh của dân làm ML). Điều này làm cho những người bắt đầu bước vào vườn thú rất choáng. Mặc dù xuất phát điểm mang tính lịch sử của machine learning là từ trí tuệ nhân tạo, nhưng nhìn lại, rất nhiều ý tưởng trong ML đã được khơi nguồn từ statistics, và trong một thời gian khá dài (từ những năm 1950 đến những năm đầu 1990) đáng tiếc là không có sự liên hệ đầy đủ giữa hai ngành. Dưới đây tôi thử liệt kê vài khái niệm trong machine learning và dịch sang ngành thống kê. Đây là open list, ai có thêm thì xin mời bổ sung vào. Để tiện tôi chia ra làm một vài mục:

Mô hình:

• machines, learning machines (e.g., support vector machines): models
• networks (e.g., neural networks, Bayesian networks, Markov networks): models
• concepts: models
• multilayer networks: hierachical models
• Bayes nets, Bayesian networks: (probabilistic) graphical models
• instance-based learning methods: nonparametric models
• input features: covariates
• output: response variable
• model selection: model choice

Thuật toán:

• learning algorithms, training algorithms: (frequentist) estimation procedures

• Bayesian learning: Bayesian inference
• probabilistic reasoning: probabilistic inference
• unsupervised learning, clustering algorithms: use of latent (hidden) variable models, generative models
• supervised learning, classification algorithms: classification, regression, discriminative models
• empirical risk minimization principle: M-estimation methods (M stands for maximization)
• cost function: loss function

Một số linh tinh khác:

• PAC (probabilistically approximately correct) learning: đảm bảo đúng với xác suất cao
• convergence: trong ML thì đây thường chỉ sự hội tụ của thuật toán, nhưng trong statistics thì đây thường nói về tốc độ hội tụ của estimation error của một estimation procedure nào đó
• sample: trong ML thì chỉ một data point, trong statistics thì chỉ một tập các data points.

Một số lớn các khái niệm căn bản của ML (thường là bắt đầu một cách ad hoc) đã được giới thiệu và nghiên cứu một cách có hệ thống và chặt chẽ ở ngành thống kê. Ngược lại, còn rất nhiều khái niệm hay và sâu sắc trong thống kê vẫn chưa được áp dụng trong các vấn đề machine learning. Tuy vậy machine learning ngày càng đóng góp cho statistics những khái niệm mới mẻ, đặc biệt liên quan đến khía cạnh computation complexity và hiệu quả thuật toán, và ML cũng góp phần phát triển nhiều mô hình (learning machines) rất thích hợp cho large scale và dynamically processed data mà ngành statistics đã từng thờ ơ. Ví dụ một số thuật ngữ sau ở machine learning nhưng không có mặt ở mainstream statistics cho đến thời gian gần đây:

• computational complexity của một vấn đề learning
• computational efficiency một learning machines
• message-passing type algorithms
• các mô hình về on-line learning
• reinforcement learning
• graphical models
• v.v.

Nhìn lại, không khó mà nhận thấy rằng intellectual root của machine learning là statistics và computer science. Điều này không nằm ngoài quy luật của phát triển khoa học. Những hướng/ngành nghiên cứu mới có triển vọng thường phát triển từ sự giao thoa của nhiều ngành khoa học lớn đi trước nó. Trong lịch sử phát triển của trí tuệ nhân tạo nói chung và machine learning nói riêng, nhiều vị tiền bối trong ngành đã không có sự nhìn nhận xác đáng về cái gốc rễ ấy (statistics và continuous mathematics). Họ đã kỳ vọng là có thể phát triển công nghệ mới mà không cần đến những công cụ toán học đương đại (kể cả xác suất thống kê). Điều này làm cho trí tuệ nhân tạo và machine learning đi chậm lại hoặc lạc hướng vì đã bị cô lập với statistics cũng như các ngành liên quan như signal processing, information theory, operations research,… trong suốt mấy thập niên liền.

Tôi không nói điều gì thực sự mới mẻ ở đây đối với những người nghiên cứu ở cutting-edge của machine learning ngày nay, nhưng có thể là mới mẻ và hy vọng là hữu ích cho những bạn đang dự định nghiên cứu về machine learning, trí tuệ nhân tạo trong KHMT, cũng như nhiều ngành liên quan đến xử lý dữ liệu khác.

Chủ đề: Nghiên cứu nghiên kiếc & Thuật ngữ chuyên ngành & Trí tuệ nhân tạo & Xác suất & thống kê | Bình luận (14) »

Khi tôi đang học đại học ở Postech và tìm một đề tài nghiên cứu tốt nghiệp, tôi làm quen với machine learning một cách tự nhiên. Mặc dù thích cả về lý thuyết thuật toán, nhưng ngày đó machine learning nghe sexy hơn nhiều. Tưởng tượng xem, tôi học ngành máy học (hay học máy nhỉ). Những năm 90 vẫn còn đọng lại dư âm cái hype của những neural networks và genetic algorithms bắt đầu từ thập niên 80. Ôi chà, những thuật toán có cảm hứng từ sinh học. Những lãng mạn từ “2001: A space odyssey” và MIT Robotics lab của Rodney Brook… Ông thầy vung vẩy tờ bìa Tạp chí Nature với cái tít “thế kỷ của brain science“, và tất nhiên tin học sẽ luôn là xe đò trong các khoa học tự nhiên và ứng dụng. This is it! Neural networks và genetic algorithms. Có rất nhiều tạp chí và conference, thậm chí cả PhD program được tập trung vào những lĩnh vực này. Thậm chí có rất nhiều người đã cao giọng khái quát hóa NNs và GAs thành các “paradigm”, “architecture” của trí tuệ nhân tạo trong tương lai. Rất nhiều chương trình nghiên cứu, như của thầy hướng dẫn thời undergraduate của tôi, chỉ xoay vần khá chật vật quanh mô hình này.

Ngày nay, NNs và GAs không còn nằm ở trung tâm của nghiên cứu machine learning hay artificial intelligence nữa. Một cách công bằng, NNs và GAs có thể coi là những dạng mô hình học hữu ích trong nhiều áp dụng thực tế. Nhưng chúng không phải là paradigm tổng quát gì cả, mà cũng có những hạn chế như rất nhiều mô hình thống kê khác. Không có gì bí ẩn tại sao các thuật toán NNs hay GAs lại work và không work. Thế mạnh và yếu đều được hiểu một cách khá cặn kẽ từ nền tảng thống kê cổ điển và hiện đại (classical và modern statistics), lý thuyết xác suất, lý thuyết xấp xỉ, v.v.

Có lẽ đóng góp lịch sử lớn nhất của NNs và GAs là sự hấp dẫn, mới lạ và sự hiệu quả của những phương pháp này. Chúng thu hút một số lượng lớn rất nhiều các kỹ sư, các nhà khoa học thực nghiệm và tính toán, vật lý lý thuyết, … tất cả những ai phải xử lý số lượng dữ liệu lớn và nhiều chiều. Những người này đã quan tâm đến và góp phần phát triển tiếp machine learning. Họ thường không ngại ngần gì với những data sets khổng lồ. Họ cần những giải pháp computation hữu hiệu, nhưng không thích quá nhiều assumption cứng nhắc về dữ liệu. Họ thực dụng, và không bị lệ thuộc vào các mô hình thống kê cổ điển giáo điều. Họ quả cảm và năng động chứ không máy móc như các nhà thống kê cổ điển. Và cũng giống như fashion, machine learning vẫn tiếp tục sexy, nhưng cái hype không còn là NNs hay GAs mà chuyển sang các mô hình thống kê khác, như graphical models (Bayes nets), support vector machines, các mô hình nonparametric Bayes, v.v.

Đó là một câu chuyện sơ lược về machine learning. Các ứng dụng của machine learning thường thú vị và bất ngờ, hương pháp áp dụng thường là những heuristic thông minh, nhưng lại ad hoc. Để phân tích và phát triển tiếp thì machine learning phải dựa vào nền tảng vững chắc của thống kê. Nếu bạn là một sinh viên đại học hoặc bắt đầu học cao học và muốn nghiên cứu về machine learning, thì phải học xác suất thống kê cho vững. Nếu không có thể bị chóng mặt bởi một đống fashionable algorithms của nó.

Vậy về mặt tri thức, machine learning và thống kê khác nhau ở điểm gì?

Đối với tôi, không hề có sự khác biệt mà chúng là một. Có thể nói đây là vision mà tôi chia sẻ với không ít người khác. Theo tôi, cả hai ngành đều cùng phát triển và sẽ hội tụ về thành một điểm trong tương lai. Gọi nó là statistical machine learning, hoặc computational statistics gì đều được. Đóng góp của statistics có tính chất nền tảng trong việc xử lý uncertainty, xử lý noise trong dữ liệu. Đóng góp của machine learning nói riêng và KHMT nói chung là sự chú trọng đến khía cạnh thuật toán và hiệu quả tính toán.

Trước đây thống kê cổ điển không chú trọng nhiều đến khía cạnh computation này, nên các sản phẩm của họ (dưới dạng statistical tests hoặc linear estimation procedures) thường có tính chất về computation rất đơn giản. Do đó chúng chỉ áp dụng được cho các data set rất nhỏ, mặc dù chúng có hiệu quả thống kê rất tốt về mặt lý thuyết; hoặc nếu data set lớn thì chỉ hữu ích khi chúng tuân thủ theo các assumption rất khắc nghiệt. Nhưng sự phát triển không ngừng của KHMT và những thành công của machine learning là cho các nhà thống kê học giật mình, và họ bắt đầu giang rộng vòng tay đón nhận machine learning như một lĩnh vực tiên phong trong statistics, sẵn sàng đón nhận những thách thức về computation bên cạnh độ hiệu quả về thống kê.

Quả thực sự phát triển của machine learning như thổi một luồng gió mới vào chính ngành statistics, làm cho nó sexy hơn. Một mặt khác, nhưng người làm về machine learning cũng cảm thấy cần thiết phải quay lại với những nền tảng của statistics để hiểu và gọt rũa các phương pháp heuristic của họ một cách hoàn chỉnh, và bớt đi phần ad hoc hơn.

Rồi bạn sẽ thấy ngày càng ít những phát biểu kiểu như: “My approach is neural network based, not a statistical one“. Trái lại bạn sẽ nghe thấy các nhà thống kê học nói nhiều hơn đến “algorithms” và “data structure”, còn dân KHMT sẽ nói nhiều đến “statistical analysis”. Bạn nào học machine learning khi trả lời phỏng vấn visa ở lãnh sự quán Mỹ, muốn tránh phiền phức với các chuyên ngành nhạy cảm (như AI, machine learning, vision, robotics,…) có thể thật thà theo giải pháp của tôi: nghiên cứu về statistical computer science Nói với tay lãnh sự rằng, it’s fun, it’s sexy, but not at all sensitive

Chủ đề: Nghiên cứu nghiên kiếc & Thuật ngữ chuyên ngành & Trí tuệ nhân tạo & Xác suất & thống kê | Bình luận (13) »

Tôi muốn giới thiệu một bài báo thú vị của David Donoho với tựa đề: The blessings and curses of dimensionality. Donoho là một siêu sao trong ngành thống kê của thập niên 90, ông cũng là một cây viết thú vị. Các bài viết của Donoho dù technical hay không, thường tạo ra nhiều cảm hứng và nhiệt tình cho người đọc. Bài báo trên của Donoho là một lời kêu gọi sự chú ý của giới làm toán nói chung hãy quan tâm hơn và đóng góp các công cụ toán học đến những vấn đề xử lý dữ liệu hóc búa của thế kỷ 21. Đọc nó, và hy vọng bạn sẽ thấy đó cũng là lời kêu gọi đến những nhà khoa học máy tính của hôm nay và ngày mai.

Những vấn đề xử lý dữ liệu không hề xa lạ với dân KHMT chúng ta. Quả thật đó cũng chính là nồi cơm của chúng ta: Làm thế nào để “make sense of” luồng dữ liệu khổng lồ trên web, trong hệ thống máy, trong các sensor networks, trong genome của người và các sinh vật khác, các loại dữ liệu ở dạng text, ảnh, âm thanh, v.v. Làm thế nào để máy tính được grounded trong data mà không bị chết sặc. Những tiến bộ trong công nghệ thông tin — communication, networking, hardware, software, data structure và algorithms — đã tạo nên một cơ sở hạ tầng tuyệt vời để thu thập và biểu hiện dữ liệu. Song chưa đủ. Xử lý luồng dữ liệu khổng lồ như thế nào lại là một chuyện phức tạp hơn nhiều. Ở thế kỷ 21, rất nhiều ngành khoa học lý thuyết, tính toán và thực nghiệm phải cùng nhau xắn tay vào để giải quyết những vấn đề như vậy.

Dân KHMT cũng không lạ gì khái niệm “curses of dimensionality” do Richard Bellman sử dụng lần đầu tiên. Curses of dimensionality nói đến sự khó khăn trong việc giải quyết các bài toán liên quan đến high dimension. Một cách cụ thể, số lượng dimension của bài toán có thể là số lượng biến số liên quan, có thể do số lượng sensors dùng để thu thập data rất lớn. Tùy theo dạng dữ liệu khác nhau mà sensors ở đây cũng nên hiểu theo nghĩa rất linh động, có thể là các routers trong một network, các cameras, các websites, các pixels của từng hình ảnh, độ dài của chuỗi DNA và protein trong sinh học phân tử, v.v. Để xử lý data với dimension khổng lồ như trên với số lượng khổng lồ đòi hỏi tìm kiếm trong một state space lớn gấp nhiều lần, có thể theo đa thức hoặc hàm số mũ (exponential). Đó chính là curses of dimensionality. Đừng vội nghĩ exponential complexity mới là tồi tệ. Nếu thuật toán của bạn scan database lần, với số dimension ở mức hàng chục triệu thì đã khó chấp nhận rồi.

Điều thú vị là high-dimension có nhiều blessings. Bạn hãy tự hỏi, tại sao con người ta luôn luôn phải đối mặt với rất nhiều sensory data (qua 7 giác quan) mà thường vẫn không bị tẩu hỏa nhập ma. Tất nhiên đây là một câu hỏi mở để ta cùng suy ngẫm. Trong toán học, một trong những yếu tố thuận lợi của high dimensions chính là khái niệm concentration of measure. Trong lý thuyết xác suất chúng ta đều biết law of large numbers: giá trị trung bình của các sự thể hiện ngẫu nhiên thường hội tụ về giá trị kỳ vọng của biến ngẫu nhiên (constant). Hay định luật central limit: Giá trị trung bình của các sự thể hiện ngẫu nhiên có hành vi giống như biến Gauss. Sâu hơn một chút, một hàm số được định nghĩa trên rất nhiều biến (high dimension), mà sự đóng góp của từng biến vào giá trị hàm số đều nhỏ, thì hàm số đó có hành vi giống như constant vậy. Kỳ thực rất nhiều hàm số mà chúng ta quan tâm trong cuộc sống đều có tính chất này. Trong hình học lồi (convex geometry), rất nhiều vật thể lồi trong high dimension thường có những tính chất phản trực quan: ví dụ một hình hộp trong không gian nhiều chiều có hình dạng rất khác một hình hộp ta biết trong 2 hay 3 chiều. Song những tính chất đó lại được tận dụng một cách hiệu quả để đưa ra những đáp án rất ngoạn mục cho các vấn đề liên quan đến high dimension.
[[Addition 04/03/07: Một quyển sách rất hay và dễ đọc giới thiệu về v/đ này: Keith Ball, Elementary introduction to convex geometry, ở đây .]]
Donoho còn liệt kê ra và dẫn chứng một số yếu tố blessings khác trong không gian nhiều chiều. Để có nó ta cần phải sử dụng các công cụ khác trong toán học.

Đây là một ví dụ của những bài báo mà khi đọc xong, tôi không khỏi cảm thấy mình thật là may mắn vì được sống trong một không gian rất nhiều chiều. Không phải vì mình đã nắm hết được hết các blessings kể trên, mà vì khả năng được tìm tòi và sử dụng các công cụ toán học đẹp đó để giải quyết các vấn đề rất thiết thực. Bring it on, your curses, dear Professor Bellman!

Chủ đề: Giới thiệu sách & Lý thuyết thông tin & Lý thuyết tính toán & Thuật Toán & Toán tối ưu & Trí tuệ nhân tạo & Xác suất & thống kê | Bình luận (2) »

Láng giềng

Giếng làng
Ai thả bùa yêu
Sông quê ai thả câu Kiều
Không trôi

Thương nhau
Cau sáu bửa đôi
Trầu têm cánh phượng
Thắm môi láng giềng
Tôi về
Cưới mắt chim quyên
Cưới em
Sính lễ một thuyền hoa xoan
Trăm tiền
đổi được mấy quan
Tôi đem mua lấy
môi ngoan em cười

Xem thêm ở đây

Chủ đề: Chưa phân loại | Bình luận »

Báo cáo mới từ viện Brookings (một thinktank ở DC) có tựa đề: The Implications of Service Offshoring for Metropolitan Economies. Kết luận nói chung cũng không khác mấy so với các báo cáo trước tôi đã post; tuy nhiên dữ liệu mới hơn một chút.

Chủ đề: CNTT các nước và VN | Bình luận »

Theo bài ở Boston Globe

In fact, educated women nationwide now have a better chance of marrying, especially at an older age, than other women. In a historic reversal of past trends … ONE REASON EDUCATED WOMEN are more likely to marry today than in the past is that modern men are less threatened by equality and more interested in finding a mate who can share the burdens of breadwinning … Furthermore, college-educated couples have lower divorce rates than any other educational group. And in the last 30 years, while the marriages of less-educated women became less stable, the marriages of college-educated women became more stable.

Cái đó chưa hay, cái này mới hay

So the doomsayers are wrong. Educated men and women are more likely to marry and less likely to divorce than others . And guess what? They have better sex lives, too. According to sociologist Virginia Rutter of Framingham State College, surveys show that educated couples engage in more variety in their sex lives. They are, for example, more likely to participate in oral sex, and educated women are more likely to receive oral sex as well as perform it. “Education breaks down gender taboos that can be at the heart of a lot of sexual disappointments,” notes Rutter, “and education helps men in particular to loosen up sexually.” Educated husbands are also more likely to help with housework, which turns out to be a potent aphrodisiac. Psychologist John Gottman, professor emeritus at the University of Washington in Seattle, found that when men do more housework, their wives are more likely to be “in the mood” for sex.

Chủ đề: Nghiên cứu nghiên kiếc | Bình luận (1) »

• Mary Poovey viết về các “chiêu” tài chính kế toán trên Notices
• Richard Layard có một chuỗi ba bài giảng về hạnh phúc từ góc nhìn kinh tế/xã hội.
• Một vài chi tiết lịch sử về Backus Normal Form (thường bị gọi sai là Backus Naur Form)
• Chuỗi các bài giảng của Lyle Zynda về triết lý của khoa học
• Một website về vấn đề triết học kinh điển: determinism vs. free will

Chủ đề: Trang web hay | Bình luận »

(Nguồn: http://xkcd.com/c184.html.)

Chủ đề: Vui - Giải Trí | Bình luận »

73. Ta có n mẫu máu. Mỗi mẫu máu thuộc về một trong m nhóm máu. (Ta không biết chính xác m là bao nhiêu, và m không nhất thiết phải là hằng số.) Có một thiết bị mà nếu bỏ vào đó hai giọt máu từ hai mẫu máu khác nhau thì thiết bị sẽ cho biết hai mẫu máu có cùng nhóm máu hay không. Nếu bỏ vào thiết bị này hơn hai giọt máu thì câu trả lời không đáng tin cậy nữa.

    Ta muốn trả lời câu hỏi sau đây: có hay không hơn n/2 mẫu máu thuộc về cùng một nhóm máu. Dùng thiết bị trên để thử, làm thế nào để trả lời câu hỏi này với tổng số ít nhất các phép thử? (Chỉ cần ít nhất về mặt asymptotic là được.) Ví dụ: cách dễ nhất là thử tất cả các cặp mẫu máu nhưng như vậy cần dùng đến phép thử.

    Ngoài ra, ta cũng giả sử rằng mỗi mẫu máu có khá nhiều giọt.

Chủ đề: Dành cho du học sinh & Vui - Giải Trí | Bình luận (6) »