무료 점심 정리 없음

이 기사는 검증을 위해 추가적인 인용이 필요합니다. 신뢰할 수 있는 자료에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주시기 바랍니다. 출처가 밝혀지지 않은 자료에 이의를 제기하여 제거할 수 있습니다. 출처 찾기 : "무료점심 정리 없음" – 뉴스 · 신문 · 서적 · 학자 · JSTOR (2022년 7월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

수학 민속에서, 데이비드 월퍼트와 윌리엄 맥레디의 "무료 점심은 없다" (때로는 복수화) 정리는 "무료 점심과 같은 것은 없다"는 말을 암시합니다. 즉, 성공을 위한 쉬운 지름길은 없습니다.1997년 "최적화를 위한 무료 점심 이론은 없다"에 등장했습니다.^[1]Wolpert는 이전에 기계 학습(통계 추론)을 위한 무료 점심 정리를 도출하지 않았습니다.^[2]

2005년, Wolpert와 Macready는 논문에서 첫 번째 정리를 "모든 가능한 문제에서 성능이 평균화될 때 두 최적화 알고리즘이 동등하다는 것을 명시합니다."^[3]라고 밝혔습니다.

"무료 점심 식사 금지" 정리는 Wolpert와 Macready가 실제로 증명하는 정리들의 쉽게 언급되고 쉽게 이해되는 결과입니다.이것은 증명된 정리보다 약하기 때문에 요약되지 않습니다.여러 조사관들이 Wolpert와 Macready의 연구를 상당히 확장시켰습니다.연구 영역의 맥락에서 NFL 정리가 어떻게 사용되는지에 관하여, 검색 및 최적화에서 무상급식은 통계적 동일성, 특히 검색^[4] 및 최적화를 위한 데이터를 수학적으로 분석하기 위한 목적으로 전용되는 분야입니다.^[5]

일부 학자들은 NFL이 중요한 통찰력을 전달한다고 주장하는 반면, 다른 학자들은 NFL이 머신러닝 연구와 거의 관련이 없다고 주장합니다.^[6][7]

예

정확히 이틀 동안 존재하며 각 날에는 정사각형 또는 삼각형과 같은 하나의 물체를 포함하는 장난감 우주를 배치합니다.우주는 정확히 네 가지 가능한 역사를 가지고 있습니다.

1. (제곱, 삼각형): 우주는 1일차에는 제곱을, 2일차에는 삼각형을 포함합니다.
2. (제곱, 제곱)
3. (triangle, 삼각형)
4. (triangle, 정사각형)

1일차에 정사각형이 있을 경우 2일차에 정사각형을 예측함으로써 역사 #2에 성공하는 모든 예측 전략은 역사 #1에 실패하고, 그 반대도 마찬가지입니다.모든 이력이 동일한 가능성이 있는 경우 모든 예측 전략의 점수는 동일하고 정확도는 0.5입니다.^[8]

기원.

Wolpert와 Macready는 민속학 정리와 밀접한 관련이 있는 두 가지 NFL 정리를 제시합니다.이들은 논문에서 다음과 같이 기술하고 있습니다.

우리는 관련 결과를 NFL 정리라고 이름 붙였는데, 그 이유는 알고리즘이 특정 종류의 문제에서 우수한 성능을 발휘할 경우 나머지 모든 문제에서 성능이 저하된 것에 대한 보상이 필요하다는 것을 보여주기 때문입니다.^[5]

첫 번째 정리는 최적화가 진행되는 동안 변하지 않는 목표 함수를 가설로 하고, 두 번째 정리는 바뀔 수 있는 목표 함수를 가설로 합니다.^[5]

여기서 ${\displaystyle {}_{}^{}}$ ${\displaystyle d_{m}^{y}}$는 입력 값 $x$ ∈ ${\displaystyle X}$와 연관된 $비용$ 값 y$${\$displaystyle y}$의 $크기$ m$${\$displaystyle m}$의 순서 집합을 나타냅니다. $X$ ${\displaystyle$ $x$$\in X$ f :${\displaystyle X}$ → ${\displaystyle Y}$ ${\displaystyle$ f$:X\rightarrow Y}$는 최적화 중인 함수이고${\displaystyle }P$ (${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ∣ ${\displaystyle f,}$ ${\displaystyle m,}$ ${\displaystyle a}$) ${\displaystyle P(d_{m}^{y}\mid$ f$,m,a)}$는 조건부 pr입니다.$함수{\displaystyle }$f {\$displaystyle$ f$}$에서$${\$displaystyle a}$을$($를$)$ {\displaystyle $m}$번$$ 실행하는 $알고리즘$에서 주어진 비용 값 시퀀스를 얻을 수 있는 가능성.

이 정리는 다음과 같이 동등하게 공식화할 수 있습니다.

여기서 블라인드 서치는 알고리즘의 각 단계에서 이전에 선택되지 않은 $V$ ${\displaystyle V}$의 요소 $중$에서 V ∈ ${\displaystyle V}$ ${\displaystyle v\in V}$의 요소를 균일한 확률 분포로 랜덤하게 선택하는 것을 의미합니다.

본질적으로, 이것은 모든 함수 f가 동일한 가능성이 있을 때, 최적화 과정에서 m 값의 임의의 시퀀스를 관찰할 확률은 알고리즘에 의존하지 않는다는 것을 의미합니다.Wolpert and Macready의 분석 프레임워크에서 성능은 관찰된 값의 시퀀스(예: 벽시계 시간)의 함수이므로 모든 알고리즘이 목표 함수를 무작위로 균일하게 그릴 때 동일하게 성능을 분배하고 모든 알고리즘이 동일한 평균 성능을 갖는다는 것을 쉽게 따라갑니다.그러나 모든 알고리즘의 동일한 평균 성능이 정리 1을 의미하는 것은 아니므로 민속 정리는 원래 정리와 동등하지 않습니다.

정리 2는 시간에 따라 변하는 목적 함수에 대해 유사하지만 "더 미묘한" NFL 결과를 확립합니다.^[5]

동기

NFL 정리는 명시적으로 "환경이 균일한 무작위"일 때 추론할 수 있는 것(기계 학습용 NFL의 경우) 또는 발견할 수 있는 것(검색용 NFL의 경우)에 대한 질문에 의해 동기 부여되지 않았습니다.알고리즘 A가 알고리즘 B를 능가하는 환경의 수와 B가 A를 능가하는 환경의 수를 비교하기 위해 오히려 균일한 무작위성이 도구로 사용되었습니다. NFL은 두 집합 모두에 (적절하게 가중치가 부여된)^{[clarification needed]} 환경이 그만큼 많다는 것을 알려줍니다.

이것은 정확하게 "환경"이 무엇인지에 대한 많은 정의에 적용됩니다.특히, 학습 알고리즘 A가 B를 이기는 (평균적으로) 이전 분포가 그 반대인 만큼 많습니다.^{[citation needed]}사전 정보 집합에 대한 이러한 설명은 NFL에서 가장 중요한 것이지, 모든 환경에 동일한 확률을 할당하는 단일 특정 사전 분포에 대해 두 알고리즘이 동일하게 수행된다는 사실이 아닙니다.

NFL은 일련의 문제에 대한 근본적인 한계를 이해하는 것이 중요하지만, 실제로 발생할 수 있는 문제의 각 특정 사례에 대해서는 아무것도 언급하지 않습니다.즉 NFL은 수학적 진술에 포함된 내용을 진술하며 그 이상도 이하도 아닙니다.예를 들어, 알고리즘이 선험적으로 고정되고, 고정된 알고리즘에 대한 최악의 경우 문제가 후험적으로 선택되는 상황에 적용됩니다.따라서 실제로 "좋은" 문제가 있거나 특정 문제 인스턴스에 대해 "좋은" 학습 알고리즘을 선택할 수 있는 경우 NFL은 이 특정 문제 인스턴스에 대한 제한 사항을 언급하지 않습니다.NFL이 학습 알고리즘이나 검색 휴리스틱의 일반화를 제안하는 다른 논문의 결과와 모순되는 것처럼 보일 수 있지만 NFL의 정확한 수학적 논리와 직관적인 해석의 차이를 이해하는 것이 중요합니다.^[9]

시사점

NFL의 반직관적 의미 중 하나를 설명하기 위해 두 개의 지도 학습 알고리즘인 C와 D를 수정한다고 가정합니다.그런 다음 대상 함수 f를 샘플링하여 일련의 입력-출력 쌍, d를 생성합니다.d 밖에 있는 점과 관련된 출력을 예측하기 위해 C를 훈련시킬지 아니면 D를 훈련시킬지 어떻게 선택해야 합니까?

C와 D 중 하나를 선택하는 이 질문에 답하는 것은 거의 모든 과학 및 통계학에서 일반적인 일입니다. 이 두 알고리즘을 사용하여 교차 검증을 실행함으로써 말이죠.다시 말해, C와 D 중 어느 것을 d에서 일반화할지 결정하기 위해 d 내에서 검정할 때 표본 외 성능이 더 우수한 것을 확인합니다.

C와 D는 고정되어 있기 때문에 이들 사이에서 선택하기 위해 교차 검증을 사용하는 것은 그 자체로 알고리즘, 즉 임의의 데이터 세트에서 일반화하는 방법입니다.이 알고리즘을 A라고 부릅니다. (A는 과학적 방법 자체를 단순화한 모델이라고 할 수 있습니다.)

우리는 또한 우리의 선택을 위해 교차 검증을 사용할 수 있습니다.즉, d 내에서 표본 외 성능이 더 나쁜 것을 기준으로 C와 D 중 하나를 선택할 수 있습니다.다시 말하지만, C와 D는 고정되어 있기 때문에, 이러한 안티 크로스 검증의 사용은 그 자체로 알고리즘입니다.그 알고리즘을 B라고 부릅니다.

NFL은 A가 B를 이기는 것처럼 많은 목표 함수(및 관련 데이터 세트 d)에서 B가 A를 이겨야 한다는 것을 우리에게 알려줍니다.바로 이러한 의미에서 과학적 방법은 승리하는 것과 마찬가지로 "반(反)" 과학적 방법에 쉽게 질 것입니다.^[10]

NFL은 가능한 모든 기능의 균일한 분포 중에서 대상 기능을 선택한 경우에만 적용됩니다.그렇지 않고 특정 대상 함수가 다른 함수보다 선택될 가능성이 높은 경우 A가 B보다 전반적으로 더 우수한 성능을 보일 수 있습니다.NFL의 기여는 적절한 알고리즘을 선택하는 것이 알고리즘이 사용되고 있는 목표 함수의 종류에 대한 가정을 요구한다는 것을 알려준다는 것입니다.가정이 없다면 과학적 방법과 같은 "메타 알고리즘"은 무작위 선택보다 더 나은 성능을 발휘하지 못합니다.

일부 학자들은 NFL이 중요한 통찰력을 전달한다고 주장하는 반면, 다른 학자들은 NFL이 머신러닝 연구와 거의 관련이 없다고 주장합니다.^[6][7]예를 들어, 낮은 콜모고로프 복잡도의 시퀀스가 높은 복잡도의 시퀀스보다 가능성이 더 높은 경우 Occam의 면도기가 정확하다면, 교차 검증과 같은 일부 알고리듬은 실제적인 문제(임의 선택 또는 반 교차 검증과 비교할 때)에서 평균적으로 더 나은 성능을 발휘합니다.^[11]

반면 콜모고로프 복잡성에 기반한 인수를 사용하여 현실 세계의 속성을 설정하는 데는 계산할 수 없고 임의의 가산 상수까지 정의되지 않기 때문에 주요 형식적 문제가 있습니다.부분적으로 이러한 도전을 인식하여, 최근 일부 과학 철학자들은 "메타-인덕션"을 사용하여 튜링 기계를 호출하지 않고 무료 점심 이론을 피할 수 있는 방법이 있다고 주장했습니다.^[12]이러한 주장은 상당히 미묘하며, 에서 설명합니다.^[13]

참고 항목

• 외부성
• 은닉비용

메모들

외부 링크

• 무료 점심 정리 금지
• 정리를 설명하는 그래픽