Construction of intelligent systems [603937]

Construction of intelligent systems
Seminar Paper of
Dumitru-Cristian Albu
At the Department of Informatics
Institut für Programmstrukturen
und Datenorganisation (IPD)
Advisor: Dipl. Inform. Alexander Wachtel
KIT – University of the State of Baden-Wuerttemberg and National Research Center of the Helmholtz Association www.kit.edu

I declare that I have developed and written the enclosed thesis completely by myself, and
have not used sources or means without declaration in the text.
I followed the rules for securing a good scientic pracise of the Karlsruhe Institute of
Technology (Regeln zur Sicherung guter wissenschaftlicher Praxis im Karlsruher Institut
fur Technologie (KIT)).
Karlsruhe, 15.01.2019
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
(Dumitru-Cristian Albu )

Contents
Abstract vii
1 Introduction 1
2 Concepts of NLP 3
2.1 Grammar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Syntax and semantic analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 "Understanding" from computer view . . . . . . . . . . . . . . . . . . . . . . 3
3 Examples of Smart Systems 5
3.1 Early stage (from 1950 to around 1980) . . . . . . . . . . . . . . . . . . . . 5
3.1.1 ELIZA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.1.2 NLC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 The second stage (from around 1980 to early 2000's) . . . . . . . . . . . . . 8
3.3 Current research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4 Conclusion 9
Bibliography 11
Glossary 13
v

Abstract
My Abstact
vii

Chapter 1
Introduction
Today we see around us a multitude of systems that we dene as intelligent ones. Following
the reasoning behind the Turing Test, developed in 1950 by Alan Turing, a machine or a
system could be considered intelligent if it could "exhibit intelligent behaviour equivalent
to, or indistinguishable from, that of a human"[Wik18a]. Let us take a look at the following
actions: we talk to a virtual assistant on the phone to schedule a meeting for us, we ask the
car's infotainment system for direction to the nearest supermarket and we receive all of this
annoying ads about products we discussed in our home near a voice-controlled speaker.
What have all of this things in common? We are not doing anything out of the ordinary, we
still communicate in natural languages, but the machines understands us and our needs,
goals and motivations better and better. All of these systems and many more use Natural
Language Processing(further as NLP) to some extent to "understand". NLP is "a subeld
of computer science, information engineering, and articial intelligence concerned with
the interactions between computers and human (natural) languages, in particular how
to program computers to process and analyze large amounts of natural language data.
Challenges in natural language processing frequently involve speech recognition, natural
language understanding, and natural language generation"[Wik18b] and was born in 1950
when Waren Waver, director of natural science for the Rockefeller Foundation, distributed
a memorandum with the rst idea of an worldwide useful machine-translation system,
"Computers had been used to break codes during the war, so why not translation?", he
wrote. The idea behind was that every language submits to some yet to be discovered
rule, and so every language is just o coding of dierent symbols. The history had shown
that a solution to the worldwide translation problem is just more complicated than just
a decoding algorithm, and from 1966 all the funds were to be terminated. Only NLP
had to win after that, because in the same report that concluded the termination of fund
for machine-translation it was stated that further research to be done to develop system
to understand natural language[WAL84]. In this paper we propose three main stages in
the research done on NLP based on elements such as approaches and technologies used
in developing the systems. The early stage represents the period of time from 1950 to
around 1980 when the programs would only look to match a hard-coded template using
keywords in "stereotyped sentence structures, and then gave back an equally stereotyped
1

2 1 Introduction
response"[WAL84]. The second stage is when the progress was very low and mainly NLP
future started to look a lot like the machine-translation mentioned above. The last stage
is the current research in this eld, based nowadays on Neural Networks.

Chapter 2
Concepts of NLP
In order to understand the systems described in Chapter 3, we need rst a short introduc-
tion in some of the processes of NLP or parts on which is built.
2.1 Grammar
In linguistics, grammar is the set of structural rules governing the composition of clauses,
phrases, and words in any given natural language.[Wik19] Noam Chomsky proposed that
the human brain contains a specialized universal grammar that allow us to learn our native
language. "In conversations, sequences of words are just the tip of the meaning iceberg,
and it is unlikely that a general method run over the surface words in communication could
capture the depth of language. Language allows for innite combinations of concepts, and
any training set, no matter how large, will represent only a nite subset"[Mug17].
2.2 Syntax and semantic analysis
A system must extract, from the input, information about the given request in natural
language in order to process it. As stated in Section 2.1, every natural language has a
grammar and can undergo syntax and semantic analysis. Syntax refers to the grammatical
structure and semantics to the meaning of the symbols arranged with that structure. It is
worth noting that a valid syntax input does not imply a semantically valid one.
2.3 "Understanding" from computer view
"Language is more than words; "meaning" depends on context, and "understanding" re-
quires a vast body of knowledge about the world"[WAL84]. This concept is important
to the understanding of evolution of intelligent systems and NLP because together with
grammar are the foundation and of this kind of systems, and also the reason why, as dis-
cussed in Chapter 4, more research is needed to be done to obtain models of our world
closer to reality in ways computers can understand and learn from, as we do as we grow
up.
3

Chapter 3
Examples of Smart Systems
As discussed in Chapter 1, we propose in this paper three main stages in the evolution of
intelligent systems and NLP. In the following we will talk about each stage individually
and give examples of the notable work done than.
3.1 Early stage (from 1950 to around 1980)
The early stage represents the time when most of the research on NLP was focused on
writing a program that "understands" natural languages, meaning they could respond
accordingly to an input phrase. The understanding was done with the help of template
matching, and the dialogue was purely a stimulus-input action. Even today, many chatbots
are still using this technique. Due to computational limitations, the researchers tried to
achieve this by "hard-coding our world into computers", meaning that the program will
solely search for the highest ranking keyword or that the input will be separated into
meaningless tokens that correspond to words and punctuation; this keywords or tokens
serve as the basis of the manually created representations of our world when we assign
meaning to them.
3.1.1 ELIZA
The paper [Wei66] is about one of the most intriguing programs that made conversations
with a computer using natural language possible because "it was so good at imitating a
nondirective psychotherapist that people would quickly nd themselves sharing intimate
details of their lives with the computer." The program used a SCRIPT that fed ELIZA
with the keywords, rules for decomposition and how to respond. According to the paper,
the ve technical problems with which ELIZA was concerned were: (1) the identication
of keywords, (2) the discovery of minimal context, (3) the choice of appropriate transfor-
mations, (4) generation of responses in absence of keywords, and (5) the provision of an
editing capability for ELIZA SCRIPTS .
The innovation behind ELIZA was that the SCRIPT was not part of the program itself,
rather a data le from which the program gathered the directives. In result, SCRIPTS
in Welsh, German and English were present. Also the mechanism of cycling through the
5

6 3 Examples of Smart Systems
Figure 3.1: A snippet from a dialogue between Eliza and an user
reassembly rules of a frequent keyword leaved the impression on users of an actual person
responding to their input.
But ELIZA had also limitation due to the keyword mechanism implemented. Because in
Figure 3.2: The data structure for a keyword containing decomposition and reassembly
rules
a left-to-right scanning all the lower ranking keywords were not taken into consideration,
the process of nding a minimum context in the input text for more complicating phrases,
and so the program responded to only a small information contained in input. This was
remarked because in absence of a memory to save past interaction, in a dead-end, ELIZA
could not go back to extract more information about the user which was neglected because
of the lower rank of keywords. The program also did not include a clever mechanism to
predict and correct misspelled words, it just copied them back into the response, problems
appearing when the misspelled word was the highest ranking keyword in the input.
3.1.2 NLC
In 1979, towards the end of the rst proposed stage, Bruce W. Ballard and Alan W.
Biermann published the paper [BB79]. They proposed NLC as a prototype "designed to
process data stored in matrices or tables, and any problem which can be represented in
such structured can be handled if the total storage requirements are not excessive". An
application would be to solve linear equations systems providing an example on how it
is done using only natural language. Even if at it's core NLC is just another hard-coded
template matching program as ELIZA, it was more advanced, for example, in processing
the input, where more linguistic advanced mechanism were used to retrieve information.
To demonstrate the usability of a such system, it was proposed a case-scenario where an
instructor would have the names of the students and their grades in a table stored and
would request to the program to calculate the nal average for them.

3.1 Early stage (from 1950 to around 1980) 7
Figure 3.3: A snippet from a dialogue between NLC and an instructor
One of the reasons why NLC is interesting to be studied is the modularity of the system.
It had four dierent stages of processing as follows: (1) the input is scanned and splitted
into tokens and possible meanings are searched for every one of them into an enhanced
dictionary, this way dealing also with misspelled words; (2) the output is sent directly
to the syntax analyzer, where the structure of the user's request is determined using the
grammar of the program in the form of transition networks(see gure 3.4); (3) with the
meanings dened and the structure found, the role of the semantics analyzer in the third
stage is to determine the mentioned entities, and to retrieve them from the table; (4)
the last stage also called "Matrix Computer" has the task of updating the screen, so the
user can have a feedback on what is going to change based on his input command, to
establish the order of operation and to execute them. Some of the limitations of this
prototype were that it understood only the domain of matrices and the principal nouns
of it, therefor it remained unknown for the machine the user's goal beside manipulating
entities in tables. Another one is due to the ambiguity of the language itself, especially the
structural ambiguity, because even if for the user was clear what he was trying to achieve,
the program needed to use a rule to select the possible meaning when dealing with this
kind of ambiguity. NLC was also not great in dealing with control structures common to
many algorithms like (a) loops and (b) conditional execution. If the conditional execution
was not supported, loops were possible with rstly instructing the program to execute
the operation on a single entity and after that to repeat it to all the other desired ones.
NLC had also the possibility of storing self-dened functions to be called later, but this
introduced also a level of ambiguity.
Figure 3.4: Simplied version of the NLC's grammar network

8 3 Examples of Smart Systems
3.2 The second stage (from around 1980 to early 2000's)
In this period were no major breakthrough due to limited in NLP due to the limitations of
the grammars used in this systems. As discussed in Section 2.1, the role of the grammar
was crucial. There were many attempts to elaborate "non-Chomskian grammatical theories
that are both psychological realistic and computable". One of those worth of being here
noted is the Lexical Functional Grammar(LFG) developed by Roland Kaplan and Joan
Bresnan at the Xerox Palo Alto Research Center. This grammar presents a formalism to
represent the syntactic knowledge of a native speaker. It did not concerned itself directly
with the ordering of words or phrase structure, but with the functional roles. It was appre-
ciated to be "intuitive, elegant, and mathematically tractable"[WAL84][KB82]. Another
remarkable moment of this stage was when the Center for the Study of Language and In-
formation(CSLI) was founded in 1983 at Stanford. It is considered "the rst real attempt
of maintaining a dialogue among allthe language-related elds"[WAL84] like linguistics,
philosophy, AI, computer science, and psychology. As it was proven by later develop-
ments, an important step in building truly intelligent system is to have a pluridisciplinary
understanding of the mentioned language-related elds above.
3.3 Current research
With the growing capabilities of Articial Intelligence based on Neural Networks in the
2000's, NLP resurfaced as a subject of interest for researchers. The most notable devel-
opments were made on machine-translation systems, the subject that started the research
in 1950. For example, Google's Neural Machine Translation System(GNMT) released in
2016 is approaching the level of human translation on some languages, and even has capa-
bilities to translate between two languages that were never trained together like Japanese-
Korean[WSC+16]. Another example are the capabilities of current virtual assistants in
speech recognition like Google Assistant or Siri. This developments were possible since the
apparition on a large scale of good encoding-decoding models based on Neural Networks,
for example, RNN for machine translation(see gure 3.5), CNN for image recognition, but
exactly this generality of the models represents the limitation for use as language under-
standing agents. The approach on natural language processing has changed in a few ways,
one of it being that now deep learning obtained high performance on dierent NLP tasks
with usage of RNN or LSTM.
Figure 3.5: Simplied version of the GNMT's RNN

Chapter 4
Conclusion
In this seminar paper I reviewed some of the rst papers in the eld of NLP and also
current research in order to obtain an overview of the evolution of this pluridisciplinary
eld that is the foundation of the interaction between people and machines. The separation
in three stages was made with the scope of delimiting dierent approaches on this subject
and to show that more is needed to be done. The last few years have showed that more
research is done into this eld and NLP is an important part of Articial Intelligence. In
conclusion, this papers presents the evolution timeline with examples that demonstrate
the innovation and where the problems were, or in case of how to make the computers
to understand our world, still are. "Our language evolved not to describe our world as it
is but rather to communicate only what the listener does not already know"[Mug17], and
in order to explain that to the computers we must nd a way to teach them every basic
thing.
9

Bibliography
[BB79] B. W. Ballard and A. W. Biermann, \Programming in natural language," in
Proceedings of the 1979 annual conference on – ACM 79 . ACM Press, 1979.
[KB82] R. M. Kaplan and J. Bresnan, \Lexical-functional grammar: A
formal system for grammatical representation," 1982. [Online]. Available:
https://books.google.de/books?id=5QEplKuY-x8C&lpg=PA29&dq=lexical%
20functional%20grammar&lr&hl=ro&pg=PA29#v=onepage&q=lexical%
20functional%20grammar&f=false
[Mug17] J. Mugan, \The two paths from natural language processing to articial intelli-
gence," Feb. 2017. [Online]. Available: https://medium.com/intuitionmachine/
the-two-paths-from-natural-language-processing-to-articial-intelligence-d5384ddbfc18
[WAL84] M. M. WALDROP, \Natural language understanding: Language is more than
words "meaning"depends on context, and "understanding"requires a vast body
of knowledge about the world," Science , vol. 224, no. 4647, pp. 372{374, apr
1984.
[Wei66] J. Weizenbaum, \ELIZA|a computer program for the study of natural lan-
guage communication between man and machine," Communications of the
ACM , vol. 9, no. 1, pp. 36{45, jan 1966.
[Wik18a] Wiki, \Turing test," Dec. 2018. [Online]. Available: https://en.wikipedia.org/
wiki/Turing test
[Wik18b] Wikipedia, \Natural language processing," Dec. 2018. [Online]. Available:
https://en.wikipedia.org/wiki/Natural language processing
[Wik19] Wikipedi, \Grammar," Jan. 2019. [Online]. Available: https://en.wikipedia.
org/wiki/Grammar
[WSC+16] Y. Wu, M. Schuster, Z. Chen, Q. V. Le, M. Norouzi, W. Macherey, M. Krikun,
Y. Cao, Q. Gao, K. Macherey, J. Klingner, A. Shah, M. Johnson, X. Liu,
A,Aukasz Kaiser, S. Gouws, Y. Kato, T. Kudo, H. Kazawa, K. Stevens,
G. Kurian, N. Patil, W. Wang, C. Young, J. Smith, J. Riesa, A. Rudnick,
O. Vinyals, G. Corrado, M. Hughes, and J. Dean, \Google's neural machine
translation system: Bridging the gap between human and machine translation,"
2016.
11

Glossary
CNN Convolutional Neural Network.
LSTM Long-Short-Term-Memory.
NLP Natural Language Processing.
RNN Recurrent Neural Network.
tokens With the exception of punctuation.
13