Decision-Focused Learning: Foundations, State of the Art,Benchmark and Future Opportunities 리뷰 1 (DFL 개론)

https://arxiv.org/abs/2307.13565

Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities

 

Decision-Focused Learning에 관한 연구들에 관한 비교와 함께 가볍게 흐름을 잡아보려고 한다. 

Decision Focused Learning

 

실제 문제들은 불확실성 기반에서 의사결정(qunatitvaley modeled using constrained optimization)을 하는 경우가 많다. 간단히 Portforlio optimization의 경우를 생각해보자. 이전에 진행했던 Markowitz model을 이용한 포트폴리오 최적화 의 경우에서를 볼때 1) 수익률과 volatility를 예측하고 2) 포트폴리오 최적화를 진행하는 2-stage 방법으로 프로젝트를 진행하였다. 이런 방법들을 Predict-Then-Optimize 라고 말한다. 

Predicte Then Optimize는 결국 uncertain parameter를 예측하는 것을 우선하고, 이후 constrained optimization 문제를 푸는 방법으로 구성된다. 하지만 이 방법은 두개의 stage가 분리되어있고, 또 독립적으로 운영된다는 점에서 의문이 제기되어 왔다. 해당 방법론의 가정은 더 나은 예측이 정확한 예측 모델로 이어지기에 고품질의 Decision making이 가능하다는 것이다. 하지만 ML모델은 종종 완벽히 정확성을 가지는 예측값을 제시하지 못할 수 있으며 이에 따라 Suboptimal한 결정이 이루어질 수 있다. 그럼으로 이상적으로는 두 모델이 결합된 형태가 필요하다. 

 

Decision Focused learning(DFL)은 ML 모델이 좋은 의사결정을 내릴 수 있는 예측을 수행하도록 설계하는 것을 목표로 한다. 이는 Optimization과 Prediction이 end-to-end로 이어지는 시스템, 모델을 말한다. 

결국 DFL에서는 loss function을 설계할 때 최적화 문제과 연관되게 설계하는 넋이 중요하며, optmization solver가 ML 모델의 일부에 포함됨을 말한다, 이럴 경우 가장 큰 문제는 최적화 문제에서 differntiating을 어떻게 할 것인가이다. 추가적으로 Discerete variable에 관해서는 연속적이지 않기에 gradient-based learning을 어떻게 설계할 것인가의 문제가 있으며, 이에 따른 매끄러운 대체모델을 찾고 이에 대해 gradient-based learning을 진해앟는 것이 중요할 것이다. 

 

paper에서는 Gradient based 방법론과 그 외를 구분하며, 이 중 gradient based DFL에 관해 더 다룬다. 

section 2에서는 문제의 concept과 Challenge에 관해 자세히 다루고, Section 3에서는 다양한 DFL 방법론들에 관하여 다룬다. Section 4에서는 Real world problem에 적용되는 사례, Section 5에서는 7개의 DFL benchmark task에 관한 모델 비교를 Public dataset에 관해 진행한다. 

가능하면 성능 평가 기준이 무엇인지와 Section 3의 방법론들의 관점 차이를 위주로 간단히 정리하고, 
각 방법론 중 흥미로운 방법론들을 위주로 다른 글을 통해 정리해보려한다. 

 

Problem setting

Constrained optimization 문제는 간단히 아래와 같이 정의된다. 이때 c는 정확하게 정의되지 않은 불확실한 매개변수라고 하자. 

optimization form

이 기본형식에서 식의 형태와 변수의 형태에 따라 LP, IP, NLP 등 다양한 형태로 문제가 정의되며 이에 따른 optmization solver도 다르다. 만일 c가 알려져있다면, 이를 full information optimal decisions라고 한다. c가 알려져있지 않을 때 관측된 z를 이용하여 supervised ML을 통해 c를 예측할 수 있다. 이 경우 Prescriptive decision이라고 하며 이 경우 Predict then optimize 방법이 적용된다. 

다만, 이 방법의 문제는 model(c를 예측하기 위한)은 일반적으로 loss로 mse나 cross entropy를 사용하는데 이는 ground truth c를 예측하기 위한 모델이다. 하지만 원칙적으로 model은 c가 아니라 x*(c)를 구하고 이를 직접 최적화하는 예측을 만드는 것이 바람직할 것이다. 이 둘 사이의 차이가 PFL과 DFL의 차이를 만든다. 

 

Prediction foucused learning(PFL), Two staged learning:

이 방법은 model이 정확한 parameter c를 예측하게 하는 것을 목표로 한다. 즉 아래의 수식(loss는 mse로 가정)을 minmize한 후에 optimization 문제를 푼다. 

 

 

