Various artificial network models have been investigated for the problem of deriving grammar rules from a finite set of input examples. Among them, discrete recurrent network are more robust and more stable than any other network models. But due to gradient descent mechanism, even discrete recurrent network is not powerful enough for a certain input examples.
In this thesis, in order to improve such recurrent networks with gradient descent rule we first present the modified learning algorithm associated with them. Then, we propose the modified second-order recurrent networks model with the structural clustering learning method in order to make the model more powerful for any type of input examples.
Such two methodologies are presented and studied in learning context-free grammars through second-order recurrent networks with a external stack. Hence, we present three main issues as follows;
● the improved second-order recurrent neural networks,
● the equivalent second-order recurrent neural networks(ESRNN), and
● the ESRNN for grammatical inference
In the improved second-order recurrent networks, we propose two considerations that improve the learning performance of the existing second-order recurrent neural networks for inferring regular grammars. One is to arrange input strings in well-ordered form and use them as inputs. Experiments were performed to evaluate the learning performance according to input order types and decide the best type. The other is to analyze the cause of the failure to learn due to the recursive gradient-descent rule and modify the algorithm so as to reduce total learning time. Using such considerations, we suggest the modified learning method and show the enhanced result of experiments.
In the equivalent second-order recurrent networks, second-order recurrent neural networks including discrete recurrent networks and analog recurrent network have such problems as the restriction of the number of training examples and the restriction of the length of training example; i.e., it is more difficult for them to learn longer examples or more examples than limitations.
We proposes the second-order recurrent neural networks (SRNN) equivalent to the modified finite automata(MFA), proves the equivalent SRNN (ESRNN) to MFA, and present how to convert ESRNN into MFA and vice versa. Since neurons in the ESRNN employ a hard-limiter activation functions, the proposed ESRNN can become a good alternative of hardware implementation for regular grammars and finite automata as well as grammatical inference.
Finally, in ESRNN for grammatical inference, we present the learning algorithm to construct the stable SRNN(SSRNN) for inferring regular grammar through the architecture of ESRNN. The learning algorithm can learn any examples without restricting their quantity and length and determine the required number of neurons and the values of weights of SSRNN. ESRNN is expanded for inferring context-free grammars by appending an external stack, stack operation layer, and link connections. This network, which is called the expanded ESRNN(EESRNN), means third-order recurrent network.
In order to develop more efficient neural networks for grammatical inference we suggest the architectures of third-order recurrent neural networks to represent the context-free and present how to convert EESRNN into PDA and vice versa.
유한개의 입력예로부터 문법규칙을 유도해 내는 문제를 해결하기 위한 많은 인공 회로망 모델이 연구되어 왔다. 그것들 중에는 이산 순환망이 종전의 어느 모델보다도 더 건강하고 더 안정된다. 그러나 기울기-감소 미케니즘덕분에 심지어 이산 순환회로망에서 조차도 어떤 입력예에 대하여 충분히 강력하지 못하다.
이 논문에서는 기울기-감소규칙을 가진 이러한 순환망을 개선하기 위하여 우리는 먼저 그것들과 결부된 수정된 학습 알고리즘을 나타낸다. 그런다음, 구조적으로 모우기 학습 방법을 가진 수정된 이차 순환 회로망을 제안하여 어떠한 형태의 입력에도 더 강력한 모델이 되도록한다.
그러한 두 방법론은 외부스택을 가진 이차 순환 회로망을 통하여 문맥-자유 문법을 나타내어 지고 연구되어진다.
● 개선된 이차 순환 신경회로망
● 동등한 이차 순환 신경회로망(ESRNN)
● 문법 추론을 위한 ESRNN
개선된 이차 순환 신경회로망에서는 정규문번을 추론하는 기존의 이차 순환 신경망의 학습 알고리즘을 개선하는 두개의 고려사항을 제안한다. 하나는 입력 스트링을 잘 정돈하여 입력으로 사용하는 것이다. 입력 순서형에 따라서 학습 성능을 평가하기 위한 실험이 이뤄지고 가장 좋은 형을 결정한다. 다른 하나는 순환적 기울기-감소 규칙때문에 학습하기가 실패하는 원인을 분석하여 전체 학습시간을 줄이기 위하여 알고리즘을 수정한다. 이러한 고려사항을 이용하여 수정된 학습 알고리즘을 제안하고 실험의 향상된 결과를 보여준다.
동등한 이차 순환 신경회로망에서는 이산 순환 신경망과 아날로그 순환 신경망을 포함한 이차 신경 회로망은 학습 예의 갯수에 대한 제한과 학습 예들의 길이등의 문제를 가진다. 즉, 그 것들이 제한된 것 보다 더 긴 예들 또는 보다 더 많은 예들을 학습하기는 더 어렵다.
우리는 이차 순환 신경망이 수정된 유한 오토마타(MFA) 제안하고 ESRNN이 MFA와 동등함을 증명하며 서로들 변환 하는 방법을 나타냈다. ESRNN에서 뉴런들은 하드리미터 활동 함수를 채택하므로 제안된 ESRNN은 문법적 추론 뿐만 아니라 정규 문법, 유한 오토마타에 대하여 하드웨어 구현의 좋은 대안이 된다.
마지막으로 추론을 위한 ESRNN에서는 ESRNN의 구조를 통해서 정규문법을 추론하는 안정된 SRNN(SSRNN)을 구성하는 학습 알고리즘을 나타낸다. 학습 알고리즘은 그 입력예들의 양과 길이를 제한함이 없이 아무 예들을 학습할 수 있고 SSRNN의 뉴런의 갯수와 가중치들의 값을 결정한다. ESRNN에 외부 스택, 스택 동작층, 연결부들을 부가함으로써 문맥-자유 문법을 추론하도록 확장된다. 소위 확장된 ESRNN(EESRNN) 이라 불리우는 이 회로망은 삼차 순환망을 의미한다.
좀더 효율적인 문법적 추론을 위하여 삼차 순환 신경회로망의 구조들을 제안해서 문맥-자유 문법을 나타내고 푸쉬다운 오토마타를 EESRNN으로 변환하는 방법을 나타낸다.
