Nguồn gốc cụm từ dynamic programming
Ngô Quang Hưng | 14 tháng 02, 2007 | 
Bản để in
Cha đẻ của kỹ thuật dynamic prorgramming (quy hoạch động) là Richard Bellman. Hồi đầu những năm 50, Bellman làm tư vấn cho RAND Corp, một trong những think tank có ảnh hưởng cực lớn của quân đội Mỹ. (Lý thuyết game, quy hoạch tuyến tính, và nhiều nhánh khác của toán học, kinh tế học hiện đại có phần gốc gác từ RAND.) Hồi đó Bellman đang nghiên cứu về planning, multistage decision process, … và ông khám ra kỹ thuật quy hoạch động. Tuy nhiên, hồi đó bộ trưởng bộ quốc phòng Mỹ là Charles Wilson rất ghét cụm từ “nghiên cứu”, đặc biệt là “nghiên cứu toán học”. Wilson vốn là một kỹ sư giỏi, nhưng sau đó đi làm business (salesman), lên đến tổng giám đốc của General Motors. Trong quyển tiểu sử tự thuật của mình, Bellman giải thích tại sao ông chọn tên “dynamic programming” như sau:
I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. “An interesting question is, ‘Where did the name, dynamic programming, came from?’ The 1950s were not good years for mathematical research. We had a very interesting gentlemen in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying–I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressmann could object to. So I used it as an umbrella for my activities
(Xem thêm bài viết này có nhiều trích đoạn hay từ hồi ký của Bellman.) Đọc đoạn này tôi chợt nhớ đến vụ toán học vô dụng vì nếu Bellman không che giấu cái “nghiên cứu toán học” của ông bằng cái tên khó hiểu, thì đã không có tiền để phát triển một ý tưởng mà ngày nay được dùng rộng rãi trong computational biology, operation research, control theory, … chưa kể ít nhất một nửa cái Internet ta dùng hàng ngày đang chạy Distance Vector protocol theo thuật toán Bellman-Ford, một thuật toán quy hoạch động.
Mình đọc được bài này mình thấy rất vui, mình đang rất muốn tìm hiểu về “Nguồn gốc của ngôn ngữ máy tính” tương tự như bài viết trên về sự ra đời của các từ trong máy tình. Vì dù sao máy tính mãi sau này mới ra đời nên theo mình biết thì mọi từ trong máy tính đều bắt nguồn từ cuộc sống. Vậy bạn nào có tài liệu liên quan đến vấn đề trên thì share cho mình mới nhé.
Mail của mình là: manguonmo82@gmail.com
Y!M: ma_nguon_mo82
Thanks a lot
Hôm nay mình đang ngồi so sánh giữa Calculus of Variations (CV) và Dynamic Programming (DP) thì lại nhớ đến bài viết của bác Hưng. Không có gì nghi ngờ Dynamic Programming đã và đang được sử dụng rộng rãi. Tuy nhiên, from my viewpoint thì so với V, DP không thật sự là a more systematic methodological approach như Richard Bellman nghĩ. So sánh này có thể khập khiễng, nhưng in some sense, nếu CV giống như việc tính đạo hàm và sau đó giải hàm bằng 0 thì DP lại giống kiểu Hill Climbing.
Trong review về cuốn “Calculus of Variations and Dynamic Programming” của Stuart Dreyfus, tác giả của “bài viết này”, Zangwill nói rằng “The last chapter, Chapter 7, is actually somewhat distinct from the rest of the book. In this chapter stochastic and adaptive optimization problems are discussed. It is perhaps in these areas that dynamic programming truly comes to its own. While the calculus of variations and optimal control theory can be developed from other viewpoints, it is dynamic programming which provides a main attack on stochastic and adaptive problems.”
Hiện giờ em không có cuốn sách này at hand nên không hiểu tại sao dynamic programming lại more favorable in stochastic control problems. Bác Hưng có thể giải thích tại sao không?
“tại sao dynamic programming lại more favorable in stochastic control problems”
Theo mình thì trong các bài toàn mô hình liên quan đến xác suất thì vấn đề thường phải giải quyết là tìm được một optimized solution cho bài toán. Vì bài toán được mô hình bởi các trạng thái xác suất và không gian tìm kiếm lời giải thường rất lớn, do đó 1 lời giải có tính DP rất được ưa chuộng. Nếu nhìn đơn giản thì các mô hình cuối cùng cũng trở lại như một kiểu đồ thị có trọng số. Một trong những ví dụ kinh điển của các mô hình xác suất là Hidden Markov Models (HMMs) với Viterbi algorithm là lời giải cho bài toán tìm kiếm tối ưu. Những mở rộng gần đây của HMMs như Maximum Entropy Markov Models (MEMM), Conditional Random Fields (CRF) đều inference algorithm dưới dạng Viterbi-style. Cái khó nhất mình nghĩ vẫn là nghĩ ra model với lại derive được inference algorithm.
@dongta: Theo tôi hiểu thì bạn đã giải thích rồi đấy … DP formulate vấn đề trên discrete (discretized) state space. Do đó các giải thuật iterative được hình thành một cách tự nhiên. Còn với continuous state space thì thường ta quy vấn đề về stochastic PDE và cuối cùng đối đầu với bài toán calculus of variation — tuy có structure rõ ràng hơn nhưng solution vẫn thường intractable. Vì vậy những gì tôi biết về lĩnh vực này (chút ít) thì DP đuợc chuộng hơn do sự phát triển của CNTT.
Có nhiều vấn đề dù là trên discrete space nhưng để hiểu structure của solution người ta vẫn phải nghiên cứu asymptotics của chúng, khi đó lại chính là solution của một vấn đề CV. Một ví dụ là trong sequential testing/detection với discrete time. Trong tình huống như vậy, hai cách nhìn đều thông dụng — một cái algorithmic (thực dụng), một cái asymptotic (lý thuyết).