신경망 가중치 노름 = 콜모고로프 복잡도

요약

본 논문은 루프형 신경망의 최소 가중치 노름이 출력 문자열의 콜모고로프 복잡도의 로그 인자 차이에 같다는 것을 증명합니다. 이는 가중치 감쇠(weight decay)가 계산 가능한 함수에 대한 최적 사전 확률인 솔로몬오프 보편 사전 확률과 다항식 인자 차이까지 일치하는 사전을 유도함을 의미하며, 노름의 종류와 무관하게 성립하는 일반적인 경계입니다. 이 결과는 고정 정밀도(fixed precision) 환경에서만 유효하며, 신경망 가중치를 프로그램으로 인코딩하고 로그 주소 지정 오버헤드를 통해 설명할 수 있다는 두 가지 핵심 축소 과정을 활용합니다.

핵심 포인트

• 신경망의 최소 가중치 노름은 출력 문자열의 콜모고로프 복잡도와 밀접하게 관련되어 있습니다.
• 가중치 감쇠는 계산 가능한 함수에 대한 최적 사전 확률(솔로몬오프 보편 사전 확률)을 유도하는 효과를 갖습니다.
• 이 경계는 사용되는 노름(norm)의 종류에 관계없이 성립하며, 고정 정밀도 환경에서만 유효합니다.
• 신경망 가중치를 프로그램으로 인코딩하고 로그 주소 지정 오버헤드를 통해 설명할 수 있다는 것이 핵심 증명 과정입니다.