튜링 머신은 딥러닝 분야에서 가장 인기 있는 순환 신경망 RNN이다? 1996년 논문이 이를 증명했습니다!

1996년 8월 19일부터 23일까지 핀란드 인공지능협회와 바사대학교가 주최한 핀란드 인공지능 컨퍼런스가 핀란드 바사에서 열렸습니다.

컨퍼런스에서 발표된 논문은 튜링 머신이 순환 신경망임을 입증했습니다.

네, 이게 26년 전이에요!

1996년에 발표된 이 논문을 살펴보겠습니다.

1 소개

1.1 신경망 분류

신경망은 입력 패턴이 특정 범주에 속하는지 여부를 확인하는 분류 작업에 사용될 수 있습니다.

단일 레이어 피드포워드 네트워크는 선형으로 분리 가능한 패턴을 분류하는 데에만 사용할 수 있다는 것이 오랫동안 알려져 왔습니다. 즉, 연속적인 레이어가 많을수록 클래스 분포가 더 복잡해집니다.

네트워크 구조에 피드백이 도입되면 퍼셉트론 출력값이 재활용되어 연속 레이어 수가 원칙적으로 무한대가 됩니다.

컴퓨팅 파워가 질적으로 향상되었나요? 대답은 '예'입니다.

예를 들어 입력 정수가 소수인지 확인하기 위해 분류자를 구성할 수 있습니다.

이 목적으로 사용되는 네트워크의 크기는 유한할 수 있으며, 입력 정수 크기가 제한되지 않더라도 올바르게 분류할 수 있는 소수의 수는 무한하다는 것이 밝혀졌습니다.

이 기사에서는 "동일한 계산 요소로 구성된 순환 네트워크 구조"를 사용하여 (알고리즘적으로) 계산 가능한 모든 기능을 완성할 수 있습니다.

1.2 계산 가능성에 대하여

계산 가능성 이론의 기본 공리에 따르면 튜링 기계를 사용하여 계산 가능한 함수를 구현할 수 있습니다.

프로그래밍 언어 정의. 언어에는 네 가지 기본 연산이 있습니다.

여기서

V

는 양의 정수 값을 갖는 변수를 나타내고 j는 행 번호를 나타냅니다. 함수가 Turing 계산 가능하다면 이 간단한 언어를 사용하여 인코딩할 수 있다는 것을 알 수 있습니다(자세한 내용은 [1] 참조)

.

2 튜링 네트워크

2.1 재귀 신경망 구조

이 글에서 연구한 신경망은 모두 퍼셉트론으로 구성되어 있습니다. 퍼셉트론 개수의 연산

q

은 다음과 같이 정의할 수 있습니다.

여기서 현재 순간의 퍼셉트론 출력(

으로 표시)은 n 입력 을 사용하여 계산됩니다. 비선형 함수 f

는 이제

로 정의할 수 있습니다. 이런 식으로 함수는 단순히 음수 값을 "절단"할 수 있으며 퍼셉트론 네트워크의 루프는 퍼셉트론이 복잡한 방식으로 결합될 수 있음을 의미합니다. .

그림 1 순환 신경망의 전체 프레임워크, 구조는 외부 입력 없이 자율적이며 네트워크 동작은 초기 상태에 의해 완전히 결정됩니다.

그림 1에서 순환 구조는 다음과 같습니다. 일반 프레임워크: 이제 및 n은 퍼셉트론의 수이고, 퍼셉트론 p에서 퍼셉트론 q로의 연결은 (1)의 스칼라 가중치로 표시됩니다.

즉, 초기 상태가 주어지면 네트워크 상태는 더 이상 변경되지 않을 때까지 반복되며 결과는 안정적인 상태 또는 네트워크의 "고정 지점"에서 읽을 수 있습니다.

2.2 신경망 구축

다음으로 이 프로그램이 퍼셉트론 네트워크에서 어떻게 구현되는지 설명하겠습니다. 네트워크는 다음 노드(또는 퍼셉트론)로 구성됩니다.

