0. 설치 환경

OS: Ubuntu 20.04 JDK: OpenJDK 11.0.18 Hadoop: Hadoop 3.3.0

1. JDK 설치

Hadoop은 Java 언어로 쓰여 있어 이를 실행하기 위한 Java runtime이 필요 이전 버전까지는 JDK 8 버전만 지원했으나, Hadoop 3.3 이후로 JDK 11 버전도 지원

1.1. JDK 설치

설치 가능한 패키지 리스트 최신화 후, OpenJdk 11 설치 (Oracle JDK 설치해도 무방 - 라이선스 확인 필요)

$ sudo apt update 
$ sudo apt install openjdk-11-jdk

1.1. Java 버전 체크

아래와 같이 자신이 설치한 버전이 출력되는지 체크

$ java -version
openjdk version "11.0.18" 2023-01-17
OpenJDK Runtime Environment (build 11.0.18+10-post-Ubuntu-0ubuntu120.04.1)
OpenJDK 64-Bit Server VM (build 11.0.18+10-post-Ubuntu-0ubuntu120.04.1, mixed mode, sharing)

2. Hadoop 계정 추가

보안상 계정을 분리하는게 좋기 때문에 새 계정을 추가 계정 이름을 hadoop으로 설정

$ sudo adduser hadoop
Adding user `hadoop' ...
Adding new group `hadoop' (1002) ...
Adding new user `hadoop' (1002) with group `hadoop' ...
Creating home directory `/home/hadoop' ...
Copying files from `/etc/skel' ...
New password:
Retype new password:
passwd: password updated successfully
Changing the user information for hadoop
Enter the new value, or press ENTER for the default
        Full Name []:
        Room Number []:
        Work Phone []:
        Home Phone []:
        Other []:
Is the information correct? [Y/n] Y

3. SSH 인증키기반 인증 설정

서버간 통신할 때, 매번 암호를 입력하고 들어가는 대신 SSH 인증키를 생성하여 암호 없이 접속하게끔 설정

3.1. SSH 키 생성 및 추가

계정 변경 후 SSH 키를 생성 키 경로는 수정하지 않고 기본값을 그대로 사용

$ su - hadoop 
$ ssh-keygen -t rsa
Generating public/private rsa key pair.
Enter file in which to save the key (/home/hadoop/.ssh/id_rsa):
Created directory '/home/hadoop/.ssh'.
...

생성된 공개키(id_rsa.pub)를 authorized_keys에 추가하고 권한을 바꿔준다

$ cat ~/.ssh/id_rsa.pub >> ~/.ssh/authorized_keys
$ chmod 640 ~/.ssh/authorized_keys

아래의 명령어를 통해 known hosts에 등록

$ ssh localhost
The authenticity of host 'localhost (127.0.0.1)' can't be established.
ECDSA key fingerprint is
...
Are you sure you want to continue connecting (yes/no/[fingerprint])? yes

4. Hadoop 설치

4.1 파일 다운로드 및 확인

hadoop 유저로 계정전환

$ su - hadoop

아래 명령어를 통해 압축 파일 및 해시값 다운

$ wget https://archive.apache.org/dist/hadoop/common/hadoop-3.3.0/hadoop-3.3.0.tar.gz
$ wget https://archive.apache.org/dist/hadoop/common/hadoop-3.3.0/hadoop-3.3.0.tar.gz.sha512

다운 받은 hadoop-3.3.0.tar.gz의 해시값과 hadoop-3.3.0.tar.gz.sha512파일의 내용 비교

$ shasum -a 512 hadoop-3.3.0.tar.gz
9ac5a5a8d29de4d2edfb5e554c178b04863375c5644d6fea1f6464ab4a7e22a50a6c43253ea348edbd114fc534dcde5bdd2826007e24b2a6b0ce0d704c5b4f5b  hadoop-3.3.0.tar.gz
$ cat hadoop-3.3.0.tar.gz.sha512
SHA512 (hadoop-3.3.0.tar.gz) = 9ac5a5a8d29de4d2edfb5e554c178b04863375c5644d6fea1f6464ab4a7e22a50a6c43253ea348edbd114fc534dcde5bdd2826007e24b2a6b0ce0d704c5b4f5b

일치하지 않으면, 받은 파일을 제거하고 네트워크가 안정적인 곳에서 파일을 다시 다운로드 받는다

4.2. Hadoop 설치

4.2.1. 압축해제

다운로드 받은 압축 파일을 압축 해제하고, 심볼릭 링크를 생성

$ tar -xvzf hadoop-3.3.0.tar.gz 
$ ln -s hadoop-3.3.0 hadoop 

4.2.2. 시스템 환경변수 추가

~/.bashrc 파일을 에디터로 열고

$ vim ~/.bashrc

아래 내용을 ~/.bashrc 파일의 제일 밑에 추가

export JAVA_HOME=/usr/lib/jvm/java-11-openjdk-amd64
export HADOOP_HOME=/home/hadoop/hadoop
export HADOOP_INSTALL=$HADOOP_HOME
export HADOOP_MAPRED_HOME=$HADOOP_HOME
export HADOOP_COMMON_HOME=$HADOOP_HOME
export HADOOP_HDFS_HOME=$HADOOP_HOME
export HADOOP_YARN_HOME=$HADOOP_HOME
export HADOOP_COMMON_LIB_NATIVE_DIR=$HADOOP_HOME/lib/native
export PATH=$PATH:$HADOOP_HOME/sbin:$HADOOP_HOME/bin
export HADOOP_OPTS="-Djava.library.path=$HADOOP_HOME/lib/native"

만약, 다른 JDK를 사용하고 있다면, JAVA_HOME 변수만 아래와 같이 수정

export JAVA_HOME=$(dirname $(dirname $(readlink $(readlink $(which java)))))

아래 명령어를 통해 환경변수를 업데이트

$ source ~/.bashrc 

4.2.4. Hadoop 다운로드 링크 만료시

만약, 링크가 만료되어 다운받을수 없다면 아래를 참고

Apache Hadoop Releases page에 접속해서 archive 페이지로 이동

아카이브 페이지로 이동한 뒤, 최근 수정된 Hadoop-3.3.0/ 폴더에 들어간다

hadoop-3.3.0.tar.gz 및 hadoop-3.3.0-src.tar.gz.sha512를 오른쪽 마우스 버튼으로 링크 주소를 복사해 새로운 링크로 교체해서 다운

5. Hadoop 설정

아래 명령어를 실행해서 NameNode와 DataNode 디렉토리를 생성 앞으로 이 디렉토리에 데이터가 저장될 예정

$ mkdir -p ~/hadoopdata/hdfs/namenode 
$ mkdir -p ~/hadoopdata/hdfs/datanode 

/home/hadoop/hadoop/etc/hadoop 경로에는 Hadoop 설정 파일이 존재

• hadoop-env.sh : Hadoop을 실행하는 쉘스크립트 파일
• workers : DataNode 서버 지정
• core-site.xml : HDFS와 MapReduce에서 공통적으로 사용할 정보들을 설정, hdfs-site와 mapred-site의 공통 설정 부분
• hdfs-site.xml : HDFS와 관련된 환경 변수를 설정
• mapred-site.xml : MapReduce의 어플리케이션 환경 설정
• yarn-site.xml : Resource Manager, Node Manager 환경 설정
• yarn-env.sh : YARN을 실행하는 쉘스크립트 파일

여기서 변경할 파일은 hadoop-env.sh, core-site.xml, hdfs-site.xml, mapred-site.xml, yarn-site.xml

5.1. hadoop-env.sh

hadoop-env.sh을 수정해서 Java 경로를 지정

$ vim $HADOOP_HOME/etc/hadoop/hadoop-env.sh 

아래 내용을 hadoop-env.sh 파일의 제일 밑에 추가

export JAVA_HOME=/usr/lib/jvm/java-11-openjdk-amd64

5.2. core-site.xml

$ vim $HADOOP_HOME/etc/hadoop/core-site.xml

아래 내용을 core-site.xml 파일의 configuration 항목을 이렇게 수정

<configuration>
        <property>
                <name>fs.defaultFS</name>
                <value>hdfs://localhost:9000</value>
        </property>
