Best local search method?

**haichit.** · #1 (**permalink**) 09-28-2009

Tớ đang tìm phương pháp local optimization hiệu quả nhất, tìm các paper + wiki thì ai cũng khen phuơng pháp của mình nên chả biết đâu mà lần. Đây là vài tính chất của function của tớ: high cost (10-20s/evaluation), 19 parameters, không tính đựoc đạo hàm, chả biết là smooth hay non-smooth nữa. Mục đích của tớ là tìm global minimum và dùng GA để search initial guess cho local search. Bây giờ tìm mấy phương pháp lòi cả mắt ra mà chả cái nào ưng ý. Tớ thử qua Nelder-Mead hay subplex method, nhưng mà vẫn tốn nhiều function evaluations quá mà kết quả không được như mỹ mãn. Các cao nhân Math cho ý kiến hộ tớ với. :X.

**Tartan** · #2 (**permalink**) 09-29-2009

Anh nghĩ em có thể thử 2 cách

1. Grid search: cách ngu nhất nhưng dễ thực hiện nhất là thử các tổ hợp của 19 giá trị. Cách này trâu bò nhưng nếu có nhiều cpus + tốc độ chạy mỗi thí nghiệm ngắn thì có thể thử rất nhanh.

2. Simulated Annealing: cái này nguồn gốc từ bên vật lí thực nghiệm, có nhiều tài liệu về trò này.
Có vài cái source code để tham khảo

C#:
[Only registered and activated users can see links. ]

Perl: Machine Learning package
[Only registered and activated users can see links. ]

	Trích:	haichit
	Tớ đang tìm phương pháp local optimization hiệu quả nhất, tìm các paper + wiki thì ai cũng khen phuơng pháp của mình nên chả biết đâu mà lần. Đây là vài tính chất của function của tớ: high cost (10-20s/evaluation), 19 parameters, không tính đựoc đạo hàm, chả biết là smooth hay non-smooth nữa. Mục đích của tớ là tìm global minimum và dùng GA để search initial guess cho local search. Bây giờ tìm mấy phương pháp lòi cả mắt ra mà chả cái nào ưng ý. Tớ thử qua Nelder-Mead hay subplex method, nhưng mà vẫn tốn nhiều function evaluations quá mà kết quả không được như mỹ mãn. Các cao nhân Math cho ý kiến hộ tớ với. :X.

~~goahead~~ · #3 (**permalink**) 09-29-2009

Và đây là sách về SA, haichit tìm được thì cho tớ xin luôn

Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing Wiley::Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing

**haichit.** · #4 (**permalink**) 09-29-2009

	Trích:	Tartan
	Anh nghĩ em có thể thử 2 cách 1. Grid search: cách ngu nhất nhưng dễ thực hiện nhất là thử các tổ hợp của 19 giá trị. Cách này trâu bò nhưng nếu có nhiều cpus + tốc độ chạy mỗi thí nghiệm ngắn thì có thể thử rất nhanh. 2. Simulated Annealing: cái này nguồn gốc từ bên vật lí thực nghiệm, có nhiều tài liệu về trò này. Có vài cái source code để tham khảo C#: [Only registered and activated users can see links. ] Perl: Machine Learning package [Only registered and activated users can see links. ]

@Tartan: Mất tầm 4-10s để tính function của em, nếu như chạy ở cluster trong lab thì cần tầm 10-20s (chậm hơn máy desktop

). Nghĩa là nếu để tính 1 triệu phép tính thì cần tầm 2 tháng cơ ạ. :, vì vậy nếu dùng grid search thì có vẻ không ổn. Em đang dùng Genetic Algorithm vì em tìm được parallel code nên cũng tiết kiệm được kha khá thời gian, có thể dùng 100 cpus một lúc cho population size 100.
[Only registered and activated users can see links. ]

Mà lab em đang dùng Fortran 90 nên tất cả các module em dùng đều viết bằng Fortran, bây giờ viết lại (hoặc covert) sang C thì chít

. (cái chính là em rất gà về C/C++

)

Em cũng ngó qua SA nhưng nó có vài điểm yếu là các thông số quá nhiều nên mất thời gian đọc nhiều tài liệu. Em cũng ngó qua benchmark của SA so với mấy phưong pháp khác như GA hay Differential Evolution ... thì thấy SA không bằng, số function phải tính vẫn khá nhiều.

Nên strategy bây giờ của em là dùng GA để lấy initial guess cho một số phương pháp tìm local minimum để refine kết quả.

.

Vừa đọc mấy cái paper về Powell method và benchmark của nó thì thấy phương pháp này cũng tốn ít thời gian thật. [Only registered and activated users can see links. ]

Không biết có cái khác hay hơn không?

. Hì, em chỉ hỏi về phương pháp thôi, còn code hay paper thì em search được. Thanks các bác nhiều.

@Go: hì, chịu khó đọc paper đi, đọc sách thì bao giờ mới hết

<-- tớ không tìm được

**Tartan** · #5 (**permalink**) 09-29-2009

