2010-06-29 19 views
6

Tôi muốn tối đa hóa hàm với một tham số. Vì vậy, tôi chạy gradient descent (hoặc, thực tế): Tôi bắt đầu với tham số ban đầu và tiếp tục thêm gradient (lần một số yếu tố tỷ lệ học tập nhỏ hơn và nhỏ hơn), đánh giá lại gradient cho tham số mới, và cứ thế cho đến khi hội tụ.Làm thế nào để chạy thuật toán gốc dốc khi tham số không gian bị hạn chế?

Nhưng có một vấn đề: Thông số của tôi phải giữ nguyên là, vì vậy nó không được coi là < = 0 vì chức năng của tôi sẽ không được xác định. Tìm kiếm gradient của tôi đôi khi sẽ đi vào các khu vực như vậy mặc dù (khi nó là tích cực, gradient nói với nó để đi một chút thấp hơn, và nó vượt qua).

Và để làm mọi thứ tồi tệ hơn, độ dốc tại điểm như vậy có thể là số âm, dẫn hướng tìm kiếm tới nhiều giá trị thông số âm hơn. (Lý do là hàm mục tiêu chứa nhật ký, nhưng gradient không.)

Một số thuật toán tốt (đơn giản) nào xử lý vấn đề tối ưu hóa hạn chế này là gì? Tôi hy vọng chỉ là một sửa chữa đơn giản cho thuật toán của tôi. Hoặc có lẽ bỏ qua gradient và làm một số loại tìm kiếm dòng cho các tham số tối ưu?

Trả lời

3

Nếu không biết thêm về sự cố của bạn, thật khó để đưa ra lời khuyên cụ thể. Thuật toán tăng dần độ dốc của bạn có thể không đặc biệt phù hợp với không gian chức năng của bạn. Tuy nhiên, cho rằng đó là những gì bạn đã có, đây là một tinh chỉnh sẽ giúp đỡ.

Bạn đang theo dõi những gì bạn tin là một gradient tăng dần. Nhưng khi bạn di chuyển về phía trước theo hướng của gradient, bạn phát hiện ra bạn đã rơi vào một hố có giá trị âm. Điều này ngụ ý rằng có một địa phương tối đa gần đó, nhưng cũng là một vách đá dốc âm rất sắc nét. Sửa chữa rõ ràng là quay lại vị trí trước đó của bạn và thực hiện một bước nhỏ hơn (ví dụ: một nửa kích thước). Nếu bạn vẫn rơi vào, hãy lặp lại với một bước nhỏ hơn. Điều này sẽ lặp lại cho đến khi bạn tìm thấy tối đa địa phương ở rìa của vách đá.

Vấn đề là, không có gì đảm bảo rằng tối đa địa phương của bạn thực sự là toàn cầu (trừ khi bạn biết nhiều hơn về chức năng của mình hơn là bạn đang chia sẻ). Đây là giới hạn chính của sự dốc lên ngây thơ ngây thơ - nó luôn luôn sửa chữa tối đa địa phương đầu tiên và hội tụ với nó. Nếu bạn không muốn chuyển sang thuật toán mạnh mẽ hơn, một cách tiếp cận đơn giản có thể giúp bạn chạy các mã lặp lại n, bắt đầu mỗi lần từ vị trí ngẫu nhiên trong không gian chức năng và giữ tối đa . Cách tiếp cận Monte Carlo này làm tăng tỷ lệ cược mà bạn sẽ vấp ngã trên mức tối đa toàn cầu, với chi phí tăng thời gian chạy của bạn theo hệ số n. Làm thế nào có hiệu quả này sẽ phụ thuộc vào 'bumpiness' của chức năng mục tiêu của bạn.

2

Một thủ thuật đơn giản để hạn chế tham số là dương là để tái xác định vấn đề về mặt logarit của nó (đảm bảo thay đổi độ dốc thích hợp). Tất nhiên, có khả năng di chuyển tối ưu tới -infty với phép biến đổi này, và tìm kiếm không hội tụ.