</configuration>

5.3. hdfs-site.xml

$ vim $HADOOP_HOME/etc/hadoop/hdfs-site.xml

아래 내용을 hdfs-site.xml 파일의 configuration 항목을 이렇게 수정

<configuration>
        <property>
                <name>dfs.replication</name>
                <value>1</value>
        </property>

        <property>
                <name>dfs.name.dir</name>
                <value>file:///home/hadoop/hadoopdata/hdfs/namenode</value>
        </property>

        <property>
                <name>dfs.data.dir</name>
                <value>file:///home/hadoop/hadoopdata/hdfs/datanode</value>
        </property>
</configuration>

5.4. mapred-site.xml

$ vim $HADOOP_HOME/etc/hadoop/mapred-site.xml

아래 내용을 mapred-site.xml 파일의 configuration 항목을 이렇게 수정

<configuration>
        <property>
                <name>mapreduce.framework.name</name>
                <value>yarn</value>
        </property>
</configuration>

5.5. yarn-site.xml

$ vim $HADOOP_HOME/etc/hadoop/yarn-site.xml

아래 내용을 yarn-site.xml 파일의 configuration 항목을 이렇게 수정

<configuration>
        <property>
                <name>yarn.nodemanager.aux-services</name>
                <value>mapreduce_shuffle</value>
        </property>
</configuration>

5.6. NameNode 포맷

아래 명령어를 통해 네임노드를 포맷

$ hdfs namenode -format
2023-03-23 14:25:33,758 INFO namenode.NNStorageRetentionManager: Going to retain 1 images with txid >= 0
2023-03-23 14:25:33,760 INFO namenode.FSImage: FSImageSaver clean checkpoint: txid=0 when meet shutdown.
2023-03-23 14:25:33,760 INFO namenode.NameNode: SHUTDOWN_MSG:
/************************************************************
SHUTDOWN_MSG: Shutting down NameNode at data_server01/127.0.1.1
************************************************************/

6. Hadoop 클러스터 실행

NameNode 포맷후 아래 명령어를 통해 Haddop 클러스터 실행

$ start-dfs.sh 
Starting namenodes on [localhost]
Starting datanodes
Starting secondary namenodes [data_server01]

다음, YARN 서비스 실행

$ start-yarn.sh
Starting resourcemanager
Starting nodemanagers

Jps 명령어를 통해 Hadoop 서비스 상태 체크

$ jps
88720 DataNode
89223 ResourceManager
88502 NameNode
89592 NodeManager
89851 Jps
88971 SecondaryNameNode

7. 방화벽 설정

방화벽이 설정되어 있으면 외부에서 접속이 안되므로, 사용하고 있다면 아래 명령어를 통해 포트를 개방

firewall-cmd --permanent --add-port=9870/tcp 
firewall-cmd --permanent --add-port=8088/tcp
firewall-cmd --reload 

8. NameNode 및 Resource Manager 액세스

NameNode 및 Resource Manager 접근은 웹브라우저 상에서 가능

