Welcome To Sora Park

Natural Language Processing (NLP) is informed by a number of perspectives (disciplines contribute to NLP):

• Computer/data science
  • Theoretical foundation of computation and practical techniques for implementation
• Information science
  • Analysis, classification, manipulation, retrieval and dissemination of information
• Computational Linguistics
  • Use of computational techniques to study linguistic phenomena
• Cognitive science
  • Study of human information processing (perception, language, reasoning, etc.)

NLP adopts multiple paradigms:

• Symbolic approaches
  • Rule-based, hand coded (by linguists/subject matter experts)
  • Knowledge-intensive
• Statistical approaches
  • Distributional & neural approaches, supervised or unsupervised
  • Data-intensive

NLP applications:

• Text categorisation
  • Media monitoring
    • Classify incoming news stories
  • Search engines
    • Classify query intent, e.g. search for 'LOG313'
  • Spam detection
• Machine translation
  • Fully automatic, e.g. Google translate
  • Semi-automated
    • Helping human translators
• Text summarisation
  : to manage information in overload, we need to abstract it down to the most important elements or summarise it
  • Summarisation
    • Single-document vs. multi-document
  • Search results
  • Word processing
  • Research/analysis tools
• Dialog systems
  • Chatbots
  • Smartphone speakers
  • Smartphone assistants
  • Call handling systems
    • Travel
    • Hospitality
    • Banking
• Sentiment Analysis
  : identify and extract subjective information
  
  • Several sub-tasks:
    • Identify polarity
      e.g. of movie reviews
      e.g. positive, negative, or neutral
    • Identify emotional states
      e.g. angry, sad, happy, etc
    • Subjectivity/objectivity identification
      e.g. “fact” from opinion
    • Feature/aspect-based
      : differentiate between specific features or aspects of entities
• Text mining
  • Analogy with Data Mining
    • Discover or infer new knowledge from unstructured text resources
  • A<->B and B<->C
    • Infer A<->C?
      e.g. link between migraine headaches and magnesium deficiency
  • Applications in life sciences, media/publishing, counter terrorism and competitive intelligence
• Question answering
  • Going beyond the document retrieval paradigm
    : provide specific answers to specific questions
• Natural language generation
• Speech recognition & synthesis

…and lots more

History of NLP

• Foundational Insights: 1940s and 1950s
  • Two foundational paradigms:
    1. The automaton, which is the essential information processing unit
    2. Probabilistic or information-theoretic models
  • The automaton arose out of Turing’s (1936) model of algorithmic computation
    • Chomsky (1956) considered finite state machines as a way to characterise a grammar
      : he was one of the first people to use these ideas
  • Shannon (1948) borrowed the concept of entropy from thermodynamics
    : Entropy is a measure of uncertainty (as entropy approaches 1.0, uncertainty increases)
    
    • As a way of measuring the information content of a language
    • Measured of the entropy of English by using probabilistic techniques based on the concept of entropy
• Two camps: 1960s and 1970s
  • Speech and language processing split into two paradigms:
    1. Symbolic:
         - Chomsky and others on parsing algorithms
         - Artificial intelligence (1956) work on reasoning and logic
         - Early natural language understanding (NLU) systems:
              - Single domains pattern matching
              - Keyword search
              - Heuristics for reasoning
    2. Statistical (stochastic)
         - Mosteller and Wallace (1964) applied Byesian methods to the problem of authorship attribution on The Federalist Papers