8
  1. Mỗi khi bạn cập nhật thông số của mình, hãy kiểm tra xem thông số đó có âm hay không và nếu đúng, hãy kẹp thành 0.
  2. Nếu không thể chấp nhận kẹp bằng không, hãy thử thêm "rào cản đăng nhập" (Google nó). Về cơ bản, nó thêm một bức tường "mềm" mịn vào chức năng mục tiêu của bạn (và sửa đổi gradient của bạn) để giữ nó khỏi các vùng bạn không muốn nó đi đến. Sau đó bạn liên tục chạy tối ưu hóa bằng cách làm cứng tường để làm cho nó trở nên vô cùng thẳng đứng hơn, nhưng bắt đầu bằng giải pháp đã tìm thấy trước đó.Trong giới hạn (trong thực tế chỉ cần một vài lần lặp), vấn đề bạn đang giải quyết giống với vấn đề ban đầu với một ràng buộc cứng.
+0

+1 đối với phương thức phạt hình sự –

2

Ở mỗi bước, hạn chế tham số là dương. Đây là (viết tắt) phương pháp gradient được chiếu bạn có thể muốn google.

2

Tôi có ba đề xuất, theo thứ tự suy nghĩ và công việc bạn muốn làm.

Đầu tiên, với độ dốc/độ dốc, bạn di chuyển mỗi lần theo thời gian gradient một số yếu tố mà bạn gọi là "yếu tố tỷ lệ học tập". Nếu, như bạn mô tả, động thái này làm cho x trở thành tiêu cực, có hai cách diễn giải tự nhiên: Hoặc độ dốc quá lớn hoặc hệ số tốc độ học tập quá lớn. Vì bạn không thể điều khiển gradient, hãy giải thích thứ hai. Kiểm tra xem di chuyển của bạn có làm cho x trở thành tiêu cực hay không và nếu có, hãy cắt giảm hệ số tỷ lệ học tập xuống một nửa và thử lại.

Thứ hai, để xây dựng dựa trên câu trả lời của Aniko, hãy x là thông số của bạn và f (x) là hàm của bạn. Sau đó xác định một hàm mới g (x) = f (e^x), và lưu ý rằng mặc dù miền của f là (0, vô cùng), miền g là (-infinity, vô cùng). Vì vậy, g không thể bị các vấn đề mà f bị. Sử dụng độ dốc gốc để tìm giá trị x_0 tối đa hóa g. Sau đó, e^(x_0), là số dương, tối đa f. Để áp dụng gradient descent trên g, bạn cần đạo hàm của nó, đó là f '(e^x) * e^x, theo quy tắc chuỗi.

Thứ ba, có vẻ như bạn đang cố gắng tối đa hóa chỉ một hàm, chứ không phải viết thường xuyên tối đa chung. Bạn có thể xem xét việc đặt gốc dốc xuống và điều chỉnh phương pháp tối ưu hóa cho các đặc điểm riêng của chức năng cụ thể của bạn. Chúng ta sẽ phải biết nhiều hơn về hành vi mong đợi của f để giúp bạn làm điều đó.

0

Bạn nhận được câu trả lời hay tại đây. Reparameterizing là những gì tôi muốn giới thiệu. Ngoài ra, bạn đã xem xét một phương pháp tìm kiếm khác, chẳng hạn như Metropolis-Hastings? Nó thực sự khá đơn giản một khi bạn bò qua các toán học đáng sợ, và nó cung cấp cho bạn các lỗi tiêu chuẩn cũng như một tối ưu.

+0

hastings đô thị là ánh sáng xa vấn đề ban đầu. –

+0

@Alexandre: Câu đầu tiên cho biết mục tiêu là tối đa hóa một hàm. MH có thể dễ dàng bị ràng buộc để tránh một khu vực bị cấm bằng cách hạn chế phân phối đề xuất. Gradients có thể ồn ào và có vấn đề, đặc biệt nếu chúng được tính toán bởi sự khác biệt hữu hạn hoặc nếu hàm gần như bằng phẳng. –

+0

Phương pháp MCMC (và các phương pháp gradient ngẫu nhiên liên quan) được sử dụng trong trường hợp mọi thứ khác không thành công. Không có dấu hiệu cho thấy các vấn đề ban đầu cần sự hội tụ kém của các phương pháp không xác định. –

1

Chỉ cần sử dụng Brent's method for minimization. Nó là ổn định và nhanh chóng và điều phải làm nếu bạn chỉ có một tham số. Đó là chức năng của Roptimize. Liên kết cũng chứa một triển khai C++ đơn giản. Và có, bạn có thể cung cấp cho nó giới hạn giá trị tham số MIN và MAX.

Các vấn đề liên quan