Proxy-Constrained Optimization — 이론

TL: DR — 장난감 예제를 통해 프록시 제한 최적화 알고리즘을 안내하는 이 노트북을 확인하십시오 . 주제의 수학적인 특성으로 인해 노트북이 충분하지 않다는 점에 유의하십시오. 주제를 더 잘 이해하려면 전체 기사를 읽는 것이 좋습니다.

참고: 이 기사는 독자가 경사 하강법 및 기본 다변수 미적분학에 익숙하다고 가정합니다.

동기 부여

AI 모델이 테스트 데이터에서 95% 정확하다고 말했습니다. 좋은 모델인가요?

그 대답은 ' 아마도 '일 것입니다. AI 연구의 많은 부분이 모델의 실질적인 효능을 결정하는 방법을 찾는 데 전념할 정도로 너무 많습니다. 불행히도 훈련 데이터에 대한 정확도는 실제로 AI 모델의 신뢰성을 결정하는 데 충분하지 않습니다. 예를 들어 모델이 과소 지정 되었을 수 있습니다.작은 데이터 세트 또는 열악한 훈련 분포로 인해; 이 기사와 관련하여 불균형 데이터 세트와 같은 요인으로 인해 특정 데이터 하위 그룹이나 다양한 공정성 및 견고성 지표에서 모델의 성능이 저하될 수 있습니다. 특정 실제 응용 프로그램은 정확성 외에 모델에 추가 요구 사항을 부과할 수도 있습니다. 예를 들어 AI 기반 이메일 필터는 실제 이메일이 거의 전달되지 않도록 하기 위해 오탐률이 특정 임계값 미만인지 확인하기를 원할 수 있습니다. 스팸 메세지 함.

이 문제를 해결하려면 모델이 따라야 하는 추가 제약 조건을 도입하는 것이 좋습니다. 이를 위해 Google AI와 Cornell University의 연구원 팀은 이러한 제약을 적용하는 데 도움이 되는 방법을 자세히 설명하는 이 문서를 발표했습니다. 그런 다음 이 백서의 방법을 사용하여 현재 제한된 최적화 문제를 해결하는 데 널리 사용되는 TFCO(Tensorflow Constrained Optimization) 라이브러리를 만들었습니다 .

물론 이것은 이와 같은 문제를 해결하는 유일한 방법은 아니며(예를 들어 손실 함수에 가중 항을 추가하는 것도 상당히 일반적임) 완전한 솔루션은 아니지만 특히 다음을 처리할 때 상당히 효과적인 방법입니다. 엄격한 제약(즉, 80% 규칙 ).

이제 이 메서드를 다시 파생시켜 실제로 어떻게 작동하는지 살펴보겠습니다.

첫 번째 단계

이전에 다변수 미적분 수업을 수강한 적이 있다면 라그랑지안 함수를 접했을 가능성이 큽니다. 이 함수를 사용하면 g(x) = 0 에 따라 일부 함수 f(x) 를 최소화할 수 있습니다 .

여기서 방법에 대해 너무 자세히 논의하지는 않겠습니다. 기본 아이디어는 로컬 최소값/최대값이지만 함수의 모든 편도함수가 0이라는 것을 알고 있으므로 방정식 시스템을 설정하고 방정식을 찾을 수 있습니다. 최소/최대.

따라서 최적화 문제에 대해 비슷한 것을 설정하고 싶을 수 있습니다. 예를 들어 다음 공식을 설정할 수 있습니다.

여기서 θ 는 분류자 매개변수 벡터이고, loss(θ) 는 주요 손실 함수(즉, 회귀의 경우 MSE, 분류의 경우 교차 엔트로피)이고, constraint(θ) 는 ≤ 0으로 제한하려는 함수입니다.

영리한 시작

정말 영리하다면 확률적 경사하강법을 사용하여 이 함수를 최적화하는 방법이 있음을 알 수 있습니다.

우리는 이것을 2인용 게임으로 최적화하는 것에 대해 생각할 수 있습니다. 첫 번째 플레이어인 θ 플레이어는 공식을 최소화하려고 합니다. 일반 AI와 마찬가지로 이 플레이어는 경사 하강법을 사용하여 일련의 매개변수를 선택합니다. 반면에 우리의 두 번째 플레이어인 λ-player는 기울기 상승을 사용하여 공식을 최대화하는 λ 를 선택하려고 시도할 것입니다 . 기본적으로 다음 업데이트 루프를 정의할 수 있습니다.

여기서 lr 은 학습률 하이퍼파라미터이고, θⱼᵗ 는 epoch t 에서의 j번째 매개변수 이며, 마찬가지로 λᵢᵗ 는 epoch t 에서의 i번째 승수입니다 . 람다 플레이어가 경사 상승을 수행하고 있기 때문에 일반 경사 하강에서처럼 빼는 대신 lr ⋅ constraintᵢ(θ)를 추가하는 방법에 주목하십시오 .

우리는 λ 의 모든 요소가 완전히 양수이기를 원하므로(이유는 잠시 후에 설명하겠습니다) 람다 업데이트 루프를 약간 수정합니다.