• 프로그램의 모든 변수 V에는 변수 노드 가 있습니다.
• 모든 프로그램 라인 i에는 명령어 노드 가 있습니다.
• 라인 i의 각 조건부 분기 명령에는 두 개의 추가 분기 노드 및 가 있습니다.

언어 프로그램의 구현은 퍼셉트론 네트워크에 대한 다음 변경 사항으로 구성됩니다.

• 프로그램의 각 변경 V에 대해 다음 링크를 사용하여 네트워크를 확장합니다.

• 프로그램 코드의 i 라인에 연산()이 없으면 다음 링크를 사용하여 네트워크가 확장됩니다(노드 이 존재한다고 가정:

• ). i 줄에 증분 작업()이 있는 경우 다음과 같이 네트워크를 확장합니다.

• 라인 i에 감소 연산()이 있는 경우 다음과 같이 네트워크를 확장합니다.

• 라인 i에 조건 분기()가 있는 경우 네트워크를 확장합니다. 다음과 같이: 네트워크 확장:

2.3 동등성 증명

이제 증명해야 할 것은 "네트워크의 내부 상태 또는 네트워크 노드의 내용"을 프로그램 상태로 식별할 수 있다는 것입니다. 네트워크 상태의 연속성은 프로그램 스트림 대응과 일치합니다.

은 네트워크의 "법적 상태"를 다음과 같이 정의합니다.

• 모든 전환 노드 및 (2.2에 정의됨)에 대한 출력은 0입니다().
최대 하나의 명령어 노드
• 에는 단위 출력()이 있고, 다른 모든 명령어 노드에는 출력이 0이며,
변수 노드에는 음수가 아닌 정수 출력 값이 있습니다.

모든 명령어 노드의 출력이 0이면 상태는

최종 상태입니다. 합법적인 네트워크 상태는 프로그램 "스냅샷"으로 직접 해석될 수 있습니다. ​인 경우 프로그램 카운터는 i 라인에 있고 해당 변수 값은 변수 노드에 저장됩니다.

네트워크 상태 변경은 0이 아닌 노드에 의해 활성화됩니다.

먼저 변수 노드에 초점을 맞추면 이들이 적분기처럼 동작하고 노드의 이전 콘텐츠가 동일한 노드로 루프백되는 것으로 나타났습니다.

변수 노드에서 다른 노드로의 유일한 연결은 음의 가중치를 갖습니다. 따라서 비선형성으로 인해 0을 포함하는 노드는 변경되지 않습니다(2).

다음으로 명령어 노드에 대해 자세히 설명합니다. 0이 아닌 유일한 명령어 노드

​가 시간 k에 있다고 가정합니다. 이는 프로그램 코드의 i 라인에 있는 프로그램 카운터에 해당합니다.

프로그램의

i 라인이 ​이면 한 단계 앞으로 나아가는 네트워크의 동작은 다음과 같이 표현될 수 있습니다(영향을 받는 노드만 표시됨)

사실이 입증되었습니다. 새로운 네트워크 상태가 다시 합법적입니다. 프로그램 코드와 비교하면 프로그램 카운터가

i+1 줄로 이동되는 것과 같습니다.

반면, 프로그램의 i번째 줄이 이면 한 단계 앞으로의 동작은

이렇게 하면 프로그램 카운터가 다음 줄로 이동하는 것 외에도 , 변수 V 값도 감소합니다. i 라인이

인 경우 변수 V의 값이 증가한다는 점을 제외하면 네트워크 작동은 동일합니다. i

라인의 조건부 분기 작업(IF

GOTO j)은 보다 복잡한 작업 순서를 활성화합니다. 이 후에 단계에서 네트워크 상태는 다시 또 다른 프로그램 스냅샷으로 해석될 수 있습니다. 해당 프로그램 라인이 실행된 것처럼 변수 값이 변경되고 토큰이 새 위치로 전송되었습니다.