Decision-focused learning (DFL)

DFL의 경우에는 예측 및 최적화를 통합하여 결정을 내린다. c의 예측 정확성이 training의 목적이 아닌 CO 이후의 error에 중점을 둔다. 즉, full-information optimal objecvie value와 predicted value를 이용한 objective value 사이의 차이를 줄이는 것이 목적이다. 이를 작업손실 task loss라 하며 아래와 같이 정의된다. 

 

 

실제로 정확히 예측한다면, 즉 prediction error가 0이라면 Regret error 또한 0일것이다. 다만, 실제로 모든 샘플에 대해 예측 오류가 없는 ML 모델을 학습하는 것은 불가능하기에 대체로 예측 손실과 작업손실이 일치하지 않는다. 그럼으로 작업손실을 직접 최소화함으로서 예측오류가 결정오류에 미치는 영향을 기준으로 예측오류를 암묵적으로 조정하는 것을 목표로 한다, 

이를 유명한 최적화 예제인 Knapsack problem을 통해서 설명한다. 

Knap sack problem & Prediction error와 Task error가 동일하지 않은 이유

Knap sack problem을 간단히 설명하면 가방에 담을 수 있는 물건의 총 무게가 한정되어있을 때 가장 가치 있는 물건의 조합을 어떻게 하면 담을 수 있는가?에 관한 문제이다. 

knap sack problem

이를 Predict-optimize 문제에 대입하면 각각의 item의 value가 예측되어야하는 경우일 것이다.

매우 단순화하여 아이템이 2개만 있는 경우라고 하자. 파란 부분은 Item 2가 선택되어야하는 경우일 것이고 빨간 부분은 item 1이 선택되어야할 경우이다(더 가치가 높은 것을 담자).

True value, ground truth of item value는 파란색 별이라고 하자. 만일 초록색 예측이 이루어진다면 ground truth와는 다른 예측이 이루어졌지만 모두 동일한 decision making이 이루어지게 된다. 하지만 x, 빨간색으로 예측한다면 다른 초록색들보다 MSE는 작을지라도 Decsion making입장에서는 다른 선택을 하는 것이 된다. 즉 예측 오류가 증가하더라도 선택된 항목이 변경되지 않는다면 솔루션은 변경되지 않는다, 즉 Task loss는 변하지 않는다.

 

단순히 point를 minimization하는 것이 아니라 Expectation, 확률적인 측면으로 접근한다면 이를 ERM, Empirical Risk Minimisation 문제로 바꾸어 표현 가능하다. ERM은 train sample에 관한 손실함수의 평균값을 구하는 방법을 의미한다. 물론 point estimiation이 아닌 분포 추정 문제로 바꿀 수 있기도 하다. 

다만, 분포적으로 robust loss를 minimization하는 것은 매우 어렵다(Levy, Carmon, Duchi, & Sidford, 2020) 

또한 ERM의 경우 직접적으로최종 의사 결정을 고려하는 문제는 아니기에 차이가 있는듯하다.
+) Overfitting 위험 및 gradient를 구하지 못하는 경우가 생길 수 있다 

 

DFL을 ERM 관점으로 바라보면 아래와 같이 정의할 수 있을 것이다.

즉, 모든 가능한 경우의 의사결정에 관한 평균 오차를 최소화하는 방향으로 이루어질 것이다. 

 

다만 문제는 위에서 언급한것과 같이 아래 식의 우측의 2번째 요소가 아래의 특징을 가질 때가 많다는 것이다. 

 

1. Loss를 update할때 loss 자체가 closed form이 아닌 경우가 많다(해를 명확히 구할 수 없는 경우가 많음)

2. 미분 불가능한 형태일 때가 많다(특정 지점이 0이거나 불연속적임)

는 것이다. 

 

미분불가능한 경우의 경우 0-1 loss가 있을 것이다 참이 아니면 1을 출력하는 경우, 실제 기울기를 구할 수는 없다. 이런 경우 대체 가능한 surrogate loss function을 사용하며 negative log-liklihood loss를 사용한다. 

 

이런 다양항문제를 해결하기 위해 그외에도 다양한 접근법이 논의되고 있다. 

 

2편에서 계속..!

 

추가 참고

https://m.blog.naver.com/cheeryun/221906435208

Surrogate Loss Functions and Early Stopping(대리 손실함수와 조기 종료)

https://velog.io/@lm_minjin/MIT-Deep-Learning-CH8.-Optimization-for-Training-Deep-models