• NameNode (http://name-server-ip:9870)

  

• Resource Manager (http://name-server-ip:8088)

  

외부에서 Namenode와 Resource Manager에 접근을 하지 못한다면 포트포워딩 설정 필요

9. Hadoop 클러스터 확인

클러스터가 잘 설정되었는지 검증하기 위해 폴더 생성과 업로드가 되는지 확인

아래의 명령어를 통해 2개 폴더를 만들고 잘 생성되었는지 확인

$ hdfs dfs -mkdir /test1
$ hdfs dfs -mkdir /logs 
$ hdfs dfs -ls /
Found 2 items
drwxr-xr-x   - hadoop supergroup          0 2023-03-23 14:44 /logs
drwxr-xr-x   - hadoop supergroup          0 2023-03-23 14:44 /test1

HDFS에 파일 업로드도 잘 수행되는지 확인

아래의 명령어를 통해 시스템 로그를 업로드 후 확인

$ hdfs dfs -put /var/log/* /logs/
$ hdfs dfs -ls /logs/
Found 33 items
-rw-r--r--   1 hadoop supergroup      25656 2023-03-23 15:04 /logs/Xorg.0.log
-rw-r--r--   1 hadoop supergroup      24544 2023-03-23 15:04 /logs/Xorg.0.log.old
-rw-r--r--   1 hadoop supergroup      25437 2023-03-23 15:04 /logs/Xorg.1.log
-rw-r--r--   1 hadoop supergroup      23620 2023-03-23 15:04 /logs/Xorg.1.log.old
-rw-r--r--   1 hadoop supergroup      50226 2023-03-23 15:04 /logs/alternatives.log
drwxr-xr-x   - hadoop supergroup          0 2023-03-23 15:04 /logs/apt
...

NameNode 웹에서도 확인 가능 Utilities → Browse the file system에서 확인 가능

10. Hadoop 클러스터 종료

$ stop-dfs.sh  
$ stop-yarn.sh 

연결 리스트, Linked List는 노드(Node)와 그 노드를 이어주는 링크(Link)를 이용하여 구현한 자료구조이다. 각 노드들은 데이터(data) 링크로 구성되며 링크는 다음번 노드를 가리키는 포인터이다. 노드를 여러개 이어 붙이면 비엔나 소시지와 비슷한 형태로 그려진다.

연결 리스트는 그 연결 구조에 따라, 단일 연결 리스트, 이중 연결 리스트, 순환 연결 리스트(환형 연결 리스트), 청크 리스트로 나눌 수 있다.

여기서는 가장 기본적인 단일 연결 리스트에 대해서만 다루도록 한다.

1.단일 연결 리스트(Singly Linked List)

1.1 자료형 정의

Node와 그 Node간의 연결을 이어주는 LinkedList 클래스에 대한 정의를 먼저 하고, 그에 대한 연산을 다뤄보자.

• Node 클래스

  class Node:
      def __init__(self, item):
          self.data = item
          self.next = None

• LinkedList 클래스

  class LinkedList:
      def __init__(self):
          self.nodeCount = 0
          self.head = None
          self.tail = None

  LinkedList 클래스에는 노드의 갯수를 저장하는 변수인 nodeCount와, 첫번째 노드를 가리키는 head, 그리고 마지막 노드를 가리키는 tail 변수로 정의를 하자.

1.2 연산의 정의

연결 리스트에서 사용하는 연산은 6개로 나눌수 있다.

1. 특정원소 참조
2. 리스트 순회
3. 길이 얻어내기
4. 원소 삽입
5. 원소 삭제
6. 두 리스트 합치기

다른 연산들은 구현이 쉬운 반면, 원소 삽입, 원소 삭제 이 두가지의 경우 구현이 까다롭다.

1.2.1 특정원소 참조

  def getAt(self, pos):
      if pos < 1 or pos > self.nodeCount:
          return None

      i = 1
      curr = self.head
      while i < pos:
          curr = curr.next
          i += 1

      return curr

1.2.2 리스트 순회

  def traverse(self):
      result = []
      curr = self.head
      while curr is not None:
          result.append(curr.data)
          curr = curr.next
      return result

1.2.3 길이 얻어내기

  def getLength(self):
      return self.nodeCount

1.2.4 원소 삽입

  def insertAt(self, pos, newNode):
      if pos < 1 or pos > self.nodeCount + 1:
          return False

      if pos == 1:
          newNode.next = self.head
          self.head = newNode

      else:
          if pos == self.nodeCount + 1:
              prev = self.tail
          else:
              prev = self.getAt(pos - 1)
          newNode.next = prev.next
          prev.next = newNode

      if pos == self.nodeCount + 1:
          self.tail = newNode

      self.nodeCount += 1
      return True

1.2.5 원소 삭제

  def popAt(self, pos):
      if pos < 1 or pos > self.nodeCount:
          raise IndexError

      prev = self.getAt(pos - 1)
      curr = self.getAt(pos)

      if self.nodeCount == 1:
          self.head = None
          self.tail = None
      else:
          if pos == 1:
              self.head = curr.next
          elif pos == self.nodeCount:
              self.tail = prev
              prev.next = None
          else:
              prev.next = curr.next

      self.nodeCount -= 1
      return curr.data

1.2.6 두 리스트 합치기

  def concat(self, L):
      self.tail.next = L.head
      if L.tail:
          self.tail = L.tail
      self.nodeCount += L.nodeCount

2.Dummy node를 추가한 단일 연결 리스트

Dummy node를 추가하면 원소의 삽입과 삭제를 더 깔끔하게 구현할 수 있다.

2.1 자료형 정의

• Node 클래스 (동일)

  class Node:
      def __init__(self, item):
          self.data = item
          self.next = None

• LinkedList 클래스

  class LinkedList:
      def __init__(self):
          self.nodeCount = 0
          self.head = Node(None)
          self.tail = None
          self.head.next = self.tail

2.2 연산의 정의

2.2.1 특정원소 참조

  def getAt(self, pos):
      if pos < 0 or pos > self.nodeCount:
          return None

      i = 0
      curr = self.head
      while i < pos:
          curr = curr.next
          i += 1

      return curr

2.2.2 리스트 순회

  def traverse(self):
      result = []
      curr = self.head
      while curr.next:
          curr = curr.next
          result.append(curr.data)
      return result

2.2.3 길이 얻어내기

  def getLength(self):
      return self.nodeCount

2.2.4 원소 삽입

  def insertAfter(self, prev, newNode):
      newNode.next = prev.next
      if prev.next is None:
          self.tail = newNode
      prev.next = newNode
      self.nodeCount += 1
      return True

  def insertAt(self, pos, newNode):
      if pos < 1 or pos > self.nodeCount + 1:
          return False

      if pos != 1 and pos == self.nodeCount + 1:
          prev = self.tail
      else:
          prev = self.getAt(pos - 1)
      return self.insertAfter(prev, newNode)

2.2.5 원소 삭제

  def popAfter(self, prev):
      if prev.next is None:
          return None

      curr = prev.next

      if curr.next is None:
          self.tail = prev

      prev.next = curr.next
      self.nodeCount -= 1
      return curr.data

  def popAt(self, pos):
      if pos < 1 or pos > self.nodeCount:
          raise IndexError

      prev = self.getAt(pos - 1)
      return self.popAfter(prev)

2.2.6 두 리스트 합치기

  def concat(self, L):
      self.tail.next = L.head.next
      if L.tail:
          self.tail = L.tail
      self.nodeCount += L.nodeCount

Transformer는 Google에서 발표한 기존에 기계번역에 사용하던 RNN을 버리고, 내부에는 Attention으로만 구현한 모델이다.

RNN과 CNN을 사용하지 않고 대신, Positional Encoding을 사용하였고, Encoder와 Decoder로 구조를 설계하고 Attention 과정을 여러 레이어에서 반복하였다.

참고로, GPT는 Transformer의 Decoder 아키텍쳐를 활용하였고, BERT는 Transformer의 Encoder 아키텍쳐를 활용하였다.

Conventional Embedding

전통적인 임베딩(Embedding)은 embedding matrix를 사용하고 이를 RNN에 이용한다.

Transformer의 Embedding

하지만 Transformer의 RNN을 사용하지 않는다. 대신, Positional Encoding을 이용하여 위치정보를 포함하고 있는 임베딩(Embedding)을 사용한다.

Transformer의 인코더(Encoder)와 디코더(Decoder)

임베딩(Embedding)이 끝난 후에 어텐션(Attention)을 진행, 성능 향상을 위해 Residual Learning을 사용한다. 이후, 어텐션(Attention)과 정규화(Normalization) 과정을 반복한다. 각 레이어는 서로 다른 Parameter를 가진다.

1.Transformer의 인코더(Encoder)

2.Transformer의 인코더(Encoder)와 디코더(Decoder)

Transformer에서는 마지막 인코더 레이어의 출력이 모든 디코더 레이어의 입력에 들어간다. 아래는 n_layers = 4일때의 예시이다.

RNN을 사용하지 않는 대신에 인코더와 디코더를 다수 사용한다는 점이 특징이다.

Query, Key, Value

• 어텐션(Attention)을 위해 Query, Key, Value가 필요하다.

• 각 단어의 임베딩(embedding)을 이용하여 생성 할 수 있다.

• 임베딩 차원($d_{model}$) → Query, Key, Value 차원 ($d_{model} / h$)

• 한개의 단어

• 행렬 연산

Multi-Head Attention

Transformer의 인코더와 디코더는 Multi-Head Attention 레이어를 사용한다

• attention을 위한 세가지 요소

  Query - Decoder의 Multi-Head attention

• Key, Value* - Encoder의 출력

• 입력값과 출력값의 demension이 같도록 만든다.

  • $Attention(Q, K, V) = softmax(\frac{QK^T}{\sqrt{d_k}})V$ ($QK^T$ Query에 대한 에너지 값, $d_k$ : key dimension)
  • $head_i = Attention(QW^Q_i, KW^K_i, VW^V_i)$ : $h$개의 서로 다른 concept을 계산
  • $MultiHead(Q, K, V) = Concat(head_1, ..., head_h)W^O$ ($h$; head의 개수, $W^O$ output matrix)

softmax입력을 ${\sqrt{d_k}}$ (Scaling factor)로 나누어 주는 이유는 Gradient Vanishing을 회피하기 위해서이다.

1.Scaled Dot-Product Attention

• 한개의 단어

• 행렬 연산

2.Multi-Head Attention

Transformer의 Attention 종류

Attention은 Bahdanau가 제안한 기존 컴퓨터 비전 분야의 Visual Attention을 자연어 처리에 활용한 것이라고 한다.🤔

기존 seq2seq 모델의 단점

자연어 처리 분야 중 NMT(Nueral Machine Translation)에서는 인코더-디코더 방식의 번역 알고리즘이 대부분이었는데, 이는 고정된 크기의 벡터로 압축시켜서 병목 현상을 유발한다. 이러한 현상은 번역품질을 악화시킬 우려가 있고 그래서 제안된것이 어텐션을 이용한 기계번역이다.

어텐션 매커니즘

$y_t$ : 출력 $S_t = f(S_{t-1}, y_{t-1}, C_t)$ $C_t = \sum^T_{j=1}\alpha_{Tj}h_T$ $\alpha_{ij} = \frac{exp(e_{ij})}{\sum^T_{k=1}exp(e_{ik})}$: <확률: attention weight> $e_{ij}=a(s_{i-1}, h_j)$ <$h_j$를 기반으로 한 에너지> $h_j = [\overrightarrow{h^T_j}; \overleftarrow{h^T_j}]$ : RNN셀의 순방향/역방향 hidden state concatenation $x_T$ : 입력

어텐션 매커니즘의 의의

1.확률과 에너지를 기반으로 한 접근

$\alpha_{ij} = \frac{exp(e_{ij})}{\sum^T_{k=1}exp(e_{ik})}$: <확률; softmax 형태> $e_{ij}=a(s_{i-1}, h_j)$ <$h_j$를 기반으로 한 에너지>

• $\alpha_{ij}$를 확률적인 가중치로 $e_{ij}$를 해당 확률을 형성하는 에너지로 볼 수 있음

2.긴 거리에서의 의존성(Long Dependencies) 문제를 해결

기존의 RNN은 문장이 매우 길어지면 depenency가 생길 수 밖에 없다. 하지만, Attention을 적용하면 각각의 hidden state에 대한 attention weight가 반영이 되기 때문에 손쉽게 해결 할 수 있다.

1.Single Layer Perceptron(SLP)

로젠블럿(Rosenblatt)이 제안한 초기형태의 인공신경망

• $X(x_1, x_2, ..., x_n)$ : 입력값
• $W(w_1, w_2, ..., w_n)$ : 가중치
• $\hat{y}$ : 예측값

들어오는 입력 $X$에는 각각의 가중치(Weight) $W$가 존재하며, 가중치가 클 수록 해당 입력값이 중요하다는것을 의미함.

활성(Activation)함수는 모델의 비선형성을 높이기 위해 사용함.

어떤 입력 X에 선형변환 A, B를 적용하여도 결국, 이 선형변환은 또 다른 선형변환 C로 대응되므로 비선형함수인 활성함수를 적용하여야 함.

다만, 이 퍼셉트론으로는 XOR 문제를 해결할 수 없다는 문제점이 있다. 이 문제를 해결한 다층 퍼셉트론을 살펴보자.

2.Multi Layer Perceptron(MLP)

다층 퍼셉트론은 단층 퍼셉트론의 층을 쌓아서 만들 수 있다.

차이점은 은닉층(Hidden Layer)의 유무이며, 은닉층이 2개 이상인 신경망을 심층 신경망(Deep Neural Network; DNN)이라고 부른다.

CNNs

Conventional CNN

1.VGGNet

VGGNet은 널리 사용되는 CNN 모델 중의 하나로 옥스퍼드 대학교 VGG(Visual Geometry Group) 연구소의 Simonyan과 Zisserman이 제안하였다.

VGGNet의 컨셉은 작은 커널을 사용하여 깊은 네트워크를 만드는 것이다.

네트워크의 깊이를 깊게 만드는 것이 성능에 어떤 영향을 미치는지 확인하고자 많은 개수의 필터를 사용하되 3×3 필터만 사용하였다. 큰 커널을 한번 적용하는 연산보다 3×3 커널을 여러 번 연산하는 것이 비선형 연산을 더 많이 수행하므로 변별력 측면에서 더 우월하다는것을 확인하였다.

2.GoogLeNet(Inception)

GoogLeNet은 Lin이 제안한 네트워크 속의 네트워크(NIN)의 영향을 받았다.

기존의 컨볼루션 레이어은 단순히 컨볼루션 연산을 수행하지만, NIN는 MLP의 순전파를 계산한다. MLPconv 레이어는 컨볼루션 연산처럼 커널을 옮겨가면서 계산을 하여 컨볼루션 처럼 Feature Map을 계산한다. (b)의 두 층 사이에 있는 네트워크를 마이크로 네트워크라고 한다.

NIN에서는 Global average pooling이라는 아이디어를 제시하였다.

기존의 AlexNet이나, VGGNet는 네트워크 뒷부분에 분류 목적으로 완전 연결층을 두었다. 여기서 문제점은 이 완전 연결층의 매개변수가 전체 VGGNet의 매개변수의 85%를 차지한다는 것이다.

이는 과잉적합의 원인이 되기 때문에 NIN에서는 MLPconv가 필요한 만큼의 클래스 수만큼 특징맵을 생성하고 이를 Global average pooling를 이용하여 매개변수를 줄여 과잉 적합을 줄인다.

GoogLeNet은 이 NIN를 확장한 신경망이다. 다만, MLPconv대신 Inception 모듈을 사용한다. GoogLeNet에서 이 Inception 모듈을 9개 결합하였고, 과적합을 정규화하고 방지하기 위해 보조 분류기를 추가하였다.

Inception 모듈은 마이크로 네트워크가 컨볼루션 연산만으로 구성되며, 네 종류의 컨볼루션을 수행하고 결과를 합하는 방식으로 이루어진다. (아래의 사진은 아래쪽이 입력이고 위쪽이 출력이다.)

(b)의 사진은 매개변수를 더 줄이기 위한 트릭을 적용한 버전이다.

이 Inception 모듈은 28x28 192장의 Feature Map을 입력으로 받아 28x28의 Feature Map을 1x1 컨볼루션은 64장, 3x3은 128장, 5x5은 32장, 3x3 Maxpooling은 32장을 생성하여 총 256장을 출력한다. 즉, 28x28x256 텐서를 출력한다.

3.ResNet

ResNet은 Kaiming He이 제안하였다. 기존 신경망의 문제점은 층수가 늘어나면 성능이 향상되다가 포화상태에 이르고, 어느 지점을 지나면 성능이 급격하게 저하하는 현상이 나타난다.

ResNet은 네트워크에 shortcut들을 추가하여 Vanishing/Exploding Gradients 문제를 해결하였다.

ResNet에서는 Residual Block을 이용하여 이를 구현하였고 그 구조는 아래와 같다.

$F(x)=\tau(x \circledast w_1) \circledast w_2$ $y = \tau(F(x)+x)$

• $\tau$ : 활성함수

여기서 역전파는 아래와 같다.

$\frac{\partial\mathcal{E}}{\partial x_l} = \frac{\partial\mathcal{E}}{\partial x_L} \frac{\partial x_L}{\partial x_l} = \frac{\partial \mathcal{E}}{\partial x_L}(1+\frac{\partial}{\partial x_l}\sum^{L-1}_{i=l}F(x_i))$

• $\mathcal{E}$ : 목적함수
• $L$, $l$ : Residual Block 번호 ($L$은 $l$보다 더 깊은곳)

여기서 역전파 되는 항이 $\frac{\partial \mathcal{E}}{\partial x_L}$와 $\frac{\partial \mathcal{E}}{\partial x_L}\frac{\partial}{\partial x_l}\sum^{L-1}{i=l}F(x_i)$ 두개의 항으로 구성되어 있다. 그런데, $\frac{\partial}{\partial x_l}\sum^{L-1}{i=l}F(x_i)$이 -1이 될 가능성이 없기 때문에 Gradient가 0이 되지 않는다. 그래서 Vanishing Gradient 문제가 발생하지 않는다.

4.DenseNet

DenseNet은 Gao Huang이 제안하였다. 정보의 흐름을 최대로 보장하기 위해서, short connection방법을 바탕으로 모든 layer들을 연결한다.

즉, DenseNet은 $\frac{L(L+1)}{2}$ 번의 direct connection이 이루어진다. 이러한 Dense Connectivity Pattern으로 인해 DenseNet이라 부른다.

Object Detection

1.R-CNN(Region-based CNN)

R-CNN은 아래의 사진과 같은 구조로 객체의 위치를 탐색하고 객체의 class를 식별한다.

1. 객체를 포함하고 있을것 같은 영역을 찾기 위해 영역 제안(region proposal) 알고리즘 적용
2. 추천된 각 영역을 224*224 정규화 한 후 feature를 추출(변형 AlexNet 모델을 사용)
3. 디스크에 캐싱
4. multi-class SVM을 적용하여 학습을 진행 추가적으로 bounding box를 미세 조정하는 회귀모델도 학습을 진행

초창기 객체 탐지 알고리즘으로 관심을 얻었지만 아래와 같은 단점이 있다.

1. 추천된 약 2,000개의 영역을 순차적으로 CNN모델에 적용해야하기 때문에 계산량이 많음
2. CNN 정규화 과정을 거치기 때문에 클래스 예측 모델에서 성능저하 발생
3. multi-class SVM과 Bbox regression 학습 알고리즘이 GPU 사용에 적합하지 않음

이러한 단점을 보완한 모델로 Fast R-CNN, Faster R-CNN 등이 있다.

2.YOLO(You Only Look Once)

YOLO 모델은 실시간으로 객체를 탐지하고 인식하는 방법이다.

1. 영상을 448*448 크기로 조정
2. 영상을 S*S 그리드로 나누기
3. 각 그리드 셀에서 B개의 객체를 검출하고 class를 결정 (검출된 객체는 Bbox로 표시, 객체의 class는 확률값으로 제공)

• Bbox Bbox에는 중심 위치$(x, y)$와 폭$(w)$, 높이$(h)$로 표현한다. 객체에 대한 Bbox에는 신뢰도($C$)가 부여됨 ($w$, $h$는 전체 영상의 폭과 높이의 비로 표현)

  $C = P(Object) \cdot IoU$

객체의 class 수가 총 $K$라면, 클래스 정보는 $K$개의 확률값으로 표현하고 YOLO는 학습시 영상 하나에 대해 $S \times S \times (5B+K)$크기의 데이터를 출력한다.

YOLO는 R-CNN의 방법(물체 영역을 찾은 다음 그 영역의 객체를 인식)과는 다르게 물체 영역과 인식을 동시에 하는 회귀 문제로 해결한다.

3.SSD(Single Shot MultiBox Detector)

SSD는 YOLO보다 정확도와 처리시간이 개선된 방법으로 실시간으로 객체를 식별하고 인식하는 방법이다.

(a) : label된 Groud Truth Bbox (b) : $8 \times 8$ Feature map (c) : $4 \times 4$ Feature map

각 Feature map의 셀에 대해 aspect ratio가 다른 K개의 base Bbox를 정하고, 해당 부분에서의 객체의 유무를 확인한다.

Bbox의 정보

1. base Bbox의 중심 위치에 대한 offset과 너비와 높이 : $\Delta$(cx, cy, h, w)
2. class에 대한 신뢰도 : $(c_1, c_2, ..., c_p)$

SSD모델은 위의 사진과 같이 기본망과 추가 feature layer로 구성된다.

Sementic Segmentation

1.FCN(Fully convolutional Networks)

FCN는 Jonathan Long, Evan Shelhamer, Trevor Darrell이 제안하였다. 이 네트워크는 Sementic Segmentation 문제를 해결하기 위해 수정한 CNN이다.

FCN은 기존 CNN의 완전 연결층을 모두 1x1 컨볼루션 레이어로 변경하였고, 마지막 레이어에서 디컨볼루션 레이어를 추가하여 축소된 이미지를 원본 이미지 크기까지 확대한다.

2.DeepLab

DeepLab은 Dilated Convolution(Atrous Convolution)을 이용한 Segmentation 모델이다.

Atrous Convolution의 장점은 파라미터의 개수를 늘리지 않고 recepticle field를 키울 수 있다.

가운데(dilation=2) 그림을 보면, recepticle field가 $7 \times 7$인 것을 볼 수 있다. 이것을 normal convolution으로 구현을 한다면 파라미터의 수가 49개이지만, dilated convolution을 사용한다면 빨간점에 해당하는 부분만 연산한다. 즉, $3 \times 3$ 필터를 적용하는 것과 같게되며 연산이 줄어든다.

DeepLab V3는 ImageNet으로 pre-trained된 ResNet을 Feature Extracter로 사용한다. 또한, 이전 버전에서 소개되었던 Atrous Spatial Pyramid Pooling (ASPP)을 사용한다.

3.U-Net

U-Net은 Olaf Ronneberger, PhilippFischer, Thomas Brox에 의해 제안되었으며, 이 네트워크는 biomedical 분야에서 주로 사용된다. 이 네트워크 이름은 아키텍쳐 구조가 U 모양이라 붙여진 이름이다.

U-Net의 메인 아이디어

1. Contracting Path(Encoding): 이미지의 context 캡처
   2. Expanding Path(Decoding): feature map을 upsampling 하고 캡처한 context와 결합 → 더욱 정확한 localization 기대 가능
   3. Data Augmentation으로 Random Elastic Deformation 사용

U-Net의 특징

1. feature map을 upsampling 하고 캡처한 context와 결합을 통해 해상도가 높게 유지됨
2. overlap-tile 전략

아래와 같이 feature map을 upsampling 하고 캡처한 context와 concatenation을 하면 해상도가 높게 유지된다.

overlap-tile 전략은 기존 Segmentation 방법이 Sliding window를 사용하였기 때문에 너무 느리고 정확도가 떨어지기 때문에 제안된 방법이다.

이 전략은 파란색 단위(tile)로 선택(파란색)해서 처리하고 다음 타일을 이전 타일의 영역과 곂쳐 선택(빨간색)한다음 처리한다. 또, border 부분에는 0으로 채워넣는 Padding 방식이 아니고 주변 값들로 채워넣는 Mirroring 방법으로 픽셀 값을 채워넣는다.

4.SegNet

SegNet은 Vijay Badrinarayanan, Alex Kendall, Roberto Cipolla가 제안하였고, 이 네트워크는 자율주행과 분야의 Sementic Segmentation 문제를 해결하기위해 설계되었다.

SegNet 모델은 크게 Encoder와 Decoder로 이루어져 있다.

Encoder는 VGG16에서 완전 연결 레이어를 제외한 13개의 컨볼루션 레이어를 그대로 사용하였고, Encoder의 2x2 Max-pooling에서 해당되는 Max-pooling 인덱스를 저장한다.

Decoder는 Upsampling과 컨볼루션을 수행한다. Decoder의 Upsampling에서는 Encoder에서 저장한 Max-pooling 인덱스를 이용한다.

Recurrent Neural Network(RNN)

1.RNN

RNN은 시계열 데이터를 다루는데 특화된 데이터에 특화된 모델이다.

그림에서 보여주듯이 이전 시간(t-1)의 은닉층 출력이 다음 시간(t)의 입력으로 들어가는 것을 볼 수 있다. 이 구조는 현재 시간(t)가 다음 시간(t+1)에 영향을 미치고, 이것이 다음 시간(t+2)에 영향을 미치는 괴정이 끊임없이 반복되어 순환하는 구조이다.

하지만 RNN을 포함한 대부분의 신경망 구조는 학습이 계속 진행됨에 따라, 이전 입력 정보의 학습에 미치는 영향이 점점 감소하다 사라지는 치명적인 문제 vanishing gradient problem을 가지고 있다. 이를 해결한 모델인 LSTM을 살펴보자.

2.LSTM

LSTM는 Alex Graves가 제안한 모델이다.

RNN의 hidden layer를 input, output, forget 3개의 게이트로 구성하는 메모리 블록으로 대체하여 Long Short-Term Memory구조를 제시하였다.

이를 통해 RNN의 Vanishing Gradient 문제를 해결하였고, 이 문제 때문에 나온 현상인 장기 의존성 문제를 해결하였다. 이 덕분에 LSTM은 먼 과거의 정보도 다음 시점의 은닉 층으로 전달할 수 있다.

3.Gated Recurrent Unit(GRU)

GRU Kyunghyun Cho이 제안한 LSTM의 장기기억능력은 보존하면서 연산은 적은 모델이다.

LSTM에서는 메모리 블록이 3개의 게이트로 구성되었지만, GRU에서는 reset, update 2개의 게이트만 있다.

LSTM과 구조적으로는 비슷하지만 output 게이트가 없다.

모델별 매개변수 개수 GRU : $3(NM+M^2+M)$개 LSTM : $4(NM+M^2+M)$개 RNN : $NM+2M^2+2M$개 (셀의 입력 : N차원, 출력 : M차원)

정보 이론에서는 메시지의 정보량을 확률로 측정한다고... 한다🤔 확률이 낮은 사건 일수록 더 많은 정보를, 반대의 경우에는 더 적은 정보를 전달한다.

어떤 사전이 일어날 확률을 추정 할 수 있다면 그 사전에 대한 정보량을 측정 할 수 있고, 이 정보량을 자기 정보(self-information)이라고 한다.

정보 엔트로피(Entropy)

자기 정보가 특정 사건의 정보량을 측정하는 반면, 엔트로피는 확률 분포의 무질서도 또는 불확실성을 측정한다.

• 이산 확률 분포 : $H(x) = - \sum^n_{i=1,k}P(e_i)log_2P(e_i)$

• 연속 확률 분포 : $H(x) = - \int_\mathbb{R}P(x)log_2P(x)$

교차 엔트로피(Cross Entropy)

서로 다른 두 확률 분포 사이의 교차 엔트로피는 아래와 같다.

$H(P, Q) = -\sum_xP(x)log_2Q(x)$ 단, 이때 두 확률 분포는 같은 확률변수에 대해 정의되어 있어야한다.

KL 다이버전스(KL Divergence)

교차 엔트로피를 다음과 같이 유도할 수 있다.

$H(P, Q) = -\sum_xP(x)log_2Q(x)$ $= -\sum_xP(x)log_2P(x) + \sum_xP(x)log_2P(x) - \sum_xP(x)log_2Q(x)$ $= H(P) + \sum_xP(x)log_2\frac{P(x)}{Q(x)}$

마지막 식의 두번째 항을 KL 다이버전스라고 하고, 아래와 같이 정의한다.

$KL(P||Q) = \sum_xP(x)log_2\frac{P(x)}{Q(x)}$

KL 다이버전스는 두 확률 분포가 얼마나 다른지를 측정하며, $P$, $Q$가 같을때 0이된다.

규제를 적용하지 않은 선형 모델

독립 변수(X)의 개수에 따라

1. 단순 선형회귀

$H(x)=Wx+b$

2. 다변수 선형회귀

$H(x_1,x_2,x_3,…,x_n)=W_1x_1+W_2x_2+W_3x_3+⋯+W_nx_n+b$

3. 다항 회귀

회귀가 독립변수의 단항식이 아닌 2차, 3차 방정식과 같은 다항식으로 표현되는 것

기울기 계산 방법에 따라

1. 최소 제곱법

종속 변수(응답 변수) y와 한개 이상의 독립 변수(입력 변수) X와의 상관관계를 모델링 한 것

$Y = ax + b, a = \frac{\sum(x-\bar{x})(y-\bar{y})}{\sum(x-\bar{x})^2}$

2. 경사 하강법

일단 선형 모델을 그리고 오차를 수정하는 방법

$H(x) = Wx + b$ $cost(W, b)=\frac{1}{m}\sum(H(x)-y)^2$

규제 선형 회귀

Norm(놈; 노름)

벡터 사이의 거리를 놈이라고 부른다. 규제 선형 모델에서 사용하는 Norm은 $L_2$과 $L_1$이다.

• $L_2$ : 유클리드 거리 → 일반적인 거리 함수

• $L_1$ : 맨해튼 거리; 택시 거리

1. Ridge(릿지) 회귀

• 평균 제곱 오차식에 alpha항이 추가
• 학습한 가중치의 제곱을 규제항($L_2$ 규제) 사용
• 편향(bias)를 조금 손해 보면서 분산(Variance)을 줄여 성능을 향상

  $cost(W, b) = MSE + α(L_2Norm)$ $= \frac{1}{m}\sum(H(x)-y)^2+α\sum^n_{j=1}W^2_j$

2. Lasso(라쏘) 회귀

• Ridge 회귀의 단점을 해결하기 위해 대안으로 나온 방법
• 학습한 가중치의 절대값의 합을 규제항으로 사용

  $cost(W, b) = MSE + α(L_1Norm)$ $= \frac{1}{m}\sum(H(x)-y)^2+α\sum^n_{j=1}|W|_j$

3. Elastic Net(엘라스틱 넷)

• 선형 회귀에 2가지 규제항($L_1$규제항, $L_2$규제항) 추가

  $cost(W, b) = MSE + α1(L_1Norm) + α_2(L_2Norm)$ $=\frac{1}{m}\sum(H(x)-y)^2+α_1\sum^n{j=1}W^2_j+α2\sum^n{j=1}|W|_j$

4. 조기 종료

경사 하강법과 같은 학습 알고리즘을 수행 할 때, 검증 에러가 최소값에 도달하면 바로 훈련을 중지 시키는 규제 방법

퀵정렬은 가장 널리 사용되는 정렬 알고리즘이다😎

- 퀵정렬의 메인 아이디어 피벗을 설정하고 그 피벗을 기준으로 리스트를 좌우로 나누어 재귀적으로 정렬을 수행하여 해결

퀵정렬의 수행 과정

1. 피벗을 설정한다
2. 그 기준보다 큰 수와 작은 수를 교환한다
3. 피벗으로 리스트를 반으로 나누어 재귀적으로 수행한다.

시간 복잡도

• 평균 : $O(NlgN)$
• 최악 : $O(N^2)$ 최악의 경우는 리스트가 이미 정렬되어 있는 경우 분할이 한쪽으로 치우쳐서 결국 $O(N^2)$이 된다.

코드

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    # 크기가 1이면 종료
    if start >= end:
        return
    pivot = start
    left = start+1
    right = end
    # 엇갈릴때까지 수행(더이상 정렬할 필요가 없을때까지)
    while left <= right:
        # 왼쪽에서부터 pivot 보다 큰 값 탐색
        while left <= end and array[pivot] >= array[left]:
            left += 1
        # 오른쪽에서부터 pivot 보다 작은 값 탐색
        while right > start and array[pivot] <= array[right]:
            right -= 1
        # 엇갈렸다면 pivot과 right 교체
        if left > right:
            array[pivot], array[right] = array[right], array[pivot]
        # 그게 아니라면 left와 right 교체
        else:
            array[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)

quick_sort(array, 0, len(array)-1)
print(array)

Generative(생성적) Adversarial(적대) Network(신경망) GAN은 서로 경쟁하는 두개의 신경망으로 구성된 네트워크다

그럼 GAN의 구조를 보도록 하자🧐

GAN은 생성기 신경망과 판별기 신경망으로 이루어져있다. 그리고 CNN, RNN, LSTM과 같은 모든 신경망을 생성기와 판별기로 이용가능하다.

GAN과 관련된 주요 개념

GAN을 학습시킬때 사용하는 목적함수와, 품질을 판단할때 사용되는 옌센-섀년 발산(JS 발산)을 보자🧐

목적함수

진짜 이미지와 유사한 이미지를 만들기 위해서 생성된 이미지와 진짜 이미지간의 유사도를 높이게 하기 위하여 목적함수를 이용하여 유사도를 측정한다.

$min_{G}max_{D}V(D, G) = E_{x \sim P_{data}}[logD(x)] + E_{x \sim P_z(z)}[log(1- D(G(z)))]$

• $D(x)$ : 판별기 모델
• $G(z)$ : 생성기 모델
• $P_x$ : 진짜 데이터 분포
• $p_z$ : 생성기가 생성한 데이터 분포
• $E$ : 예상되는 출력 내용

훈련중에 판별기(D)는 최대화하는 방향으로, 생성기(G)는 최소화하는 방향으로 학습이 진행이 된다. GAN을 학습을 시켜보면 판별기와 생성기가 균형을 잡게 되는데, 이를 모델이 수렴했다고 하고, 이 균형을 내시 균형(Nash Equilibrium)이라고 한다. 반대의 경우를 모드 붕괴(Mode Collapse)라고 한다.

KL Divergence (KL 발산)

쿨백-라이블러 발산은 두 확률 분포가 얼마나 다른가를 측정하는 방법이다. 아래는 두 확률 분포 p와 q사이의 KL 발산을 나타낸다.

• 이산형 확률 변수 : $D_{KL}(p||q) = \sum_iP(i)log\frac{p(i)}{q(i)}dx$

• 연속형 확률 변수 : $D_{KL}(p||q) = \int_xP(x)log\frac{p(x)}{q(x)}dx$

다만, KL 발산은 비대칭적이기 때문에, 두 확률분포 사이의 거리를 측정할때는 사용하면 안된다. 대신 JS 발산을 사용하여야 한다.

JS Divergence (JS 발산)

옌센-섀넌 발산은 대칭적이며 두 확률 분포 사이의 거리를 측정하는데 쓰인다. 아래는 두 확률 분포 p와 q사이의 옌센-섀넌 발산을 나타낸다.

$D_{JS}(p||q) = \frac{1}{2}D_{KL}(p||\frac{p+q}{2}) + \frac{1}{2}D_{KL}(q||\frac{p+q}{2})$

멀티 프로세싱을 알아보기 전에 스레드와 프로세스의 차이를 보자🧐

• 프로세스(Process)

  프로세서(Processor)에 의해 처리되는 상태

• 쓰레드(Thread)

  프로세스(Process) 내에서 실행되는 흐름의 단위

그렇다면 멀티 스레딩과 멀티 프로세싱은 뭘까?🤔

멀티 프로세싱 vs 멀티 스레딩

• 멀티 프로세싱(Multi-processing)

  하나 이상의 프로세스(Process)가 서로 협력하여 일을 처리하는 것

• 멀티 스레딩(Multi-Threading)

  하나의 프로세스(Process) 내에서 둘 이상의 스레드(Thread)가 동시에 작업을 수행하는 것

각각의 장단점

• 멀티 프로세스 장점 : 하나의 프로세스가 죽더라도 다른 프로세스에 영향을 주지 않아 안정성이 높다. 단점 : 멀티 스레드보다 많은 메모리공간과 CPU 시간을 차지하는 단점이 있다.

• 멀티 스레드 장점 : 멀티 프로세스보다 적은 메모리 공간을 차지하고 문맥 교환(Context Switching)이 빠르다. 단점 : 자원 공유 문제와 하나의 스레드 장애로 전체 스레드가 종료 될 위험이 있다.

하지만 파이썬에서는 GIL(Global Interpreter Lock) 때문에 한번에 하나의 스레드에게만 모든 자원 점유를 허락한다...고 한다😅

파이썬 멀티 프로세싱

단일 프로세스

소요시간 : 약 3.483초

import time
from threading import Thread

def work(id, start, end, result):
    total = 0
    for i in range(start, end):
        total += i
    result.append(total)
    return


if __name__ == "__main__":
    start_time = time.time()
    START, END = 0, 100000000
    result = list()
    th1 = Thread(target=work, args=(1, START, END, result))

    th1.start()
    th1.join()

    end_time = time.time()
    print(f"Result: {sum(result)}")
    print(f"total elapsed time : {end_time - start_time}")

멀티 프로세스

소요시간 : 약 1.824초

import time
from multiprocessing import Process, Queue

def work(id, start, end, result):
    total = 0
    for i in range(start, end):
        total += i
    result.put(total)
    return

if __name__ == "__main__":
    start_time = time.time()
    START, END = 0, 100000000
    result = Queue()
    th1 = Process(target=work, args=(1, START, END//2, result))
    th2 = Process(target=work, args=(2, END//2, END, result))

    th1.start()
    th2.start()
    th1.join()
    th2.join()

    result.put('STOP')
    total = 0
    while True:
        tmp = result.get()
        if tmp == 'STOP':
            break
        else:
            total += tmp
    print(f"Result: {total}")

    end_time = time.time()
    print(f"total elapsed time : {end_time - start_time}")

문제 접근

최종 목표: DFS와 DFS 탐색

문제에서 입력으로 주어지는 간선은 양방향이라고 언급하였으므로, 인접 리스트가 아닌 인접 행렬을 이용해 문제를 풀어야 한다.

문제 해결 아이디어

enumerate() 함수를 이용하면 간단하게 인접 행렬을 사용할 수 있다.

코드

from collections import deque
n, m, v = map(int, input().split())

visited = [False] * (n+1)
graph = [[0] * (n+1) for _ in range(n+1)]

# 인접 행렬 입력
for i in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1 
    graph[b][a] = 1

def dfs(graph, start, visited):
    # 현재 방문 노드 처리
    visited[start] = True
    print(start, end=' ')
    # 인접 노드 탐색
    for next_node, value in enumerate(graph[start]):
        if value == 1:
            if not visited[next_node]:
                dfs(graph, next_node, visited)    

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        # 방문 노드 처리
        now = queue.popleft()
        print(now, end=' ')
        # 인접 노드 탐색
        for next_node, value in enumerate(graph[now]):
            if value == 1:
                if not visited[next_node]:
                    queue.append(next_node)
                    visited[next_node] = True

dfs(graph, v, visited)
print()
visited = [False] * (n+1)
bfs(graph, v, visited)

서포트 벡터 머신의 메인 아이디어: 부류 간의 여백(마진)을 크게 하여 일반화 능력을 최대화

이를 위하여 결정함수와 목적함수를 이용한다.

결정함수를 이용하여 오류가 적거나(소프트 마진) 없는(하드 마진) 가중치 벡터(w)를 찾고, 목적함수를 이용하여 결정함수의 기울기(w)를 최적화하는 것이다.

선형 SVM

선형 SVM에서는 두 클래스를 분리하기 위하여 결정함수 $d(x)$를 이용한다.

결정함수

$d(x)=w^T x+b=0$

위 식은 특징공간을 2개로 분할하며 결정 초평면이라고도 부른다.

이 평면을 기준으로 한쪽 영역은 $d(x)>0$, 나머지 한쪽 영역은 $d(x)<0$으로 나눈다. $w$는 초평면의 법선 벡터이고, 바이어스($b$)는 초평면의 위치를 지정한다.

• 임의의 점($x$)에서부터 초평면까지의 거리($h$)는 다음과 같이 나타낸다.

  $h=\frac{|d(x)|}{||w||_2}$

목적함수

목적함수는 마진을 가장 크게 하는 초평면의 기울기$(w)$를 찾는 문제이다.

서포트 벡터$(x)$에 대한 마진을 계산한 후 역수를 취하여 최솟값을 찾으면 최적의 $w$값을 찾을 수 있다. 또, $d(x)$에 상수 $c$를 곱하여도 같은 초평면을 나타내므로 $|d(x)| = 1$로 만들 수 있다.

• 서포트 벡터에 대한 마진은 다음과 같이 나타낼 수 있다.

  $margin$ = $\frac{2|d(x)|}{||w||_2}$ = $\frac{2}{||w||_2}$

• 목적함수는 간단하게 아래와 같이 나타낼 수 있다.

  $minimize(\frac{||w||_2^2}{2})$

선형 분리 불가능 문제

선형 분리가 불가능한 문제에서도 SVM을 적용할 수 있다. 아래와 같은 상황이 선형으로 두 클래스를 분리 시킬 수 없는 예이다.

선형 SVM으로 이를 해결하려면 샘플 몇개정도는 마진안에 들어가는 것을 허용해야한다. 이를 허용하는 SVM을 소프트 마진 SVM이라고 한다.

훈련집합 $𝕏$={$x_1,x_2,x_3,…,x_n$}, $𝕐$={$y_1, y_2,y_3,…,y_n$}이고, $y_i$∈{1,-1}인 조건 하에서 최대 마진을 갖는 초평면을 찾는 것은 조건부 최적화 문제로 나타낼 수 있다.

라그랑주 승수법

조건부 최적화 문제는 라그랑주 승수법을 이용한다. 라그랑주 승수법의 기본 개념은 원문제(primal problem)의 등식제약을 함수의 제약으로 옮겨서 제약이 없는 문제로 표현하는 것이다. 이를 수식으로 표현하면 다음과 같다.

KKT 조건

하지만, 이문제는 부등식 조건하 최적화 문제이기 때문에 KKT 조건을 추가로 적용해야 한다.

1. 라그랑주 함수 $L(w,b,α)$에서 라그랑주 승수를 제외한 $w, b$로 편미분한 식이 0이다.
2. 모든 라그랑주 승수($α$)는 0보다 크거나 같다.
3. 모든 조건식에 대해 $α_i=0$이거나 $y_i(w^T x_i+b)-1=0$이 되어야 한다.

여기서 $y_i(w^T x_i+b)=1$를 만족하는 점이 서포트 벡터이다.

쌍대 문제

지금까지 유도한 수식은 선형분류만 적용 가능하며, 비선형 문제를 해결하기 위한 커널 트릭을 적용하기 위해서는 쌍대문제를 이용해야 한다.

원문제가 $f_i (θ)≥0,i=1,…,n$이라는 조건 하에서 $J(θ)$를 최소화하는 문제라고 하면, 쌍대문제는 $\frac{∂L(θ,α))}{∂θ}=0$과 $αi≥0, i=1,…,n$이라는 두가지 조건하에서
$L(θ,α)=J(θ)-∑{i=1}^nα_i f_i (θ)$를 최대화하는 문제로 표현할 수 있다.

위의 SVM문제를 쌍대문제로 나타낸다면 아래와 같이 표현할 수 있다.

위 식을 $L(w,b,α)$에 대입하여 정리하면 아래와 같이 표현할 수 있다.

위의 식은 하나의 등식조건과 n개의 부등식 조건을 가진 2차 목적함수의 최대화 문제이다.

라그랑주 승수만 구한다면 $w$와 $b$를 구할 수 있을 뿐만 아니라 목적함수에서 특징벡터가 내적형태인 $x_i^T x_j$로 나타나기 때문에 머서의 정리를 이용하면 선형 SVM을 비선형 SVM으로 확장할 수 있다.

비선형 SVM

선형으로 분리되지 않는 데이터를 비선형 매핑, 즉 커널함수를 이용하여 해결할 수 있다.

머서의 정리를 이용하면 2차 다항식 매핑함수 φ를 이용하여 3차원 공간으로 매핑 시킬 수 있다.

머서(Mercer)의 정리

두개의 차원벡터 $a$, $b$에 2차 다항식 매핑을 적용한 다음 변환된 벡터로 내적을 적용하면 아래와 같다.

$φ(a)^T φ(b) = \begin{pmatrix} a_1^2 \\ \sqrt{2}a_1a_2 \\ a_2^2 \end{pmatrix} \begin{pmatrix} b_1^2 \\ \sqrt{2}b_1b_2 \\ b_2^2 \end{pmatrix} =a_1^2b_1^2+2a_1b_1a_2b_2+ a_2^2b_2^2$ $= (a_1b_1+a_2b_2)^2= \begin{pmatrix} \begin{pmatrix} a_1^T \\ a_2 \end{pmatrix} \begin{pmatrix} b_1 \\ b_2 \end{pmatrix} \end{pmatrix}^2 =(a^T b)^2$

즉, 변환된 벡터의 내적은 원래 백터의 내적의 제곱과 같다. 이를 이용하면 다양한 커널을 사용할 수 있다. 그 목록은 아래와 같다.

• 선형 : $K(a,b)= a^Tb$
• 다항식 : $K(a,b)= (γa^T b+r)^d$
• 가우시안 RBF : $K(a,b)=exp(-γ||a-b||^2)$
• 시그모이드 : $K(a,b)= tanh(γa^T b+r)$

참고문헌 [1] 기계학습(Machine Learning), 오일석, 한빛아카데미, 2016 [2] 인공지능(Artificial intelligence): 튜링 테스트에서 딥러닝까지, 이건명, 생능출판사, 2018 [3] 핸즈온 머신러닝 - 사이킷런, 케라스, 텐서플로 2를 활용한 머신러닝, 딥러닝 완벽 실무, Géron, A, 박해선, 한빛미디어, 2020

문제 접근

최종 목표 : 조이스틱 조작 횟수의 최솟값 출력

사실 이 문제가 그리디인지 완전탐색 문제인지 잘 모르겠다...😅 내 생각에는 모든 노드를 탐색하여 조작 횟수의 최솟값을 찾는 문제라 완전탐색으로 접근해야 맞는 것 같다.

우선 문제를 쪼개어서 생각해 보자🧐

문제 쪼개기

1. 상하 이동 최소 횟수 구하기
2. 좌우 이동 최소 횟수 구하기
3. 이동 횟수를 모두 더하여 결과 출력

상하 이동 횟수: 현재 문자가 A에 더 가까운지 Z에 더 가까운지 계산 좌우 이동 횟수: 현재 노드에서 좌측과 우측의 이동횟수를 비교하여 더 적은 것을 선택

문제 해결 아이디어

• 상하 이동 최소 횟수: 아스키 코드를 이용하여 계산 $min(char - 'A', 'Z'- char + 1)$

• 좌우 이동 최소 횟수: 좌측과 우측을 비교하여 더 적은 곳으로 계산 $min(left, right)$

코드

def solution(name):
    # 아스키 코드를 이용하여 상하 이동 최소 횟수를 구함
    graph = [min(abs(ord(char) - ord('A')), abs(ord('Z') - ord(char)+1)) for char in name]
    now, answer = 0, 0
    while True:
        # 현재 방문노드 처리
        answer += graph[now]
        graph[now] = 0
        # 모든 노드를 방문하였을때 종료
        if sum(graph) == 0:
            break
        # 좌측과 우측을 비교하며 더 짧은 곳으로 이동
        left, right = 1, 1
        # 좌측 체크: 좌측 문자열을 변경할 필요가 없는 경우 좌측으로 이동
        while graph[now - left] == 0:
            left += 1
        # 우측 체크: 우측 문자열을 변경할 필요가 없는 경우 우측으로 이동
        while graph[now + right] == 0:
            right += 1
        # 더 작은 값으로 업데이트 후
        # 이동 거리가 더 짧은 곳으로 인덱스를 이동
        answer += min(left, right)
        now +=  -left if left < right else right
    return answer

문제 접근

최종 목표: 안전 영역의 최대 크기를 출력

위와 같은 문제는 어떻게 쉬운 문제로 쪼갤 수 있을까?🤔

문제 쪼개기

1.벽 3개 임의로 배치 2. 바이러스가 퍼지는 것을 BFS로 구현 3. 1과 2를 수행한 후에 지도 상에 존재하는 0의 개수 세기 4. 1~3 반복해서 0이 가장 많은 결과(안전 영역의 최대 크기) 출력

우선 이렇게 4개의 작은 문제로 쪼개서 생각해보았다. 모든 경우를 시도하여 안전 영역의 최대 크기를 찾아보자

문제 해결 아이디어

모든 경우의 수 계산

다만, 구현하기 까다로워서 연습이 필요하다.

코드

from collections import deque

n, m = map(int, input().split())
data = [list(map(int, input().split())) for i in range(n)]
temps = [[0] * m for _ in range(n)]

# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

answer = 0

def walls_dfs(num_walls):
    global answer
    # 벽 3개 배치 
    if num_walls == 3:
        for i in range(n):
            for j in range(m):
                temps[i][j] = data[i][j]

        # 바이러스 전파
        for i in range(n):
            for j in range(m):
                if temps[i][j] == 2:
                    virus_bfs(i, j)
        # 안전영역 계산
        answer = max(answer,  get_score())
        return

    # 빈 공간에 울타리 설치
    for i in range(n):
        for j in range(m):
            if data[i][j] == 0:
                data[i][j] = 1
                num_walls += 1
                walls_dfs(num_walls)
                data[i][j] = 0
                num_walls -= 1

def virus_bfs(x, y):
    queue = deque([(x, y)])
    # 현재노드 방문처리
    temps[x][y] = 2
    while queue:
        x, y = queue.popleft()
        # 인접 노드 탐색
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 범위에 해당하는 경우
            if (0 <= nx < n) and (0 <= ny < m):
                # 방문하지 않은 경우
                if temps[nx][ny] == 0:
                    temps[nx][ny] = 2
                    queue.append((nx, ny))

def get_score():
    score = 0
    for i in range(n):
        for j in range(m):
            if temps[i][j] == 0:
                score += 1
    return score

walls_dfs(0)
print(answer)

문제 접근

최종 목표 : 최단거리가 K인 도시를 출력

어떻게 하면 문제를 해결할 수 있을까....? 🤔 일단 문제를 쪼개서 쉬운 문제 여러 개로 바꾸어보자

문제 쪼개기

1. 시작 노드(S)에서부터 다음 노드(N)의 최단 거리를 계산 후 다음 노드로 이동
2. 현재 노드(C)와 다음 노드(N)의 최단 거리를 계산 후 다음 노드로 이동
3. 2번을 반복하여 시작 노드(S)와 최단거리가 K인 도시들을 출력

일단 이렇게 해서 전체 문제를 부분 문제 여러 개로 쪼개서 생각해보았다.

이 문제를 확인해보면 모든 엣지의 길이가 1이라는 점이 문제 해결의 키포인트로 보인다.

문제 해결 아이디어

D(시작 노드, 현재 노드) = D(시작 노드, 이전 노드) + 1이다.

이를 이용하면 BFS로 간단하게 해결할 수 있다.

코드

from collections import deque

# 도시의 개수(N), 도로의 개수(M), 거리 정보(K), 출발 도시번호(X)
n, m, k, x = map(int, input().split())

# 인접 리스트 입력
graph = [[] for i in range(n+1)]
for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)

# 최단거리 리스트(start 노드에서 부터 해당 노드 까지의)
dist = [-1] * (n+1)

def bfs(graph, dist, target, start):
    # 시작 노드 큐에 삽입
    queue = deque([start])
    # 시작노드 최단거리 초기화
    dist[start] = 0

    while queue:
        current = queue.popleft()
        # 인접 리스트를 탐색
        for next_node in graph[current]:
            # 방문하지 않은경우
            if dist[next_node] == -1:
                # 최단거리 갱신
                dist[next_node] = dist[current] + 1
                queue.append(next_node)

    # 최단 거리가 정확히 K인 도시 출력
    if target in dist:
        for i in range(1, n+1):
            if target == dist[i]:
                print(i)
    # 없을 경우 -1 출력
    else:
        print(-1) 

    return

bfs(graph, dist, k, x)