토큰이 사라지면 네트워크 상태는 더 이상 변경되지 않습니다. 이는 프로그램 카운터가 프로그램 코드를 "초과"하는 경우, 즉 프로그램이 종료되는 경우에만 발생할 수 있습니다.

네트워크의 운영도 해당 프로그램의 운영과 유사하게 진행되어 증명이 완료됩니다.

3 수정

3.1 확장

프로그래밍을 더 쉽게 만들고 결과 프로그램을 더 읽기 쉽고 더 빠르게 실행할 수 있도록 간소화된 추가 지침을 쉽게 정의할 수 있습니다. 예를 들어,

라인의

i

에 있는 무조건 분기(GOTO j)는 i 라인의 변수(

​

)에 상수 c를 추가하여

​

로 구현될 수 있습니다. 는 라인의 또 다른 조건부 분기(IF

V

=0 GOTO
• j )일 수 있습니다. i는
  ​
• 증가/감소 명령으로 구현할 수 있습니다. 다음을 수행한다고 가정해 보겠습니다. ​. 노드는 하나만 필요합니다​
  :
​
• 위의 방법이 결코 튜링 머신을 구현하는 유일한 방법은 아닙니다. 이는 간단한 구현이므로 애플리케이션에서 반드시 최적이 아닐 수도 있습니다.
  
3.2 행렬 공식화
• 위의 구성은 행렬의 형태로도 구현될 수 있습니다. 기본 아이디어는 프로세스 상태s에 변수 값과 "프로그램 카운터"를 저장하고 상태 전이 행렬 A
  이 노드 간의 링크를 나타내도록 하는 것입니다.

행렬 구조의 작동은 이산 시간 동적 프로세스로 정의될 수 있습니다

여기서 비선형 벡터 값 함수 는 이제 (2)에서와 같이 요소별로 정의됩니다.

상태 전이 행렬A의 내용은 네트워크 공식에서 쉽게 해독됩니다. 행렬 요소는 노드 간 가중치입니다.

이 행렬 공식은 [3]에서 제안된 "개념 행렬" 프레임워크와 유사합니다.

4 예제

간단한 함수 y=x를 구현하려고 한다고 가정합니다. 즉, 입력 변수 x의 값이 출력 변수 y에 전달되어야 합니다. 언어를 사용하면 다음과 같이 인코딩될 수 있습니다(이제 "진입점"이 첫 번째 줄이 아니라 세 번째 줄이 되도록 함).

결과 퍼셉트론 네트워크는 그림 2에 표시됩니다.

실선은 양의 연결(무게 1)을 나타내고, 점선은 음의 연결(무게 -1)을 나타냅니다. 그림 1과 비교하면 노드에 지연 요소를 통합하여 네트워크 구조가 다시 그려지고 단순화됩니다.

그림 2 간단한 프로그램의 네트워크 구현

행렬 형식에서 위 프로그램은 다음과 같습니다.