여기서 ε은 작은 양의 값입니다. 또한 최대 값을 적용하기 위해 이것을 추가로 수정할 수 있지만(논문에서 수행함) 꼭 필요한 것은 아닙니다.

자, 이것은 정말 복잡해 보이므로 조금 분해해 봅시다.

먼저 λ 플레이어를 살펴보겠습니다. λ 플레이어는 공식을 최대화하기를 원하기 때문에 그들의 전략은 기본적으로 다음과 같이 분류할 수 있습니다.

1. Constraintᵢ(θ) > 0 이면 λᵢ를 가능한 한 크게 만드십시오 (λᵢ ⋅ constraintᵢ(θ)는 constraintᵢ(θ) 가 양수일 때 큰 λᵢ로 최대화되기 때문입니다).
2. Constraintᵢ(θ) < 0 이면 λᵢ를 가능한 한 작게 만드십시오 .

반면에 θ 플레이어는 라그랑지안을 최소화할 때 기본 손실 함수와 제약 조건 함수를 모두 고려합니다. 따라서 이들의 전략은 다음과 같이 분류할 수 있습니다.

1. λᵢ ⋅constraintᵢ (θ) 가 특정 제약에 대해 정말 크다면 주손실함수에 어긋나더라도 항을 최소화하는 방향으로 θ를 이동시킨다 .
2. 제약 조건을 만족하고 λᵢ ⋅constraintᵢ (θ) 가 작은 경우 주 손실 함수를 최소화하는 방향으로 θ를 이동합니다.

이제 제한된 최적화를 위한 적절한 출발점이 있습니다. θ 플레이어는 제약 조건을 충족하고 손실 함수를 최소화하도록 인센티브를 받습니다. 결정적으로, λ 플레이어는 제약 조건이 충족될 때(즉, 제약 조건ᵢ(θ) ≤ 0일 때) 제약 조건의 가중치를 거의 0으로 줄이기 때문에 θ 플레이어는 더 이상 제약 조건을 추가로 최소화하기 위해 명시적으로 인센티브를 받지 않습니다. 주 손실 기능을 최소화하는 데에만 집중합니다 . 이것이 이 접근 방식이 가중 보조 목표로 제약 조건을 추가하는 것과 다른 점입니다.

몇 가지 문제

일부 경우, 즉 라그랑지안이 미분 가능하고 볼록한 경우 이 접근 방식이 실제로 작동합니다. 그러나 종종 그렇듯이 이러한 조건이 충족되지 않으면 어떻게 됩니까?

예를 들어 1% 이하의 오탐률로 이메일 스팸 필터를 구축하려고 한다고 가정해 보겠습니다. 기억해

여기서 FP는 위양성의 수이고 TN은 참음성이며 FPR은 위양성 비율입니다.

다음과 같이 공식을 설정할 수 있습니다.

여기서 BCE(θ) 는 이진 교차 엔트로피 손실(주요 목적 함수)입니다. 그러나 θ에 대한 업데이트 루프는

이는 경사 하강법에 대해 작업할 수 없습니다. 즉, FPR(θ)은 거의 모든 곳에서 0 도함수를 갖는 조각별 함수입니다.

θ 플레이어가 제약 조건을 무시할 수 있기 때문에 오목한 설정에서도 실현 가능한 솔루션이 보장되지 않습니다.

더 가까워지기 — 근사값 사용

자, 분명히 우리의 방법은 미분 불가능하거나 오목한 공식에 대해서는 작동하지 않습니다. 그렇다면 지저분한 제약 조건을 사용하는 대신 거의 모든 곳에서 미분할 수 있는 근사치를 사용하면 어떨까요? 예를 들어 오탐지의 경우 다음과 같은 근사치를 설정할 수 있습니다.

그런 다음

부터

우리는 그것을 알고

이것은 정말 복잡해 보일 수 있지만 분해하면 나쁘지 않습니다. 조각별 함수의 첫 번째 문은 기본적으로 샘플이 참 양성인 경우 FPR이 변경되지 않는다고 말합니다. 예측 값이 0 미만이면 변경되지 않지만 관련성이 높지는 않습니다.)

그렇지 않으면 샘플이 참 음성이면 θⱼ가 예측을 더 긍정적으로 추진하거나( ∂/∂θⱼ ŷᵢ가 양수인 경우) 현재 예측 값( ŷᵢ )이 낮은 경우(예측 값이 낮기 때문에) 올라갈 것입니다. 올라가서 FPR을 올릴 수 있는 공간만 있습니다. ŷᵢ 이 이미 높으면 FPR이 더 높아져도 실제로 증가하지 않습니다.

기억해야 할 중요한 점은 이전의 조각별 FPR과 달리 근사 FPR wrt θ의 도함수가 모든 곳에서 0이 아니라는 것입니다. 즉, 실제로 θ를 업데이트하는 데 사용할 수 있습니다 . 또한 대략적인 FP는 볼록합니다 .

이것은 실제로 솔루션에 매우 가깝습니다. 불행하게도 공식에서 근사 함수를 사용하기 때문에 이제 λ 업데이트는 다음과 같이 됩니다.