Giả sử có 50 cpus

(20s * 1,000,000)/50 cpus ~ 4.6 days

Cho 1M phép tính với grid search

	Trích:	haichit
	@Tartan: Mất tầm 4-10s để tính function của em, nếu như chạy ở cluster trong lab thì cần tầm 10-20s (chậm hơn máy desktop ). Nghĩa là nếu để tính 1 triệu phép tính thì cần tầm 2 tháng cơ ạ.

**haichit.** · #6 (**permalink**) 09-29-2009

Hì, nếu tổ hợp thì nó sẽ ra thế này: tính một cách đơn giản là 'quét' 20 giá trị cho một biến, tính sơ sơ cũng mất 20^19 functions.

. Tổng cộng mất 110833756130559 của một nghìn năm cơ ạ.

, nghĩa là đời con cháu, chắt, chít .... nữa

**Tartan** · #7 (**permalink**) 09-29-2009

Tất nhiên cách này là ngu nhất rồi.

Có 1 tip để chạy grid search nhanh hơn 1 chút là chạy 2 bước.

Bước 1: chạy với ít tổ hợp thôi ví du chỉ (2^19) /20s/50cpus ~ 9 phút

Bước 2: chọn tổ hợp có giá trị cao nhất, fix 1 số biến ví dụ 11 biến, sau đó làm lại
(10^8) /20s /50cpus ~ 1.2 ngày

	Trích:	haichit
	Hì, nếu tổ hợp thì nó sẽ ra thế này: tính một cách đơn giản là 'quét' 20 giá trị cho một biến, tính sơ sơ cũng mất 20^19 functions. . Tổng cộng mất 110833756130559 của một nghìn năm cơ ạ. , nghĩa là đời con cháu, chắt, chít .... nữa

**haichit.** · #8 (**permalink**) 10-01-2009

Paper này so sánh một vài global optimization methods trong đó có GA và SA. SA làm việc rất kém với nhiều biến.

Mongeau, M.; Karsenty, H.; Rouz, V.; Hiriart-Urruty, J.-B., Comparison of public-domain software for black box global optimization. Optimization Methods and Software 13 (2000), 203-226.

[Only registered and activated users can see links. ]

Gas: GA method
Asa: SA method

**Tartan** · #9 (**permalink**) 10-01-2009

Nói chung mấy cái so sánh kiểu này phụ thuộc vào từng bài toán và chuyên ngành cụ thể.

Nếu em muốn optimize nhiều parameters thì thử search trong ngành em có ai test các pp tối ưu chưa kết quả của họ ra sao.

Bên ngành anh thì đơn giản nhất cũng phải optimized khoảng 15 tham số cho mỗi một hệ thống. Có một số pp để tối ưu nhưng phổ biến có 2 cái

- MERT - Minimum Error Rate Training: cái này chạy tương đối tốt và nhanh khi hệ thống có ít hơn 50 tham số. Lần đầu tiên xuất hiện trong ngành vào năm 2003.

- MIRA - Margin Infused Relaxed Algorithm: cái này đầu tiên từ bên machine learning khoảng 3 năm trước; giới thiệu vào ngành anh trong khoảng 1 năm gần đây. MIRA có thể tối ưu cực nhiều tham số. Bài báo "11001 New Features for Statistical Machine Translation" chứng minh MIRA works vơi 11,001 tham số đã giật giải Best-Paper Award năm nay của HLT-NAACL. Các tác giả đang tập trung cải tiến để có thể tối ưu đến cả triệu tham số.

	Trích:	haichit
	Paper này so sánh một vài global optimization methods trong đó có GA và SA. SA làm việc rất kém với nhiều biến. Mongeau, M.; Karsenty, H.; Rouz, V.; Hiriart-Urruty, J.-B., Comparison of public-domain software for black box global optimization. Optimization Methods and Software 13 (2000), 203-226. [Only registered and activated users can see links. ] Gas: GA method Asa: SA method

**haichit.** · #10 (**permalink**) 10-01-2009

Vâng, trong project em đang làm thì các cụ hay dùng Nelder-Mead hoặc GA method để tìm. Các cụ chạy 100 lần với initial guess khác nhau và pick result mà các cụ ưng ý nhất --> Các cụ không care lắm đến global minimum. Nhưng mà cụ của em (advisor) muốn test xem là cái model của các cụ đang làm có limitation là do bản chất của phương pháp hay là do các cụ chưa optimize cẩn thận

. Em cũng không cần phải lấy global minimum nhưng phải cho cụ nhà em biết là tao chỉ làm được đến thế thì các phương pháp opitmization hiện nay cũng chỉ đến thế ....

(j/k).

So sánh các methods khác nhau cũng hơi bị subjective vì mỗi bài toán cần những user-supplied parameters cụ thể nên cái này cũng phải search literature nhiều.

Em sẽ thử hai phương pháp mà bác chọn (nhờ bác mà em mới biết đến nó, chứ không thì toàn biết đến GA, SA hay Pswarm, ...). Hi vọng là có fortran code để em thử

.