행렬 A의 처음 두 행/열에 해당 두 개의 변수 Y 및 X를 나타내는 노드에 대한 링크가 있는 다음 세 줄은 세 개의 프로그램 줄(1, 2 및 3)을 나타내고 마지막 두 줄은 분기 명령에 필요한 추가 노드(3' 및 삼'').

그리고 초기(반복 전) 상태와 최종(반복 후, 고정 소수점을 찾았을 때) 상태가 있습니다.

변수 노드의 값이 0과 1 사이에서 엄격하게 유지된다면, 그러면 동적 시스템( 3) 작업은 선형이 되며 ​ 함수는 전혀 효과가 없습니다.

원칙적으로 선형 시스템 이론을 분석에 사용할 수 있습니다.

예를 들어 그림 3에는 상태 천이 행렬 A의 고유값이 표시됩니다.

위의 예에서 단위원 외부에 고유값이 있더라도 비선형성으로 인해 반복이 항상 안정적입니다.

반복은 항상 단계 후에 수렴되는 것으로 나타났습니다. 여기서 입니다.

그림 3 간단한 프로그램의 "고유값"

5 토론

5.1 이론적 측면

튜링 기계는 퍼셉트론 네트워크로 인코딩될 수 있음이 밝혀졌습니다.

정의에 따르면 모든 계산 가능한 함수는 Turing 계산 가능합니다. 계산 가능성 이론의 틀 내에서는 이보다 더 강력한 계산 시스템이 존재하지 않습니다.

그래서 결론을 내릴 수 있습니다. -

순환 퍼셉트론 네트워크(위에 표시됨)는 Turing 기계의 (아직 또 다른) 형태입니다.

이 동등성의 장점은 계산 가능성 이론의 결과를 쉽게 얻을 수 있다는 것입니다. 예를 들어 네트워크와 초기 상태가 주어지면 프로세스가 결국 멈출지 여부를 알 수 없습니다.

위의 이론적 동등성은 계산 효율성에 대해 아무 말도 하지 않습니다.

네트워크에서 발생하는 다양한 메커니즘으로 인해 기존 Turing 기계 구현(실제로는 오늘날의 컴퓨터)에 비해 이 프레임워크에서 일부 기능을 더 잘 구현할 수 있습니다.

적어도 어떤 경우에는 스냅샷 벡터에 여러 "프로그램 카운터"를 허용하여 알고리즘의 네트워크 구현을 병렬화할 수 있습니다.

네트워크 운영은 글로벌이 아닌 엄격하게 로컬입니다.

예를 들어, NP-완전 문제가 네트워크 환경에서 더 효율적으로 공격될 수 있는지에 대한 흥미로운 질문이 생깁니다!

언어 와 비교하여 네트워크 구현에는 다음과 같은 "확장"이 있습니다.

• 변수는 정수 값뿐만 아니라 연속형일 수 있습니다. 실제로 실수를 표현하는 (이론적) 능력은 표현되는 모든 숫자가 유리수인 언어 보다 네트워크 구현을 더 강력하게 만듭니다.
• 다양한 "프로그램 카운터"가 동시에 존재할 수 있으며 제어 전송이 "퍼지"될 수 있습니다. 이는 명령 노드에서 제공하는 프로그램 카운터 값이 정수가 아닐 수 있음을 의미합니다.
• 더 작은 확장은 자유롭게 정의할 수 있는 프로그램 진입점입니다. 이는 프로그램을 단순화하는 데 도움이 될 수 있습니다. 예를 들어 변수 복사는 위의 세 개의 프로그램 라인에서 수행되는 반면 명목 솔루션([1] 참조)에는 7개의 라인과 추가 로컬 변수가 필요합니다.

원래 프로그램 코드와 비교할 때 행렬 공식은 분명히 프로그램 코드보다 더 "연속적인" 정보 표현입니다. 매개변수는 (자주) 수정될 수 있으며 반복 결과는 갑자기 변경되지 않습니다.

이 "중복성"은 일부 응용 프로그램에서 유용할 수 있습니다.

예를 들어, 구조 최적화를 위해 유전자 알고리즘(GA)을 사용하는 경우 유전자 알고리즘에 사용되는 무작위 검색 전략이 더 효율적으로 만들어질 수 있습니다. 시스템 구조가 변경된 후 연속 비용 함수의 로컬 최소값은 다음과 같습니다. 일부 전통적인 기술을 사용하여 검색했습니다([4] 참조).

[5]에서 설명한 것처럼 예제를 통해 유한 상태 기계 구조를 학습하면 이보다 복잡한 경우에도 네트워크 구조를 반복적으로 향상시키는 방법이 사용된다는 것을 알 수 있습니다.

위 결과는 신경망 이론뿐만 아니라 동적 시스템 공식(3)만 보면 계산 가능성 이론 분야에서 발견되는 모든 현상도 비선형 역학을 찾는 간단한 형태로 존재한다는 것이 분명합니다. 프로세스.

예를 들어, 정지 문제의 결정 불가능성은 시스템 이론 분야에 흥미로운 기여를 합니다. Turing 기계로 표현되는 모든 결정 프로세스에는 이 프로세스를 위반하는 형식 (3)의 동적 시스템이 있습니다. 일반적인 안정성 분석 알고리즘.

5.2 관련 작업

제시된 네트워크 구조와 재귀적 Hopfield 신경망 패러다임 사이에는 몇 가지 유사점이 있습니다(예를 들어 [2] 참조).

두 경우 모두 "입력"은 네트워크의 초기 상태로 인코딩되고 "출력"은 반복 후 네트워크의 최종 상태에서 읽혀집니다.

Hopfield 네트워크의 고정점은 사전 프로그래밍된 패턴 모델이고 입력은 "노이즈" 패턴입니다. 네트워크를 사용하여 손상된 패턴을 향상시킬 수 있습니다.

의 비선형 함수의 전망(2)은 위에서 언급한 "튜링 네트워크"에서 가능한 상태의 수를 무한하게 만듭니다.

단위 출력이 항상 -1 또는 1인 Hopfield 네트워크와 비교하면 이론적으로 이러한 네트워크 구조가 매우 다르다는 것을 알 수 있습니다.

예를 들어 Hopfield 네트워크의 안정적인 포인트 집합은 제한되어 있지만 Turing 네트워크로 표현되는 프로그램은 가능한 결과가 무한한 경우가 많습니다.

Hopfield 네트워크의 계산 기능은 [6]에서 논의됩니다.

Petri net은 이벤트 기반 및 동시 시스템 모델링을 위한 강력한 도구입니다[7].

페트리 넷은 비트와 전환, 그리고 이를 연결하는 호로 구성됩니다. 각 장소에는 원하는 수의 토큰이 포함될 수 있으며 토큰의 배포를 페트리넷의 표시라고 합니다.

변환의 입력 위치가 모두 마커로 채워지면 변환이 트리거되어 각 입력 위치에서 마커를 제거하고 각 출력 위치에 마커를 추가할 수 있습니다.

추가 억제 아크를 갖춘 확장된 페트리 네트에도 튜링 기계의 기능이 있다는 것이 입증될 수 있습니다([7] 참조).

위에서 언급한 튜링 넷과 페트리 넷의 주요 차이점은 페트리 넷의 프레임워크가 더 복잡하고 특별히 맞춤화된 구조를 가지고 있어 단순한 일반 형식으로는 표현할 수 없다는 것입니다(3).

참조

1 Davis, M. 및 Weyuker, E.: 계산 가능성, 복잡성 및 언어---Fundamentals of Theoretical Computer Science, New York, 1983.

2 Haykin, S.: Neural Networks. Macmillan College Publishing, New York, 1994.

3 Hyötyniemi, H.: Building Blocks of Intelligence? 지능의 차원), 핀란드 인공지능학회, 1995년, pp. 199--226.

4 Hyötyniemi, H. 및 Koivo, H.: 유전자, 코드 및 동적 시스템에 관한 두 번째 북유럽 워크숍 진행 중. Genetic Algorithms(NWGA'96), 핀란드 바사, 1996년 8월 19~23일.

5 Manolios, P. 및 Fanelli, R.: 1차 순환 신경망 및 결정론적 유한 상태 신경 계산 6. , 1994, pp. 1155--1173.

6 Orponen, P.: 신경망 계산 8, 1996, pp. 403--415.

7 Peterson , J.L.: Petri Net 이론 및 시스템 모델링 - Hall, Englewood Cliffs, New Jersey, 1981.

참고 자료:

​​https://www.php. /link/0465a1824942fac19824528343613213​​​

위 내용은 튜링 머신은 딥러닝 분야에서 가장 인기 있는 순환 신경망 RNN이다? 1996년 논문이 이를 증명했습니다!의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!