• Early NLP systems
  : ELIZA and SHRDLU were the highly influential early NLP systems
  
  • ELIZA
    •  Wiezenbaum 1966
    • Pattern matching (ELIZA used elementary keyword spotting techniques)
    • First chatbot
      

      

  •  SHRDLU
    • Winograd 1972
    • Natural language understanding
    • Comprehensive grammar of English
      

      

      They created this imaginary world called the block’s world (simulated a robot embedded in a world of toy blocks). The user could interact with this block’s world by asking questions and giving commands.
  • Further developments in the 1960s
    • First text corpora (corpora is plural of corpus)
      • The Brown corpus: a one-million-word collection of samples from 500 written texts from different genres (newspaper, novels, non-fiction, academic, etc.), assembled at Brown University in 1963-64 (Kuˇcera and Francis, 1967; Francis, 1979; Francis and Kuˇcera, 1982), and William S. Y. Wang’s 1967 DOC (Dictionary on Computer)
  • Empiricism: 1980s and 1990s
    : The rise of the WWW emphasised the need for language-based information retrieval and information extraction.
    
    • The return of two classes of models that had lost popularity:
      1. Finite-state models:
           - Finite-state morphology by Kaplan and Kay (1981) and models of syntax by Church (1980)
      2. Probabilistic and data-driven approaches:
           - From speech recognition to part-of-speech tagging, parsing and semantics
    • Model evaluation
      • Quantitative metrics, comparison of performance with previous published research
      • Regular competitive evaluation exercises such as the Message Understanding Conferences (MUC)
  • The rise of machine learning: 2000s
    : Large amounts of spoken and written language data became available, including annotated collections
    e.g. Penn Treebank (Marcus et al. 1993)
    • Traditional NLP problems, such as parsing and semantic analysis, became problems for supervised learning
    • Unsupervised statistical approaches began to receive renewed attention
      • Statistical approaches to machine translation (Brown et al., 1990; Och and Ney, 2003) and topic modelling (Blei et al., 2003) demonstrated that effective applications could be constructed from systems trained on unannotated data
      • Cost and difficulty of producing annotated corpora became a limiting factor for supervised approaches
  • Ascendance of deep learning: 2010s onwards
    • Deep learning methods have become pervasive in NLP and AI in general
      • Advances in technology such as GPUs developed for gaming
      • Plummeting costs of memory
      • Wide availability of software platforms
    • Classic ML methods require analysts to select features based on domain knowledge
      • Deep learning introduced automated feature engineering: generated by the learning system itself
    • Collobert et al (2011) applied convolutional neural nets (CNNs) to POS tagging, chunking, NE tags and language modelling
      • CNNs unable to handle long-distance contextual information
    • Recurrent neural networks (RNNs) process items as a sequence with a "memory" of previous inputs'
      : The method is very useful for what we call sequence labelling tasks.
      • Applicable to many tasks such as:
        
        • Word-level: named entity recognition, language modelling
        • Sentence-level: sentiment analysis, selecting responses to messages
        • Language generation for machine translation, image captioning, etc.

RNNs are supplemented with long short-term memory (LSTM) or gated recurrent units (GRUs) to improve training performance (the 'vanishing gradient problem').

Deep neural networks do the input-to-target mapping via a deep sequence of simple data tranformations (layers). This transformation implemented by a layer is parameterised by its weights. Weights are also sometimes called the parameters of a layer.

• Learning means finding a set of values for the weights of all layers in a network.

The network will correctly map the inputs to their associated targets only if the weights are reasonable.

• To control the output of a neural network, we need to be able to measure how far this output is from what we expected. This is the job of the loss function of the network. The loss function is also sometimes called the objective function or cost function.

The loss function takes the predictions of the network and the true target and computes a distance score, capturing how well the network has done.

The fundamental trick in deep learning is to use this score as a feedback signal to adjust the value of the weights a little, in a direction that will lower the loss score. This adjustment is the job of the optimiser, which implements what's called the backpropagation algorithm, which is the central algorithm in deep learning.

With every example the network processes, the weights are adjusted a little in the correct direction, and the loss score decreases. This is the training loop.

헵 규칙 (Hebb rule) 은 최초의 신경망 학습 규칙 중 하나로, 1949년 도널드 헵 (Donald O. Hebb) 이 뇌의 시냅스 변형 메커니즘으로 제안한 이후로 인공 신경망 훈련에 사용되고 있다.

당시 헵이 집필한 'The Organization of Behavior' 책에는 헵 학습으로 알려진 가정 (공리) 이 있다.

세포 A의 축삭이 세포 B를 자극하기에 충분히 가깝고 B를 발화하는 데 반복적 또는 지속적으로 참여할 때, 한쪽 또는 양쪽 세포에 일종의 성장 과정이나 신진대사의 변화가 일어남으로써 B를 발화하는 세포 중 하나로서 A의 효율이 올라간다.

헵 학습 규칙은 다양한 신경망 구조와 결합해서 사용할 수 있다. 예를 들어 선형 연상 메모리 (linear associator) 가 있다.