이것의 문제는 λ 플레이어가 이제 실제 함수가 아닌 근사값을 기반으로 λ를 이동하도록 장려된다는 것입니다. 따라서 FPRₐₚₚᵣₒₓ ≤ 0.01 이면 FPR > 0.01 인 경우에도 제약 조건이 충족되는 것으로 간주됩니다 . 유사하게, 우리는 모델을 과도하게 제한하거나 실제로 잘못된 긍정 비율을 줄이기보다는 모델이 자신의 주장에 대해 더 확신하도록 만들 수 있습니다. 네거티브인 경우 FPR은 0이지만 FPRₐₚₚᵣₒₓ = 0.25입니다. 이는 모델이 원래 제약 조건을 실제로 충족하는 것보다 부정적인 주장에 대해 더 확신하도록 인센티브가 부여된다는 의미입니다.

솔루션 — 두 가지 제형

이것을 본 후에 우리는 이제 다음과 같은 공식이 필요하다는 것을 깨달았습니다.

1. θ 플레이어는 볼록하고 미분 가능한 것을 최소화합니다.
2. λ 플레이어는 일부 프록시가 아닌 원래 제약 조건을 기반으로 선택합니다.

여기서 L(θ, λ)ₜₕₑₜₐ 는 θ-플레이어가 사용하는 공식이고 마찬가지로 λ 공식은 λ-플레이어가 사용합니다. FPR 예에서 이것은 우리에게

결정적으로, 이 공식에서 λ는 엄격하게 양의 항목이 있는 벡터이고 모든 항목의 합은 1이어야 합니다. 기본적으로 λ 벡터는 공식의 각 요소에 가중치를 부여하는 정도를 결정합니다. 다시 말해서,

여기서 주목해야 할 몇 가지 사항이 있습니다. 먼저, 우리의 람다 플레이어에 대한 라그랑주 공식이 첫 번째 요소, 즉 원래 손실 함수의 가중치에 대해 어떤 것도 포함하지 않는다는 점에 주목하십시오. 물론 다른 λ 항목, 즉

그러나 이는 우리의 λ-플레이어가 기본 손실의 가중치를 결정하지만 실제로는 업데이트 단계의 손실에 대해 신경 쓰지 않는다는 것을 의미합니다. 왜 이런거야?

제약 조건 값이 변경될 때 λ에 어떤 일이 발생하는지 생각해 봅시다. 두 가지 기본 시나리오가 있습니다.

1. 원래 제약 조건이 충족되지 않으면 λ 업데이트로 인해 해당 제약 조건의 배수 가 매우 높아집니다. 따라서 우리의 1차 손실에 대한 배수는 매우 작아질 것입니다. 즉, θ-플레이어는 대략적인 제약 조건을 최소화하도록 인센티브를 받을 것입니다(올바르게 구성된 경우 원래 제약 조건을 충족해야 함).
2. 제약 조건이 충족되면 비 프록시 공식에서와 마찬가지로 λ 업데이트는 해당 제약 조건에 대한 가중치 증가를 중지하거나 충족되지 않은 제약 조건이 남아 있으면 충족된 제약 조건에서 충족되지 않은 제약 조건으로 가중치를 이동하기 시작합니다. 따라서 θ-플레이어는 더 이상 이미 충족된 제약 조건을 추가로 충족하도록 인센티브를 받지 않고 대신 기본 목표를 최소화하거나 미해결 제약 조건을 충족하도록 이동합니다.

두 번째로 주목해야 할 중요한 점은 λ-플레이어가 원래 제약 조건 만 보기 때문에 근사값이 아닌 원본 제약 조건을 준수하도록 강제한다는 것입니다. 실제 FPR이 0이기 때문에 모델이 참 부정 세트에 대해 ~25%의 긍정적 가능성을 예측하는 시나리오가 있는 경우 대략적인 FPR > 1%이더라도 해당 제약 조건의 가중치는 감소하는 경향이 있습니다.

마지막으로, θ-플레이어의 라그랑지안은 "친숙한" 근사 제약 조건을 사용하기 때문에 원래 제약 조건을 충족하기 위해 올바른 방향으로 이동하도록 매개 변수를 적절하게 업데이트할 수 있습니다.

결론

이제 제한된 최적화를 수행하기 위한 작업 공식을 성공적으로 도출했습니다. 이를 최소화하는 알고리즘을 보고 싶다면 이 기사를 위해 만든 컴패니언 노트북을 확인하는 것이 좋습니다 . 또한 주제에 대해 더 자세히 알고 싶다면 원본 문서를 확인하는 것이 좋습니다 .

내 노트북은 TFCO가 하는 일을 정확하게 수행하지 않습니다. 즉, 논문에 설명된 전체 절차는 최적화 루프 이후에 매개변수의 최종 집합을 반환하는 것이 아니라 보조 절차를 사용하여 n + 1 매개변수 집합에 대한 최적의 분포를 찾습니다. 여기서 n 은 제약 조건의 수입니다. 결국 절차에 대해 쓸 수 있지만 이 기사의 범위를 벗어납니다.

다음 시간까지!
-마태

문의사항이 있으시면 [email protected] 로 연락주세요 .