이는 연상 메모리 (associative memory) 라고 하는 신경망 종류의 한 예로, 연상 메모리의 작업은 프로토타입 입력/출력 벡터의 Q개 쌍을 학습하는 것이다.

$$ \{p_1,t_1\}, \{p_2,t_2\}, ... , \{p_Q,t_Q\} $$

네트워크가 입력 p를 받으면 출력 t를 생성해야 하는데, 입력이 바뀌면 출력도 약간 바뀌어야 한다.

시냅스 양쪽에 있는 두 뉴런이 동시에 활성화되면 시냅스의 강도는 증가하게 될 것이다.

• 위 그림에서 입력 p와 출력 a의 연결 (시냅스) 은 가중치 w이다.

헵의 가정은 양의 p가 양의 a를 생성한다면 w가 증가해야 한다는 것을 의미한다. 수학적 해석은 아래와 같다.

• p는 q번째 입력 벡터의 j번째 요소
• a는 q번째 입력 벡터가 네트워크에 제시될 때 네트워크 출력의 i번째 요소
• 알파는 양의 상수이며, 학습률 (learning rate) 이라고 부름

이 식은 가중치 w의 변화가 시냅스 양쪽의 활성 함수의 곱에 비례한다는 사실을 말해준다.

참고로 이 식에 정의된 헵 규칙은 비지도 학습 (unsupervised learning) 규칙이므로, 목표 출력에 관련된 정보가 필요 없다. 지도 (supervised) 헵 규칙에서는 실제 출력을 목표 출력으로 대체할 수 있다.

이 방법은 알고리즘에게 '네트워크가 현재 하고 있는 것'이 아닌 '네트워크가 해야만 하는 것'을 알려준다.

• t는 q번째 목표 벡터 t의 i번째 요소
• 학습률은 1로 설정

벡터 표기법은 아래와 같다.

$$ W^N=W^O+t_qp_q^T $$

가중치 행렬을 0으로 초기화하고 Q개의 입력/출력 쌍을 한번에 적용하면 아래와 같이 작성할 수 있다.

$$ W=t_1p_1^T+t_2p_2^T+ ... +t_QP_Q^T=\sum_{q=1}^{Q}t_qp_q^T $$

이 식은 행렬 방식으로 표현될 수 있다.

$$ W=\begin{bmatrix}
t_1 & t_2 & ... & t_Q \\
\end{bmatrix}\begin{bmatrix}
p_1^T \\ p_2^T \\ ... \\ p_Q^T
\end{bmatrix}=TP^T $$

여기서

$$ T=\begin{bmatrix}
t_1 & t_2 & ... & t_Q \\
\end{bmatrix}, P=\begin{bmatrix}
p_1 & p_2 & ... & p_Q \\
\end{bmatrix} $$

선형 연상 메모리에 대한 헵 학습의 성능 분석 시 프로토타입 벡터 (p_q) 가 직교하면서 단위 길이를 갖는 정규직교 (orthonormal) 인 경우와 단위 길이를 갖지만 직교하지 않는 경우를 나눠서 살펴볼 수 있다.

1. 정규직교인 경우:
   p_k 가 네트워크 입력이면 네트워크 출력은 다음과 같이 계산된다.
   $$ a=Wp_k=(\sum_{q=1}^{Q}t_qp_q^T)p_k=\sum_{q=1}^{Q}t_q(p_q^Tp_k) $$
   p_q 가 정규직교이기 때문에 다음과 같이 된다.
   $$ (p_q^Tp_k)=1, q=k $$
   $$ (p_q^Tp_k)=0, q!=k $$
   Identity matrix 가 되기 때문에 네트워크 출력은 다음과 같이 간단하게 작성될 수 있다.
   $$ a=Wp_k=t_k $$
2. 단위 길이이지만, 직교가 아닌 경우:
   벡터가 직교하지 않기 때문에 네트워크는 정확한 출력을 생성하지 않을 것이며, 오차의 크기는 프로토타입 입력 패턴 사이에 상관 관계의 크기에 따라 달라진다.
   $$ a=Wp_k=t_k+\sum_{q!=k}^{}t_q(p_q^Tp_k) $$
   우항의 시그마는 오차를 나타낸다.

예제 1) 입력 벡터가 정규직교일 때

$$ p_1=\begin{bmatrix}
0.5 \\ -0.5 \\ 0.5 \\ -0.5
\end{bmatrix}, t_1=\begin{bmatrix}
1 \\ -1
\end{bmatrix}  $$

$$ p_2=\begin{bmatrix}
0.5 \\ 0.5 \\ -0.5 \\ -0.5
\end{bmatrix}, t_2=\begin{bmatrix}
1 \\ 1
\end{bmatrix} $$

가중치 행렬:

$$ W=TP^T=\begin{bmatrix}
1 & 1 \\
-1 & 1 \\
\end{bmatrix}\begin{bmatrix}
0.5 & -0.5 & 0.5 & -0.5 \\
0.5 & 0.5 & -0.5 & -0.5 \\
\end{bmatrix}=\begin{bmatrix}
1 & 0 & 0 & -1 \\
0 & 1 & -1 & 0 \\
\end{bmatrix} $$

각각의 프로토타입 입력에 대한 가중치 행렬 테스트 결과:

$$ Wp_1=\begin{bmatrix}
1 & 0 & 0 & -1 \\
0 & 1 & -1 & 0 \\
\end{bmatrix}\begin{bmatrix}
0.5 \\ -0.5 \\ 0.5 \\ -0.5 \\
\end{bmatrix} =\begin{bmatrix}
1 \\ -1
\end{bmatrix} $$

$$ Wp_2=\begin{bmatrix}
1 & 0 & 0 & -1 \\
0 & 1 & -1 & 0 \\
\end{bmatrix}\begin{bmatrix}
0.5 \\ 0.5 \\ -0.5 \\ -0.5 \\
\end{bmatrix}=\begin{bmatrix}
1 \\ 1
\end{bmatrix} $$

네트워크 출력이 목표와 동일하다는 것을 알 수 있다.

예제 2) 입력 벡터가 직교하지 않을 때

$$ p_1=\begin{bmatrix}
1 \\ -1 \\ -1
\end{bmatrix},
p_2=\begin{bmatrix}
1 \\ 1 \\ -1
\end{bmatrix} $$

두 프로토타입 입력을 정규화하고 희망 출력을 -1과 1로 각각 선택하면 다음과 같다.

$$ p_1=\begin{bmatrix}
0.5774 \\ -0.5774 \\ -0.5774
\end{bmatrix}, t_1=\begin{bmatrix}
-1
\end{bmatrix} $$

$$ p_2=\begin{bmatrix}
0.5774 \\ 0.5774 \\ -0.5774
\end{bmatrix}, t_2=\begin{bmatrix}
1
\end{bmatrix} $$

가중치 행렬:

$$ W=TP^T=\begin{bmatrix}
-1 & 1
\end{bmatrix}\begin{bmatrix}
0.5774 & -0.5774 & -0.5774 \\
0.5774 & 0.5774 & -0.5774 \\
\end{bmatrix}=\begin{bmatrix}
1 & 1.1548 & 0
\end{bmatrix} $$

두 프로토타입 패턴을 가중치 행렬과 곱하면 다음과 같다.

$$ Wp_1=\begin{bmatrix}
0 & 1.1548 & 0
\end{bmatrix}\begin{bmatrix}
0.5774 \\ -0.5774 \\ -0.5774
\end{bmatrix} =\begin{bmatrix}
-0.6668
\end{bmatrix} $$

$$ Wp_2=\begin{bmatrix}
0 & 1.1548 & 0
\end{bmatrix}\begin{bmatrix}
0.5774 \\ 0.5774 \\ -0.5774
\end{bmatrix} =\begin{bmatrix}
0.6668
\end{bmatrix} $$

출력이 목표 출력과 일치하지 않는다.

단일 입력 뉴런 (Single input neuron)

입력이 1개인 뉴런

a = f(w * p + b)

• a: 뉴런 출력 (축삭 신호)
• p: 입력 (Scala or Matrix)
• bias: 또 다른 입력의 편향
• weight: 가중치 (시냅스 강도)
• f: 전달/활성 함수

예를 들어 weight = 3, p = 2, b = -1.5 일 때, a = f(3 * 2 - 1.5) = f(4.5) 로 출력된다.

다중 입력 뉴런 (Multiple input neuron)

입력이 2개 이상인 뉴런

a = f(W * p + b)

• Weight: 가중치 행렬

개별 입력 p1, p2,... 에 대응하는 각각의 가중치 w 존재

일 때 

로 표현할 수 있다.

계층

• 출력 계층 (output layer)
• 은닉 계층 (hidden layer)

• 순환 계층 (recurrent layer)

순환망 (recurrent network) 은 피드백이 있는 네트워크이므로, 피드포워드 (feedforward) 네트워크보다 강력하며 시간적 행동을 보여줄 수 있다.

전달함수 종류

1. 하드 리밋 (Hard Limit)

2. 대칭 하드 리밋 (Symmetrical Hard Limit)

3. 선형 (Linear)

4. 포화 선형 (Saturating Linear)

5. 대칭 포화 선형 (Symmetric Saturating Linear)

6. 로그-시그모이드 (Log-Sigmoid)

7. 하이퍼볼릭 탄젠트 시그모이드 (Hyperbolic Tangent Sigmoid)

8. 양의 선형 (Positive Linear)

9. 경쟁 (Competitive)

입력 2개의 뉴런 파라미터가 $$ b=1.2, W=\begin{bmatrix}
3 & 2 \\
\end{bmatrix}, p=\begin{bmatrix}
-5 & 6 \\
\end{bmatrix}^T $$ 인 경우 네트 입력은 $$ n=Wp+b=\begin{bmatrix}
3 & 2 \\
\end{bmatrix}\begin{bmatrix}
-5 \\ 6
\end{bmatrix}+(1.2)=-1.8 $$ 로 계산되고, 뉴런 출력은

• 대칭 하드 리밋 전달 함수: $$ a=hardlims(-1.8)=-1 $$
• 포화 선형 전달 함수: $$ a=satlin(-1.8)=0 $$
• 하이퍼볼릭 탄젠트 시그모이드 전달 함수: $$ a=tansig(-1.8)=-0.9468 $$

등으로 구할 수 있다.

피드포워드 네트워크의 이진 패턴 인식에는 경계 값에 따라 분류를 하는 과정에서 애매한 경우 정확도가 떨어질 수 있는 문제가 있다. 이를 보완한 것이 해밍 (hamming) 네트워크와 홉필드 (hopfield) 네트워크이다.

해밍 네트워크는 피드포워드 계층과 순환 계층을 모두 이용한다.

피드포워드 계층에서는 프로토타입 벡터와 입력 벡터의 닮음 정도 (내적) 에 편향 벡터를 더해 값이 절대 음수가 되지 않게 함으로써 순환 계층이 적절히 작동하도록 한다. 순환 계층은 경쟁 계층으로, 피드포워드 계층 출력에 가중 행렬을 곱하는 과정을 반복한다. 가중 행렬은 아래와 같은 형태를 갖는다.

$$ W^2=\begin{bmatrix}
1 & -\varepsilon  \\
-\varepsilon  & 1 \\
\end{bmatrix} $$ 

Epsilon은 1/(S-1)보다 작은 숫자이며, S는 순환 계층에서 뉴런의 수다.

그림과 같이 포드피워드 계층 출력과 가중 행렬의 내적을 구하게 되면, 각 요소는 다른 요소의 동일 비율만큼 감소하게 된다.

• 큰 요소는 작게 감소하고 작은 요소는 크게 감소함으로써 큰 요소와 작은 요소 간의 차이가 커질 것이다.

순환 계층의 효과는 가장 큰 값 (입력과 해밍 거리가 가장 가까운 프로토타입 패턴에 해당) 을 갖는 뉴런을 제외하고 모든 뉴런은 0을 출력한다.

해밍 네트워크는 선택한 프로토타입 패턴을 출력이 0이 아닌 뉴런으로 나타내는 반면, 홉필드 네트워크는 선택한 프로토타입 패턴을 출력한다.

홉필드 네트워크는 입력 벡터로 뉴런을 초기화하며 출력이 수렴될 때까지 반복한다. 해밍 네트워크는 피드포워드 계층의 가중치가 프로토타입 패턴이었던 반면, 홉필드 네트워크는 가중치 형렬과 편향 벡터를 설계해야 하기 때문에 비교적 복잡하게 느껴진다.