jonathandinu/페이스파싱 · 포옹하는 얼굴 (huggingface.co)

import torch
from torch import nn
from transformers import SegformerImageProcessor, SegformerForSemanticSegmentation

from PIL import Image
import matplotlib.pyplot as plt
import requests

# convenience expression for automatically determining device
device = (
    "cuda"
    # Device for NVIDIA or AMD GPUs
    if torch.cuda.is_available()
    else "mps"
    # Device for Apple Silicon (Metal Performance Shaders)
    if torch.backends.mps.is_available()
    else "cpu"
)

# load models
image_processor = SegformerImageProcessor.from_pretrained("jonathandinu/face-parsing")
model = SegformerForSemanticSegmentation.from_pretrained("jonathandinu/face-parsing")
model.to(device)

# expects a PIL.Image or torch.Tensor
url = "https://images.unsplash.com/photo-1539571696357-5a69c17a67c6"
image = Image.open(requests.get(url, stream=True).raw)

# run inference on image
inputs = image_processor(images=image, return_tensors="pt").to(device)
outputs = model(**inputs)
logits = outputs.logits  # shape (batch_size, num_labels, ~height/4, ~width/4)

# resize output to match input image dimensions
upsampled_logits = nn.functional.interpolate(logits,
                size=image.size[::-1], # H x W
                mode='bilinear',
                align_corners=False)

# get label masks
labels = upsampled_logits.argmax(dim=1)[0]

# move to CPU to visualize in matplotlib
labels_viz = labels.cpu().numpy()
plt.imshow(labels_viz)
plt.show()

Image Segmentation - Hugging Face Community Computer Vision Course

[CV] Image Segmentation (이미지 분할) (tistory.com)

Yolo26

yolo26n-seg를 사용해 보았다.

from torch.serialization import save
import cv2

model = YOLO("yolo26n-seg.pt")

results = model(img_path, save = True)

for result in results:
    p = result.plot()

    img_rgb = cv2.cvtColor(p, cv2.COLOR_BGR2RGB)
    plt.imshow(img_rgb)
    plt.show()

    masks = result.masks  # SegMask objects
    boxes = result.boxes  # Boxes objects
    print(f"Detected {len(boxes)} objects.")

print(type(results))
print(results)

Instance Segmentation

Ultraltice에서 제공하는 개발자 문서를 토대로 새로운 데이터 셋을 학습시켰다.

yolo26의 모델별 성능

Train

from ultralytics import YOLO

# Load a model
model = YOLO("yolo26n-seg.yaml")  # build a new model from YAML
model = YOLO("yolo26n-seg.pt")  # load a pretrained model (recommended for training)
model = YOLO("yolo26n-seg.yaml").load("yolo26n.pt")  # build from YAML and transfer weights

# Train the model
results = model.train(data="coco8-seg.yaml", epochs=100, imgsz=640)

모델을 가져오는 방법은 3가지로 나누어진다

• YOLO("yolo26n-seg.yaml")

  • yolo26모델의 아키텍쳐만 가지고 온다.
  • 사전에 학습이 없고 새로운 데이터 셋을 학습시킬 때 가지고 사용한다.

• YOLO("yolo26n-seg.pt")

  • 사전에 학습된 모델의 가중치를 가지고 온다.
  • 파인튜닝 할때 사용된다.

• YOLO("yolo26n-seg.yaml").load("yolo26n.pt")

  • -seg 모델의 아키텍쳐를 가지고 오고 가중치는 객체 탐지 가중치를 가지고 온다.
  • 특수한 구조 변경이 필요할 때 사용한다.

• model.train()

  • 모델을 학습시킨다.

    매개변수	기본값	설명
    model	None	학습에 사용할 모델 파일 경로 (.pt 또는 .yaml)
    data	None	데이터셋 설정 파일 경로 (data.yaml)
    epochs	100	전체 데이터를 반복 학습할 횟수
    imgsz	640	입력 이미지 크기 (정사각형 기준)
    batch	16	한 번에 학습할 이미지 개수 (-1로 설정 시 자동 최적화)
    save	True	학습 결과 및 체크포인트를 저장할지 여부
    device	None	실행 장치 (예: device=0, device='cpu')
    project	None	결과가 저장될 상위 폴더 이름
    name	None	결과가 저장될 하위 폴더 이름
    resume	False	마지막 중단된 지점부터 학습을 재개할지 여부

data.yml 구조

# Root directory containing the dataset
path: ../datasets/my_dataset
# Paths to training, validation, and optional test sets
train: images/train
val: images/val
test: images/test # Optional
# Number of classes in the dataset
nc: 3
# Class names (zero-indexed)
names:
 0: cat
 1: dog
 2: bird

Predict

from ultralytics import YOLO

# Load a model
model = YOLO("yolo26n-seg.pt")  # load an official model
model = YOLO("path/to/best.pt")  # load a custom model

# Predict with the model
results = model("https://ultralytics.com/images/bus.jpg")  # predict on an image

# Access the results
for result in results:
    xy = result.masks.xy  # mask in polygon format
    xyn = result.masks.xyn  # normalized
    masks = result.masks.data  # mask in matrix format (num_objects x H x W)

• model

  학습된 모델로 판단해보기 위해서는 먼저 모델을 가져온다.

  YOLO("yolo26n-seg.pt") ← yolo에서 ****제공된 사전 학습된 모델

  • YOLO("path/to/best.pt") ← 새로운 데이터셋을 이용한 커스텀 모델

• model("https://ultralytics.com/images/bus.jpg")

  model()에 이미지 경로를 넣어주면 잘 나오는 것을 볼 수 있다.

결과 이미지를 보기 위한 코드

t = results[0].plot() # 좌표등 숫자 데이터를 원본이미지에 합쳐줌
t = cv2.cvtColor(t, cv2.COLOR_BGR2RGB)# 색상 체계를 BGR에서 RGB로 변환합니다.
plt.imshow(t)
plt.show()

Val

모델이 얼마나 정확하게 물체를 찾고(Box), 그 형태를 따냈는지(Segmentation)를 수치

from ultralytics import YOLO

# Load a model
model = YOLO("yolo26n-seg.pt")  # load an official model
model = YOLO("path/to/best.pt")  # load a custom model

# Validate the model
metrics = model.val()  # no arguments needed, dataset and settings remembered
metrics.box.map  # map50-95(B)
metrics.box.map50  # map50(B)
metrics.box.map75  # map75(B)
metrics.box.maps  # a list containing mAP50-95(B) for each category
metrics.seg.map  # map50-95(M)
metrics.seg.map50  # map50(M)
metrics.seg.map75  # map75(M)
metrics.seg.maps  # a list containing mAP50-95(M) for each category

• map50-95

  IoU 임계값(0.5에서 0.95까지)에 대한 평균 정밀도(mAP) ← 전반적인 탐지 능력을 나타냄

• map50

  정답 값과 얼마나 겹치는지 판단하는 지표 → 50% 겹쳐도 정답 인정

• map75

  정답 값과 얼마나 겹치는지 판단하는 지표 → 75% 겹쳐도 정답 인정

  engine/trainer:

Data set

code

!pip install ultralytics

from ultralytics import YOLO
import matplotlib.pyplot as plt
import matplotlib.image as mpimg
import cv2

model = YOLO("yolo26n-seg.pt")

ex_img = model('/content/drive/MyDrive/yolo26_seg/valid/images/1-1-_jpg.rf.c27b687ae48fe13d078a73965bcbae4e.jpg')

t = ex_img[0].plot()
t = cv2.cvtColor(t, cv2.COLOR_BGR2RGB)
plt.imshow(t)
plt.show() # 데이터 셋 확인

model = YOLO("yolo26n-seg.pt")

new_model = model.train(data="/content/drive/MyDrive/yolo26_seg/data.yaml", epochs = 20, imgsz = 640)

네트워크 너무 불안하여 학습을 시키면서 많은 어려움이 있었다… (계속 날라감 ;;;)

그래서 resume을 이용해 어찌 저찌 했다…

model = YOLO("/content/drive/MyDrive/yolo26_seg/runs/segment/train5/weights/last.pt")

model.train(resume=True)

초반에 1 epoch당 4분 16초 씩 걸려서 뭔가 봤더니 1 ~ 10 epoch 까지 데이터 증강 (모자이크) 로 학습되고 있었다.

• 출력로그

    Starting training for 20 epochs...
  
          Epoch    GPU_mem   box_loss   seg_loss   cls_loss   dfl_loss   sem_loss  Instances       Size
           5/20      5.39G      1.774      1.801      1.436   0.006005     0.7486        499        640: 100% ━━━━━━━━━━━━ 202/202 4.8s/it 16:16
                     Class     Images  Instances      Box(P          R      mAP50  mAP50-95)     Mask(P          R      mAP50  mAP50-95): 100% ━━━━━━━━━━━━ 12/12 1.4s/it 16.7s
                       all        362      12168       0.73      0.677      0.738      0.425      0.473      0.441      0.375      0.165
  
          Epoch    GPU_mem   box_loss   seg_loss   cls_loss   dfl_loss   sem_loss  Instances       Size
           6/20      5.64G      1.722      1.702      1.291   0.005731     0.7424        435        640: 100% ━━━━━━━━━━━━ 202/202 1.3s/it 4:17
                     Class     Images  Instances      Box(P          R      mAP50  mAP50-95)     Mask(P          R      mAP50  mAP50-95): 100% ━━━━━━━━━━━━ 12/12 1.3s/it 15.4s
                       all        362      12168      0.739       0.67      0.742      0.451      0.455      0.422      0.359      0.144
  
          Epoch    GPU_mem   box_loss   seg_loss   cls_loss   dfl_loss   sem_loss  Instances       Size
           7/20      5.67G      1.685      1.657      1.241   0.005478     0.6747        592        640: 100% ━━━━━━━━━━━━ 202/202 1.3s/it 4:17
                     Class     Images  Instances      Box(P          R      mAP50  mAP50-95)     Mask(P          R      mAP50  mAP50-95): 100% ━━━━━━━━━━━━ 12/12 1.3s/it 15.8s
                       all        362      12168      0.745      0.685      0.754      0.452      0.463      0.423      0.362      0.141
  
          Epoch    GPU_mem   box_loss   seg_loss   cls_loss   dfl_loss   sem_loss  Instances       Size
           8/20      5.48G      1.656      1.631      1.202   0.005329     0.6483        424        640: 100% ━━━━━━━━━━━━ 202/202 1.3s/it 4:16
                     Class     Images  Instances      Box(P          R      mAP50  mAP50-95)     Mask(P          R      mAP50  mAP50-95): 100% ━━━━━━━━━━━━ 12/12 1.2s/it 14.7s
                       all        362      12168      0.752      0.693      0.764      0.473      0.429      0.384      0.327       0.12
  
          Epoch    GPU_mem   box_loss   seg_loss   cls_loss   dfl_loss   sem_loss  Instances       Size
           9/20      5.53G      1.652      1.652       1.19   0.005447     0.6792        416        640: 100% ━━━━━━━━━━━━ 202/202 1.3s/it 4:16
                     Class     Images  Instances      Box(P          R      mAP50  mAP50-95)     Mask(P          R      mAP50  mAP50-95): 100% ━━━━━━━━━━━━ 12/12 1.3s/it 16.0s
                       all        362      12168      0.765       0.69      0.768      0.458       0.46      0.418      0.352      0.152
  
          Epoch    GPU_mem   box_loss   seg_loss   cls_loss   dfl_loss   sem_loss  Instances       Size
          10/20      5.54G       1.62      1.619      1.145   0.005209     0.6139        444        640: 100% ━━━━━━━━━━━━ 202/202 1.3s/it 4:17
                     Class     Images  Instances      Box(P          R      mAP50  mAP50-95)     Mask(P          R      mAP50  mAP50-95): 100% ━━━━━━━━━━━━ 12/12 1.3s/it 15.8s
                       all        362      12168      0.773      0.703      0.775      0.484      0.481      0.432      0.371      0.158
    Closing dataloader mosaic

총 소요시간 : 1시간 20분 정도

Ultralytics 8.4.17 🚀 Python-3.12.12 torch-2.10.0+cu128 CUDA:0 (Tesla T4, 14913MiB)
YOLO26n-seg summary (fused): 139 layers, 2,689,079 parameters, 0 gradients, 9.0 GFLOPs
                 Class     Images  Instances      Box(P          R      mAP50  mAP50-95)     Mask(P          R      mAP50  mAP50-95): 100% ━━━━━━━━━━━━ 12/12 1.5s/it 18.1s
                   all        362      12168      0.842      0.769      0.842      0.585      0.499      0.449      0.378       0.15
Speed: 0.3ms preprocess, 4.9ms inference, 0.0ms loss, 6.0ms postprocess per image

mAP50 기준으로 BOX는 84%로 잘 찾아내는 모습을 보였지만 Mask는 37%로 처첨했다.

일단 결과를 해석해보면 train loss 값이 떨어짐과 동시에 val loss 값도 같이 떨어지는 모습을 보이고 있다. 특히 데이터 증강이 있던 에포크 10을 기점으로 loss 값이 튀는 걸 볼 수 있지만 다행히 잘 줄어 들었다.

종합해 봤을 때 적은 에포크 수로 인해 학습이 덜 되었던 것 같다.

정확도를 높이기 위하여

정확도를 높이기 위해 뭘 생각해야할까?

• 에포크가 너무 부족했나?
• 데이터 셋이 부족한가? 증강이 더 필요하나?
• 이미지크기가 너무 작았나? (현재 640)

에포크수와 이미지 크기를 조금더 키워서 다시 학습시켜 보겠다.

model = YOLO("yolo26n-seg.pt")

model.train(data="/content/drive/MyDrive/yolo26_seg/data.yaml", epochs = 50, imgsz = 800, name = "train_is800_e50")

하으…. 하루 사용량을 다 사용한 것 같다.

• log 메세지

| Timestamp | Level | Message |
| --- | --- | --- |
| Feb 26, 2026, 5:57:10 PM | WARNING | 0\.00s - Note: Debugging will proceed\. Set PYDEVD\_DISABLE\_FILE\_VALIDATION=1 to disable this validation\. |
| Feb 26, 2026, 5:57:10 PM | WARNING | 0\.00s - to python to disable frozen modules\. |
| Feb 26, 2026, 5:57:10 PM | WARNING | 0\.00s - make the debugger miss breakpoints\. Please pass -Xfrozen\_modules=off |
| Feb 26, 2026, 5:57:10 PM | WARNING | 0\.00s - Debugger warning: It seems that frozen modules are being used, which may |
| Feb 26, 2026, 5:57:08 PM | WARNING | kernel 3bc7ac6d-2692-417e-b5ff-4f53a4ad0116 restarted |
| Feb 26, 2026, 5:57:08 PM | INFO | AsyncIOLoopKernelRestarter: restarting kernel \(1/5\), keep random ports |
| Feb 26, 2026, 5:53:16 PM | WARNING | 0\.00s - Note: Debugging will proceed\. Set PYDEVD\_DISABLE\_FILE\_VALIDATION=1 to disable this validation\. |
| Feb 26, 2026, 5:53:16 PM | WARNING | 0\.00s - to python to disable frozen modules\. |
| Feb 26, 2026, 5:53:16 PM | WARNING | 0\.00s - make the debugger miss breakpoints\. Please pass -Xfrozen\_modules=off |
| Feb 26, 2026, 5:53:16 PM | WARNING | 0\.00s - Debugger warning: It seems that frozen modules are being used, which may |
| Feb 26, 2026, 5:53:14 PM | WARNING | kernel 3bc7ac6d-2692-417e-b5ff-4f53a4ad0116 restarted |
| Feb 26, 2026, 5:53:14 PM | WARNING | kernel 3bc7ac6d-2692-417e-b5ff-4f53a4ad0116 restarted |

imgsz를 800으로 돌렸더니 메모리부족으로 병목현상이 발생하였다.

해결방안으로 배치 크기를 8까지 줄였더니 돌아가긴 했지만 대략 1%올라가는데 2~3분 정도 걸리고 있다.

오늘 안으로 학습이 힘들것 같아 gpu가 죽기 전에 23 에포크 까지의 결과로 비교를 해보겠다.

segmention만 비교하도록 하겠다.

20 에포크를 비교하였을 때 mAP50 기준 imgsz를 늘렸을 때 48%로 이전 37%였던 결과물에 비해 정확도가 많이 상승한 것을 확인할 수 있었다.

마지막 에포크인 23에포크 에서도 mAP50 - 51% mAP50-95 23%로 정확도가 상승곡선을 그리고 있었다.

💡 마무리 하며

하이퍼파라미터 튜닝을 통해 AI 성능 최적화의 흐름을 이해할 수 있었다.

또한, 물리적인 컴퓨팅 자원(GPU/RAM)과 학습 효율 간의 상관관계를 직접 경험할 수 있었다.

수치 너머의 맥락을 읽는 법을 배우며 인공지능을 다루는 큰 틀을 잡는 유익한 과정이었습니다.

Instance Segmentation - Ultralytics YOLO Docs

Ultralytics YOLO 하이퍼파라미터 튜닝 가이드 - Ultralytics YOLO Docs

영상 데이터를 기반으로 한 대회인 ILSVRC2012에서 우승한 CNN 구조이다. Alex Krzhevsky의 이름을 따서 AlexNet이라고 부른다. Convolution Layer 5개와 Fully Connected Layer 3개로 구성되어 있다.

AlenNet 구조

특징

ReLU Activation Function

tanh 활성화함수를 사용하였을 때보다 ReLU활성화 함수를 사용하였을 때 Error rate를 매우 빠르게 0.25에 도달시켰다.

max pooling

maxpooling을 사용해 이미지의 특징을 추출했다. 이때 stride값을 kernel size보다 작게하여 overrapping이 발생되도록 하였다. → non-overrapping 모델보다 정확도 상승

overrapping? kernel을 겹치게하여 뉴런들이 중복되게 풀링을 진행하는 것을 말한다.

Mulitple GPUs

2개의 GPU를 사용해 병렬적으로 학습할 수 있도록 구조를 설계하였다.

논문

proceedings.neurips.cc

[CNN] AlexNet 논문리뷰 (velog.io)

[DL][CNN] AlexNet 개념 및 Pytorch 구현 (tistory.com)

딥러닝 CNN 모델 살펴보기(1) : AlexNet 논문 리뷰 : 네이버 블로그 (naver.com)

VGGNet

VGGNet은 네트워크의 깊이가 성능에 미치는 영향을 분석하기 위하여 설계된 CNN 모델이다. 기존 모델보다 깊은 계층을 가지기위해 합성곱의 Kernel을 3x3으로 통일 시켰다.

VGGNet 구조

VGG16과 VGG19는 성능을 비교하기위해 계층을 16개 19개 다른 구조를 만들었다.

A에서 D → E 점차 계층의 깊이가 깊어질 수 록 Error rate이 점차 감소하여 성능이 좋아지는 것을 알게되었다.

VGG16의 계층 구조이다.

[CNN 알고리즘들] VGGNet의 구조 (VGG16) by bskyvision.com

[DL][CNN] VGGNet 개념 및 Pytorch 구현

ResNet

CNN 모델들이 단순하게 Layer을 깊게 쌓을 수록 성능이 더 좋아질 것 이라고 예상했지만 20층 이상부터는 성능이 낮아지는 현상이 발생 “Degradation” (VGG는 19층까지만 쌓았다) 하지만 ResNet은 Residual Learning을 통해 152층까지 쌓아 모델을 만들었다.

ResNet의 구조

ResNet은 기존 VGG의 구조와 깊이의 차이 말고 layer의 차이는 크게 없다. 하지만 보는 것과 같이 화살표들이 막 연결된 구조를 확인할 수 있다. 바로 skip connection을 표시한 것으로 계층을 깊게 쌓아도 더 좋은 성능을 낼 수 있게 해준것이다.

Skip-connection을 사용한 모델이 20층 이상의 모델에서 error가 떨어지는 것을 볼 수 있다.

Skip-connection

Skip-connection은 layer의 입력을 layer의 출력에 바로 연결시키는 것을 말한다.

원래는 네트워크 뉴런은 $H(x) = F(x)$ 를 찾기위하여 학습을 했다면

Skip-connection을 적용시켜 보면 $H(x) = F(x) + x$로 바뀌게 된다.

자 이제 생각해보자 계층이 쌓일수록 가중치의 변화량을 적어질 것이다. ( 역전파가 원활하게 이루어지지 않을 것이니 ) H(x) 가 x 와 근사한다고 했을 때 F(x)는 0에 가까워지는 방향으로 학습을 하면 된다. 훨씬 학습하기 쉬워진다.

정리하자면 학습할 때 입력과 출력의 차이 $H(x) -x$ 잔차(Residual)만 학습하는 것이다.

논문

arxiv.org

[DL][CNN] ResNet 개념 및 Pytorch 구현

3) ResNet, ResNet의 확장(레이어 152개 이하) - 한땀한땀 딥러닝 컴퓨터 비전 백과사전8. CNN 구조 3 - VGGNet, ResNet : 네이버 블로그

배치 정규화, Batch Normalization

왜 사용하는 것 일까. 흔히 말해 학습시간을 줄이거나 모델이 Local optimum에 빠지지 않도록 또, overfitting에 빠지지않도록 하기위해서 라고 한다.

Internal Covariance shift

공부를 하며 단 한번도 빠지지 않고 나온 개념이었다. 뜻을 알아보겠다.

Convariance - 공변량

Convariance은 변수의 개념을 가지고 있다. 보통 종속변수와 독립변수을 흔하게 알고 있다. 하지만 여러 잡음이 섞여 독립변수와 종속변수의 관계를 설명하지 못하는 경우가 있다.

이때, 독립변수와 종속변수의 관계를 설명할 때 방해가 될 수 있는 요인을 공변량이라고 한다.

Covariance shift

이전 layer의 파라미터의 변화로 인해 현재 layer의 입력의 분포가 바뀌는 현상이라고 한다.

Internal Covariance shift

Covariance shift의 정의보다 조금더 확장되어서 입력 데이터가 model의 layer에 통과되면서 분산이 달라니는 것. 즉, 원래의 데이터에서 왜곡된다는 의미이다.

자 생각해보자 우리는 모델을 학습시켜서 입력값을 넣었을 때 원하는 결과값을 얻고 싶다. 하지만 input이 layer들을 통과될 수록 가중치들이 곱해지고 왜곡이 일어난다.

조금 다르게 말하면 training dataset을 학습시키면 분포가 test dataset과 달라져 우리가 원하는 결과와 멀어진다. 이것이 Overfitting이다.

계층을 통과하고 나면 데이터 분포가 달라지고 있다.

Internal Covariance shift 해결방안

Internal Covariance shift의 해결방안은 Batch Normalization이다.

정말 쉽게 직관적으로 봤을 때 단순히 분포의 위치와 크기를 바꿔주면 해결이 된다고 생각할 수 있다. ( 이게 바로 Bath Normalization )

계산과정을 살펴 보겠다.

미니배치 평균 → 미니배치 분산 → 정규화 → 스케일 조정 및 이동

• mini-batch mean

$$ \mu_{\mathcal{B}} \leftarrow \frac{1}{m} \sum_{i=1}^{m} x_i $$

• mini-batch variance

$$ \sigma_{\mathcal{B}}^2 \leftarrow \frac{1}{m} \sum_{i=1}^{m} (x_i - \mu_{\mathcal{B}})^2 $$

• normalize

$$ \widehat{x}i \leftarrow \frac{x_i - \mu{\mathcal{B}}}{\sqrt{\sigma_{\mathcal{B}}^2 + \epsilon}} $$

평균은 0, 분산은 1

• scale and shift

$$ y_i \leftarrow \gamma \widehat{x}i + \beta \equiv \text{BN}{\gamma,\beta}(x_i) $$

마지막에 보이는 감마와 배타가 정규화를 통해 얻은 분산을 넓게/좁게 그리고 좌우로 이동시키는 역할을 한다.

감마와 베타는 역전파 단계에서 업데이트된다. 위는 감마와 베타가 적용되는 수식이다.

Batch Normalization 순서

Batch Normalization은 layer와 활성화 함수 사이에 들어가 동작을 수행하게 된다.

BatchNorm2d

BatchNorm2d 은 2차원 이미지를 학습할 때 배치 정규화과정에서 사용된다.

 torch.nn.BatchNorm2d(*num_features*, *eps=1e-05*, *momentum=0.1*, *affine=True*, *track_running_stats=True*, *device=None*, *dtype=None*)

num_features: 입력 데이터의 채널 수.

eps: 수치적 안정성을 위해 분모에 더해주는 값.

momentum: 매치마다 계산된 평균/분산을 누적할 때 사용하는 계수.

affine: True일 경우, 학습 가능한 $\gamma$와 $\beta$를 사용

track_running_stats: True일 경우, 학습 중 계산한 평균/분산을 기록해두었다가 추론(Inference) 시에 사용.

BatchNorm2d — PyTorch 2.10 documentation

감사합니다. Batch Normalization (velog.io) [CNN] Batch Normalization(배치 정규화) (velog.io) [Deep Learning] Batch Normalization (배치 정규화) (tistory.com)

여러 층의 노드들이 연결되어 있어 전층결합(Fully Connected Layer) 라고 부른다. 입력층 - 은닉층 - 출력층 구조를 이루고 있으며 정형 데이터를 처리할 때 아주 효과적이다.

MLP로 모델 구현

import numpy as np
import matplotlib.pyplot as plt

import torch
from torch import nn
import torch.nn.functional as F
from torch.utils.data import DataLoader
from torchvision import datasets, transforms

BATCH_SIZE = 32
EPOCHS = 10

train_dataset = datasets.MNIST(root = "../data/MNIST", train = True, download=True, transform = transforms.ToTensor())
test_dataset = datasets.MNIST(root = "../data/MNIST", train = False, download=True, transform = transforms.ToTensor())

train_loader = DataLoader(train_dataset, batch_size = BATCH_SIZE, shuffle = True)
test_loader = DataLoader(test_dataset,batch_size = BATCH_SIZE, shuffle = False) 

train_dataset, test_dataset 에 datasets으로 MNIST 데이터 셋을 불러오고 있다. root 경로에 가져온다. train 을 True, False로 명시해서 사용할 수 있다. transforms.Totensor() 을 통해 데이터 셋을 Tensor로 변환시켰다.

DataLoader 를 통해 batch_size, shuffle 여부를 결정할 수 있다. ( test set의 경우에는 섞지 않는다.)

for(X_train, y_train) in train_loader:
  print(X_train.shape)
  print(y_train.shape)
  break

pltsize = 1
plt.figure(figsize=(10 * pltsize, pltsize)) #10개 plot하기 위한 figure 크기 설정

for i in range(10):
    plt.subplot(1, 10, i + 1) # plot.subplot(rows, columns, index)
    plt.axis('off')
    plt.imshow(X_train[i, :, :, :].numpy().reshape(28, 28), cmap = "gray_r")
    plt.title('Class: ' + str(y_train[i].item()))

class MLP(nn.Module):
  def __init__(self):
    super(MLP, self).__init__()
    self.fc1 = nn.Linear(28*28, 512)
    self.fc2 = nn.Linear(512, 256)
    self.fc3 = nn.Linear(256, 10)

  def forward(self, x):
    x = x.view(-1, 28*28)
    x = F.relu(self.fc1(x))
    x = F.relu(self.fc2(x))
    x = self.fc3(x)
    x = F.log_softmax(x, dim=1)
    return x

모델 클래스를 정의 했다. view()를 통해 1차원으로 다시 나열했다.

이후 Linear층 → relu 함수를 반복하며 특징을 뽑아냈다.

relu 함수는 0이하의 값은 모두 0으로 0보다 큰 값은 그대로 쓰는 함수이다.

마지막으로 log_softmax를 통해 fc3에서 나온 결과값을 계산해 합계를 100%(0.1)로 만드는 과정이다.

log_softmax([input], [dim]) dim=1은 가로방향(행)으로 계산, dim=0은 세로방향(열)로 계산

model = MLP().to(device=torch.device("cpu"))
optimizer = torch.optim.SGD(model.parameters(), lr=0.01, momentum=0.5)
criterion = nn.CrossEntropyLoss()

CrossEntropyLoss() 기존의 MESLoss() 과 같은 역할을 하지만 모델이 분류하고자 하는 목적이 다르기 때문에 CrossEntropyLoss() 가 더 적합하다.

def train (model, train_loader, optimizer, log_interval):
  model.train()
  for batch_idx, (image, label) in enumerate(train_loader):
    image = image.to(device=torch.device("cpu"))
    label = label.to(device=torch.device("cpu"))  
    optimizer.zero_grad()
    output = model(image)
    loss = criterion(output, label)
    loss.backward()
    optimizer.step()

    if batch_idx % log_interval == 0:
      print("Train epoch: {} [{}/{} ({:.0f}%)]\tTrain Loss: {:.6f}".format(
                epoch, batch_idx * len(image),
                len(train_loader.dataset), 100. * batch_idx / len(train_loader),
                loss.item()))

모델을 학습 시키는 과정이다. 인자로 모델과 학습 데이터, optimizer, 로그를 띄우는 인자를 받고 있다. 위에서 만든 criterion()함수를 이용해 output과 label 을 넣고 loss를 구하고 있다.

def evaluate(model, test_loader):
    model.eval()
    test_loss = 0
    correct = 0

    with torch.no_grad():
        for image, label in test_loader:
            image = image.to(torch.device("cpu"))
            label = label.to(torch.device("cpu"))
            output = model(image)
            test_loss += criterion(output, label).item()
            prediction = output.max(1, keepdim=True)[1]
            correct += prediction.eq(label.view_as(prediction)).sum().item()

    test_loss /= (len(test_loader.dataset)/ BATCH_SIZE)
    test_accuracy = 100. * correct/len(test_loader.dataset)
    return test_loss, test_accuracy

모델이 잘 학습 되었는지 확인하기 위한 검증함수 이다.

for epoch in range(1, EPOCHS + 1):
  train(model, train_loader, optimizer, log_interval=200)
  test_loss, test_accuracy = evaluate(model, test_loader)
  print("\n[EPOCH: {}], \tTest Loss: {:.4f}, \tTest Accuracy: {:.2f} %\n".format(
        epoch, test_loss, test_accuracy))

실제 코드를 돌리는 부분이다.

출력결과

Train epoch: 1 [0/60000 (0%)]    Train Loss: 2.295880
Train epoch: 1 [6400/60000 (11%)]    Train Loss: 1.856210
Train epoch: 1 [12800/60000 (21%)]    Train Loss: 0.766492
Train epoch: 1 [19200/60000 (32%)]    Train Loss: 0.451512
Train epoch: 1 [25600/60000 (43%)]    Train Loss: 0.649790
Train epoch: 1 [32000/60000 (53%)]    Train Loss: 0.578205
Train epoch: 1 [38400/60000 (64%)]    Train Loss: 0.283212
Train epoch: 1 [44800/60000 (75%)]    Train Loss: 0.336932
Train epoch: 1 [51200/60000 (85%)]    Train Loss: 0.262401
Train epoch: 1 [57600/60000 (96%)]    Train Loss: 0.398156

[EPOCH: 1],     Test Loss: 0.3243,     Test Accuracy: 90.29 %

Train epoch: 2 [0/60000 (0%)]    Train Loss: 0.354413
Train epoch: 2 [6400/60000 (11%)]    Train Loss: 0.369770
Train epoch: 2 [12800/60000 (21%)]    Train Loss: 0.291158
Train epoch: 2 [19200/60000 (32%)]    Train Loss: 0.519158
Train epoch: 2 [25600/60000 (43%)]    Train Loss: 0.156046
Train epoch: 2 [32000/60000 (53%)]    Train Loss: 0.158155
Train epoch: 2 [38400/60000 (64%)]    Train Loss: 0.243987
Train epoch: 2 [44800/60000 (75%)]    Train Loss: 0.248704
Train epoch: 2 [51200/60000 (85%)]    Train Loss: 0.162071
Train epoch: 2 [57600/60000 (96%)]    Train Loss: 0.095227

[EPOCH: 2],     Test Loss: 0.2261,     Test Accuracy: 93.38 %

Train epoch: 3 [0/60000 (0%)]    Train Loss: 0.106720
Train epoch: 3 [6400/60000 (11%)]    Train Loss: 0.385983
Train epoch: 3 [12800/60000 (21%)]    Train Loss: 0.193502
Train epoch: 3 [19200/60000 (32%)]    Train Loss: 0.542263
Train epoch: 3 [25600/60000 (43%)]    Train Loss: 0.047341
Train epoch: 3 [32000/60000 (53%)]    Train Loss: 0.072650
Train epoch: 3 [38400/60000 (64%)]    Train Loss: 0.396035
Train epoch: 3 [44800/60000 (75%)]    Train Loss: 0.041442
Train epoch: 3 [51200/60000 (85%)]    Train Loss: 0.278256
Train epoch: 3 [57600/60000 (96%)]    Train Loss: 0.334667

[EPOCH: 3],     Test Loss: 0.1803,     Test Accuracy: 94.75 %

Train epoch: 4 [0/60000 (0%)]    Train Loss: 0.094163
Train epoch: 4 [6400/60000 (11%)]    Train Loss: 0.351428
Train epoch: 4 [12800/60000 (21%)]    Train Loss: 0.372503
Train epoch: 4 [19200/60000 (32%)]    Train Loss: 0.278116
Train epoch: 4 [25600/60000 (43%)]    Train Loss: 0.112307
Train epoch: 4 [32000/60000 (53%)]    Train Loss: 0.087376
Train epoch: 4 [38400/60000 (64%)]    Train Loss: 0.073601
Train epoch: 4 [44800/60000 (75%)]    Train Loss: 0.319843
Train epoch: 4 [51200/60000 (85%)]    Train Loss: 0.114105
Train epoch: 4 [57600/60000 (96%)]    Train Loss: 0.057666

[EPOCH: 4],     Test Loss: 0.1575,     Test Accuracy: 95.36 %

Train epoch: 5 [0/60000 (0%)]    Train Loss: 0.132325
Train epoch: 5 [6400/60000 (11%)]    Train Loss: 0.175407
Train epoch: 5 [12800/60000 (21%)]    Train Loss: 0.221547
Train epoch: 5 [19200/60000 (32%)]    Train Loss: 0.056232
Train epoch: 5 [25600/60000 (43%)]    Train Loss: 0.489672
Train epoch: 5 [32000/60000 (53%)]    Train Loss: 0.482867
Train epoch: 5 [38400/60000 (64%)]    Train Loss: 0.065646
Train epoch: 5 [44800/60000 (75%)]    Train Loss: 0.091367
Train epoch: 5 [51200/60000 (85%)]    Train Loss: 0.063387
Train epoch: 5 [57600/60000 (96%)]    Train Loss: 0.184671

[EPOCH: 5],     Test Loss: 0.1306,     Test Accuracy: 96.05 %

Train epoch: 6 [0/60000 (0%)]    Train Loss: 0.016412
Train epoch: 6 [6400/60000 (11%)]    Train Loss: 0.174848
Train epoch: 6 [12800/60000 (21%)]    Train Loss: 0.043638
Train epoch: 6 [19200/60000 (32%)]    Train Loss: 0.147906
Train epoch: 6 [25600/60000 (43%)]    Train Loss: 0.169951
Train epoch: 6 [32000/60000 (53%)]    Train Loss: 0.175466
Train epoch: 6 [38400/60000 (64%)]    Train Loss: 0.065988
Train epoch: 6 [44800/60000 (75%)]    Train Loss: 0.097291
Train epoch: 6 [51200/60000 (85%)]    Train Loss: 0.031171
Train epoch: 6 [57600/60000 (96%)]    Train Loss: 0.107508

[EPOCH: 6],     Test Loss: 0.1180,     Test Accuracy: 96.46 %

Train epoch: 7 [0/60000 (0%)]    Train Loss: 0.023183
Train epoch: 7 [6400/60000 (11%)]    Train Loss: 0.041281
Train epoch: 7 [12800/60000 (21%)]    Train Loss: 0.075828
Train epoch: 7 [19200/60000 (32%)]    Train Loss: 0.052879
Train epoch: 7 [25600/60000 (43%)]    Train Loss: 0.021749
Train epoch: 7 [32000/60000 (53%)]    Train Loss: 0.198561
Train epoch: 7 [38400/60000 (64%)]    Train Loss: 0.050543
Train epoch: 7 [44800/60000 (75%)]    Train Loss: 0.075291
Train epoch: 7 [51200/60000 (85%)]    Train Loss: 0.125982
Train epoch: 7 [57600/60000 (96%)]    Train Loss: 0.064391

[EPOCH: 7],     Test Loss: 0.1011,     Test Accuracy: 96.92 %

Train epoch: 8 [0/60000 (0%)]    Train Loss: 0.016860
Train epoch: 8 [6400/60000 (11%)]    Train Loss: 0.117673
Train epoch: 8 [12800/60000 (21%)]    Train Loss: 0.019247
Train epoch: 8 [19200/60000 (32%)]    Train Loss: 0.225010
Train epoch: 8 [25600/60000 (43%)]    Train Loss: 0.073858
Train epoch: 8 [32000/60000 (53%)]    Train Loss: 0.155419
Train epoch: 8 [38400/60000 (64%)]    Train Loss: 0.107518
Train epoch: 8 [44800/60000 (75%)]    Train Loss: 0.042732
Train epoch: 8 [51200/60000 (85%)]    Train Loss: 0.402344
Train epoch: 8 [57600/60000 (96%)]    Train Loss: 0.028305

[EPOCH: 8],     Test Loss: 0.0939,     Test Accuracy: 97.07 %

Train epoch: 9 [0/60000 (0%)]    Train Loss: 0.126242
Train epoch: 9 [6400/60000 (11%)]    Train Loss: 0.168472
Train epoch: 9 [12800/60000 (21%)]    Train Loss: 0.033166
Train epoch: 9 [19200/60000 (32%)]    Train Loss: 0.030906
Train epoch: 9 [25600/60000 (43%)]    Train Loss: 0.017684
Train epoch: 9 [32000/60000 (53%)]    Train Loss: 0.095147
Train epoch: 9 [38400/60000 (64%)]    Train Loss: 0.020783
Train epoch: 9 [44800/60000 (75%)]    Train Loss: 0.146282
Train epoch: 9 [51200/60000 (85%)]    Train Loss: 0.047931
Train epoch: 9 [57600/60000 (96%)]    Train Loss: 0.105028

[EPOCH: 9],     Test Loss: 0.0915,     Test Accuracy: 97.25 %

Train epoch: 10 [0/60000 (0%)]    Train Loss: 0.027292
Train epoch: 10 [6400/60000 (11%)]    Train Loss: 0.144544
Train epoch: 10 [12800/60000 (21%)]    Train Loss: 0.009972
Train epoch: 10 [19200/60000 (32%)]    Train Loss: 0.008092
Train epoch: 10 [25600/60000 (43%)]    Train Loss: 0.026988
Train epoch: 10 [32000/60000 (53%)]    Train Loss: 0.019556
Train epoch: 10 [38400/60000 (64%)]    Train Loss: 0.048808
Train epoch: 10 [44800/60000 (75%)]    Train Loss: 0.107426
Train epoch: 10 [51200/60000 (85%)]    Train Loss: 0.011870
Train epoch: 10 [57600/60000 (96%)]    Train Loss: 0.113121

[EPOCH: 10],     Test Loss: 0.0856,     Test Accuracy: 97.40 %

CNN ( Convolutional Neural Network )

합성 곱 신경망으로 Convolution Layer와 Pooling Layer 층을 가지고 구성된다.

CNN 모델 구현

import torch
from torch import nn
import torch.nn.functional as F
from torch.utils.data import DataLoader
from torchvision import datasets, transforms

DEVICE = 'cuda' if torch.cuda.is_available() else 'cpu'
BATCH_SIZE = 32
EPOCHS = 10

train_dataset = datasets.MNIST(root = "../data/MNIST", train =True, download=True, transform = transforms.ToTensor())
test_dataset = datasets.MNIST(root = "../data/MNIST", train = False, download=True, transform = transforms.ToTensor())

train_loader = DataLoader(train_dataset, batch_size = BATCH_SIZE, shuffle = True)
test_loader = DataLoader(test_dataset,batch_size = BATCH_SIZE, shuffle = False) 

from torch.nn.modules import ReLU
class CNN(nn.Module):
    def __init__(self):
        super(CNN, self).__init__()
        self.keep_prob=0.5

        self.layer1 = torch.nn.Sequential(
            torch.nn.Conv2d(1,32,kernel_size=3,stride=1,padding=1),
            torch.nn.ReLU(),
            torch.nn.MaxPool2d(kernel_size=2,stride=2)
        )
        self.layer2 = torch.nn.Sequential(
            torch.nn.Conv2d(32,64,kernel_size=3,stride=1,padding=1),
            torch.nn.ReLU(),
            torch.nn.MaxPool2d(kernel_size=2,stride=2)
        )
        self.layer3 = torch.nn.Sequential(
            torch.nn.Conv2d(64,128,kernel_size=3,stride=1,padding=1),
            torch.nn.ReLU(),
            torch.nn.MaxPool2d(kernel_size=2,stride=2)
        )


        self.fc1 = torch.nn.Linear(128 * 3 * 3, 625, bias=True)
        torch.nn.init.xavier_uniform_(self.fc1.weight) # 가중치 초기화

        self.layer4 = torch.nn.Sequential(
            self.fc1,
            torch.nn.ReLU(),
            torch.nn.Dropout(p=(1-self.keep_prob))
        )

        self.fc2 = torch.nn.Linear(625, 10, bias=True)
        torch.nn.init.xavier_uniform_(self.fc2.weight) # 가중치 초기화

    def forward(self, x):
        out = self.layer1(x)
        out = self.layer2(out)
        out = self.layer3(out)
        out = out.view(out.size(0), -1)
        out = self.layer4(out)
        out = self.fc2(out)
        return out

Sequential() 를 통해 게층을 하나로 묶었다. 이전 코드에서는 forward 과정에서 각각 호출에서 작성했지만 Sequential() 을 통해 코드르 간결화 시켰다. 전체적인 코드는 con층 3개 fc 층 2개로 이루어져있다. 가중치의 값이 너무 크거나 너무 작으면 원하는 값을 구하기 어려줘 진다. torch.nn.init.xavier_uniform_ 는 입력 노드와 출력 노드의 수를 고려하여 가중치값이 너무 치우치지 않도록 가중치 값을 초기화 시켜주는 역할을 가지고 있다.

[ 몇가지의 의문점 ] Conv2d의 함수에서 padding은 왜 사용하는 걸까? , Conv2d에서 출력 채널을 정하는 기준이 있을까?

padding은 들어온 이미지의 테두리에 가상의 픽셀을 추가하는 동작을 수행한다. 필터로 이미지를 보다보면 중앙 부분보다 가장자리 테두리 부분의 이미지 픽셀이 훨씬 적게 계산된다. (그만큼 중요도와 특징을 뽑아내지 못함) 이것을 완화하기 위해 padding을 사용해 방지한다.

직접적인 계산이 있는 것이 아닌 하이퍼파라미터이다. 현재 층 출력 채널과 다음 층 입력 채널을 맞춰주면 큰 문제는 없지만, 관습적으로 2의 제곱에 해당하는 숫자로 한다.

model = CNN().to(DEVICE)

criterion = nn.CrossEntropyLoss().to(DEVICE)
optimizer = torch.optim.Adam(model.parameters(), lr = 0.001)

optim 에서 SGD가 아닌 Adam을 사용했다. Adam은 SGD + Momentum + RMSProp의 장점을 합쳐서 사용하는 방식이다. 함정에 빠질 확률을 낮출 수 있다. 하지만 더욱 정교한 교정이 필요할 때에는 SGD로 사용하는 경우가 있다.

def train(model, train_loader, optimizer, log_interval):
    model.train()

    for batch_idx, (image, label) in enumerate(train_loader):
      image = image.to(DEVICE)
      label = label.to(DEVICE)

      optimizer.zero_grad()
      output = model(image)
      loss = criterion(output, label)
      loss.backward()
      optimizer.step()

      if batch_idx % log_interval == 0:
        print("Train epoch: {} [{}/{} ({:.0f}%)]\tTrain Loss: {:.6f}".format(
                epoch, batch_idx * len(image),
                len(train_loader.dataset), 100. * batch_idx / len(train_loader),
                loss.item()))

모델을 학습 시키는 함수이다.

def evaluation(model, test_loader):
    model.eval()
    test_loss = 0
    correct = 0

    with torch.no_grad():
        for image, label in test_loader:
            image = image.to(DEVICE)
            label = label.to(DEVICE)

            output = model(image)
            test_loss += criterion(output, label).item()
            prediction = output.max(1, keepdim=True)[1]
            correct += prediction.eq(label.view_as(prediction)).sum().item()

    test_loss /= (len(test_loader.dataset)/ BATCH_SIZE)
    test_accuracy = 100. * correct/len(test_loader.dataset)
    return test_loss, test_accuracy

모델이 얼마나 학습했는지 test data set을 이용해 검증하는 함수이다.

for epoch in range(1, EPOCHS + 1):
    train(model, train_loader, optimizer, log_interval=200)
    test_loss, test_accuracy = evaluation(model, test_loader)
    print("\n[EPOCH: {}], \tTest Loss: {:.4f}, \tTest Accuracy: {:.2f} %\n".format(
        epoch, test_loss, test_accuracy))

출력결과

Train epoch: 1 [0/60000 (0%)]    Train Loss: 2.302500
Train epoch: 1 [6400/60000 (11%)]    Train Loss: 0.020710
Train epoch: 1 [12800/60000 (21%)]    Train Loss: 0.072938
Train epoch: 1 [19200/60000 (32%)]    Train Loss: 0.070585
Train epoch: 1 [25600/60000 (43%)]    Train Loss: 0.010864
Train epoch: 1 [32000/60000 (53%)]    Train Loss: 0.164177
Train epoch: 1 [38400/60000 (64%)]    Train Loss: 0.000477
Train epoch: 1 [44800/60000 (75%)]    Train Loss: 0.026269
Train epoch: 1 [51200/60000 (85%)]    Train Loss: 0.029791
Train epoch: 1 [57600/60000 (96%)]    Train Loss: 0.074889

[EPOCH: 1],     Test Loss: 0.0415,     Test Accuracy: 98.69 %

Train epoch: 2 [0/60000 (0%)]    Train Loss: 0.090489
Train epoch: 2 [6400/60000 (11%)]    Train Loss: 0.006572
Train epoch: 2 [12800/60000 (21%)]    Train Loss: 0.157872
Train epoch: 2 [19200/60000 (32%)]    Train Loss: 0.060257
Train epoch: 2 [25600/60000 (43%)]    Train Loss: 0.000952
Train epoch: 2 [32000/60000 (53%)]    Train Loss: 0.003554
Train epoch: 2 [38400/60000 (64%)]    Train Loss: 0.009752
Train epoch: 2 [44800/60000 (75%)]    Train Loss: 0.040368
Train epoch: 2 [51200/60000 (85%)]    Train Loss: 0.006694
Train epoch: 2 [57600/60000 (96%)]    Train Loss: 0.250820

[EPOCH: 2],     Test Loss: 0.0262,     Test Accuracy: 99.14 %

Train epoch: 3 [0/60000 (0%)]    Train Loss: 0.001073
Train epoch: 3 [6400/60000 (11%)]    Train Loss: 0.009513
Train epoch: 3 [12800/60000 (21%)]    Train Loss: 0.082231
Train epoch: 3 [19200/60000 (32%)]    Train Loss: 0.001920
Train epoch: 3 [25600/60000 (43%)]    Train Loss: 0.055383
Train epoch: 3 [32000/60000 (53%)]    Train Loss: 0.093025
Train epoch: 3 [38400/60000 (64%)]    Train Loss: 0.006312
Train epoch: 3 [44800/60000 (75%)]    Train Loss: 0.160864
Train epoch: 3 [51200/60000 (85%)]    Train Loss: 0.031659
Train epoch: 3 [57600/60000 (96%)]    Train Loss: 0.002794

[EPOCH: 3],     Test Loss: 0.0287,     Test Accuracy: 99.06 %

Train epoch: 4 [0/60000 (0%)]    Train Loss: 0.032770
Train epoch: 4 [6400/60000 (11%)]    Train Loss: 0.004879
Train epoch: 4 [12800/60000 (21%)]    Train Loss: 0.074115
Train epoch: 4 [19200/60000 (32%)]    Train Loss: 0.000641
Train epoch: 4 [25600/60000 (43%)]    Train Loss: 0.000061
Train epoch: 4 [32000/60000 (53%)]    Train Loss: 0.000526
Train epoch: 4 [38400/60000 (64%)]    Train Loss: 0.002731
Train epoch: 4 [44800/60000 (75%)]    Train Loss: 0.000543
Train epoch: 4 [51200/60000 (85%)]    Train Loss: 0.070365
Train epoch: 4 [57600/60000 (96%)]    Train Loss: 0.003590

[EPOCH: 4],     Test Loss: 0.0275,     Test Accuracy: 99.18 %

Train epoch: 5 [0/60000 (0%)]    Train Loss: 0.013684
Train epoch: 5 [6400/60000 (11%)]    Train Loss: 0.000570
Train epoch: 5 [12800/60000 (21%)]    Train Loss: 0.057022
Train epoch: 5 [19200/60000 (32%)]    Train Loss: 0.038811
Train epoch: 5 [25600/60000 (43%)]    Train Loss: 0.000251
Train epoch: 5 [32000/60000 (53%)]    Train Loss: 0.003567
Train epoch: 5 [38400/60000 (64%)]    Train Loss: 0.160953
Train epoch: 5 [44800/60000 (75%)]    Train Loss: 0.021606
Train epoch: 5 [51200/60000 (85%)]    Train Loss: 0.000387
Train epoch: 5 [57600/60000 (96%)]    Train Loss: 0.000611

[EPOCH: 5],     Test Loss: 0.0267,     Test Accuracy: 99.25 %

Train epoch: 6 [0/60000 (0%)]    Train Loss: 0.001599
Train epoch: 6 [6400/60000 (11%)]    Train Loss: 0.052861
Train epoch: 6 [12800/60000 (21%)]    Train Loss: 0.014980
Train epoch: 6 [19200/60000 (32%)]    Train Loss: 0.000985
Train epoch: 6 [25600/60000 (43%)]    Train Loss: 0.000812
Train epoch: 6 [32000/60000 (53%)]    Train Loss: 0.002275
Train epoch: 6 [38400/60000 (64%)]    Train Loss: 0.007388
Train epoch: 6 [44800/60000 (75%)]    Train Loss: 0.043215
Train epoch: 6 [51200/60000 (85%)]    Train Loss: 0.000217
Train epoch: 6 [57600/60000 (96%)]    Train Loss: 0.001535

[EPOCH: 6],     Test Loss: 0.0283,     Test Accuracy: 99.15 %

Train epoch: 7 [0/60000 (0%)]    Train Loss: 0.000100
Train epoch: 7 [6400/60000 (11%)]    Train Loss: 0.000396
Train epoch: 7 [12800/60000 (21%)]    Train Loss: 0.000071
Train epoch: 7 [19200/60000 (32%)]    Train Loss: 0.000645
Train epoch: 7 [25600/60000 (43%)]    Train Loss: 0.065544
Train epoch: 7 [32000/60000 (53%)]    Train Loss: 0.004502
Train epoch: 7 [38400/60000 (64%)]    Train Loss: 0.000171
Train epoch: 7 [44800/60000 (75%)]    Train Loss: 0.000013
Train epoch: 7 [51200/60000 (85%)]    Train Loss: 0.004819
Train epoch: 7 [57600/60000 (96%)]    Train Loss: 0.014584

[EPOCH: 7],     Test Loss: 0.0280,     Test Accuracy: 99.17 %

Train epoch: 8 [0/60000 (0%)]    Train Loss: 0.024070
Train epoch: 8 [6400/60000 (11%)]    Train Loss: 0.000015
Train epoch: 8 [12800/60000 (21%)]    Train Loss: 0.000056
Train epoch: 8 [19200/60000 (32%)]    Train Loss: 0.128571
Train epoch: 8 [25600/60000 (43%)]    Train Loss: 0.000719
Train epoch: 8 [32000/60000 (53%)]    Train Loss: 0.000371
Train epoch: 8 [38400/60000 (64%)]    Train Loss: 0.000062
Train epoch: 8 [44800/60000 (75%)]    Train Loss: 0.005178
Train epoch: 8 [51200/60000 (85%)]    Train Loss: 0.000601
Train epoch: 8 [57600/60000 (96%)]    Train Loss: 0.002863

[EPOCH: 8],     Test Loss: 0.0374,     Test Accuracy: 99.18 %

Train epoch: 9 [0/60000 (0%)]    Train Loss: 0.048398
Train epoch: 9 [6400/60000 (11%)]    Train Loss: 0.008198
Train epoch: 9 [12800/60000 (21%)]    Train Loss: 0.029910
Train epoch: 9 [19200/60000 (32%)]    Train Loss: 0.002376
Train epoch: 9 [25600/60000 (43%)]    Train Loss: 0.000050
Train epoch: 9 [32000/60000 (53%)]    Train Loss: 0.000209
Train epoch: 9 [38400/60000 (64%)]    Train Loss: 0.001148
Train epoch: 9 [44800/60000 (75%)]    Train Loss: 0.000002
Train epoch: 9 [51200/60000 (85%)]    Train Loss: 0.000002
Train epoch: 9 [57600/60000 (96%)]    Train Loss: 0.000423

[EPOCH: 9],     Test Loss: 0.0272,     Test Accuracy: 99.30 %

Train epoch: 10 [0/60000 (0%)]    Train Loss: 0.002476
Train epoch: 10 [6400/60000 (11%)]    Train Loss: 0.000269
Train epoch: 10 [12800/60000 (21%)]    Train Loss: 0.000115
Train epoch: 10 [19200/60000 (32%)]    Train Loss: 0.001352
Train epoch: 10 [25600/60000 (43%)]    Train Loss: 0.326977
Train epoch: 10 [32000/60000 (53%)]    Train Loss: 0.000599
Train epoch: 10 [38400/60000 (64%)]    Train Loss: 0.000920
Train epoch: 10 [44800/60000 (75%)]    Train Loss: 0.000658
Train epoch: 10 [51200/60000 (85%)]    Train Loss: 0.027969
Train epoch: 10 [57600/60000 (96%)]    Train Loss: 0.000011

[EPOCH: 10],     Test Loss: 0.0288,     Test Accuracy: 99.34 %

마지막….

이제 MLP CNN에서 사용되는 Linear, Conv2d가 익숙해지고 작동 원리가 이해되기 시작하는 단계인 것 같다. 코드 구현은 아직 익숙하지 않기에 완벽하지는 않다.(많이 쳐보면 될 문제이다.) 하지만, 코드 구조를 짜는 것은 아직 감이 안잡힌다. 몇개의 층을 사용해야 더 좋은 정확도가 도출될 것인가. 한번 고민하고 더 공부해봐야할 부분인 것 같다.

선형회귀는 입력 변수와 출력 변수 사이의 관계를 설명하는 직선을 찾는 기법

$y = Wx + b$

W(weight) - 가중치 b(Bias) - 편향

입력 값 x가 들어왔을 때 W와 b를 조정하며 정확한 y를 예측하는 것.!

Simple Linear Regression PyTorch 구현하기

목표

x(입력 값) [[1], [2], [3]] 이 y(출력 값) [[10.0], [20.0], [30.0]] 으로 되게 W와 b를 찾는 것이다.

x_train = torch.FloatTensor([[1], [2], [3]])
y_train = torch.FloatTensor([[10.0], [20.0], [30.0]])

라이브러리

import torch
import torch.optim as optim

torch.optim 패키지는 가중치 업데이트를 편리하도록 알고리즘을 모아둔 패키지이다.

가중치 && 편향

#weight 
W = torch.zeros(1,requires_grad=True)
#bias
b = torch.zeros(1,requires_grad=True)

requires_grad=True 은 텐서의 모든 연산을 기록하기 위해 사용한다. True로 설정을 해두면 torch가 모든 연산을 기록한다.

경사하강법

#Optimizer 설정
optimizer = optim.SGD([W,b],lr=0.01)

optim.SGD는 W,b를 0.01의 학습률을 이용해 값을 조정한다. 역전파로 계산된 기울기 값을 W = W - (lr - gradient) 을 이용해 조정한다.

가중치 업데이트

  optimizer.zero_grad()
  cost.backward()
  optimizer.step()

optimizer.zero_grad() 모델의 가중치 (W,b)에 저장되어있는 기울기를 0으로 초기화 한다. Pytorch는 역전파를 할때마다 기존값에 더해버리는 정실이 있기 때문에 원하는 학습결과를 위해 초기화해야한다. cost.backward() 오차를 기준으로 미분을 수행하여 기울기 값이 채워짐 optimizer.step() 학습률을 곱해서 실제 가중치를 업데이트 한다.

전체 코드

import torch
import torch.optim as optim

x_train = torch.FloatTensor([[1], [2], [3]])
y_train = torch.FloatTensor([[10.0], [20.0], [30.0]])

#weight 
W = torch.zeros(1,requires_grad=True)
#bias
b = torch.zeros(1,requires_grad=True)

#Optimizer 설정
optimizer = optim.SGD([W,b],lr=0.01)

nb_epochs = 10000
for epoch in range(1,nb_epochs+1):
  hypothesis = x_train * W + b
  cost = torch.mean((hypothesis - y_train)**2)

  optimizer.zero_grad()
  cost.backward()
  optimizer.step()

  if epoch % 1000 == 0:
    print(f'Epoch {epoch:4d}/{nb_epochs} W: {W.item():.3f}, b: {b.item():.3f} Cost: {cost.item():.6f}')

모델이 학습을 시작하기 전에 사용자가 설정해주는 “값”

Learning rate

학습률로, 모델이 학습을 할때 역전파(backward)를 통해 모델의 가중치를 얼마나 이동시킬지를 나타내는 값이다.

$$ W_{t+1} = W_t - \eta \nabla L(W_t) $$

이때 학습률에 따라 나타날 수 있는 상황이있다.

• 학습률이 너무 클 경우 - Loss가 발산하거나 Local Minimum 주변에서 진동(Oscillation)하며 수렴하지 못한다.
• 학습률이 너무 작을 경우 - 수렴 속도가 매우 느리며, Saddle point나 Shallow Local Minimum에 갇힐 위험이 큽니다.

Oscillation(진동) - 학습률이 너무 클경우 극값으로 가지 못하고 반대편 사면으로 오버슈팅되는 현상 Saddle point - $\nabla L(W) = 0$ 이지만 극소/극대값이 아닌 지점 임계점

Batch Size

모델이 한번 학습할 때 사용되는 데이터 샘플 수를 나타낸다.

Batch size 결정

작은 배치 사이즈

• 장점

  • 일반화 성능이 좋음
  • 메모리 효율 굿

• 단점

  • 학습속도가 느림
  • gradient의 분산이 커서 불안할 수 있음

큰 배치 사이즈

• 장점

  • 학습속도가 빠름

• 단점

  • 과적합 위험
  • 일반화 성능이 떨어질 수 있음

Epoch

전체 데이터셋이 신경망을 통과한 횟수

lteration은 1-epoch을 마치는데 필요한 미니배치 수를 의미한다. Step이라고 부르기도 한다.

Overfitting / Underfitting

Overfitting 과 Underfitting 발생 시 모델이 데이터를 정확하게 판단하지 못하는 결과를 가져온다. 발생하는 원인은 다르지만 모델에 성능에 영향을 끼친다.

Overfitting

모델이 데이터의 내재적 패턴(Signal)뿐만 아니라 샘플의 노이즈(Noise)까지 학습하여, 학습 데이터에만 특화된 결정 경계(Decision Boundary)를 형성하기 때문.

Underfitting

모델의 가중치 공간(Hypothesis Space)이 실제 데이터의 분포를 표현하기에 너무 작거나(Low Capacity), 학습이 충분히 이루어지지 않았을 때 발생한다.

손실 값 혹은 cost 라고 불리는 이 값은 우리가 돌리고 있는 모델의 예측값과 실제 정답 사이의 차이를 값을 표현한 것이다.

당연하게 차이의 값이 작으면 작을수록 예측값이 실제 정답과 가까워진다고 표현할 수 있다. 그러기에 Loss 값을 적게하는게 AI 구조를 다루는 개발자의 역할이다.

$$ Loss = \frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{y}_i)^2 $$

위에는 MSE 손실 함수로 Loss 값을 구하는 방정식이다.구한 Loss 값을 가지고 가중치(weight)와 편향(bais)를 Loss 값이 최소한의 값이 되도록 조정해야한다.

주요 손실함수

• MSE(Mean Squared Error) - 예측값과 실제값의 차이를 제곱한 뒤에 평균값을 낸 값
• MAE(Mean Absolute Error) - 예측값과 실제값의 절대 차이 평균을 구한 값

손실함수도 상황과 목적에 맞게 사용해야 모델의 성능을 이끌어낼 수 있다. MSE와 MAE는 회귀에 유용하게 쓰이는 손실함 수 이다. MSE는 오차에 크게 반응하고 MAE는 이상치에 좋다.

Gradient Descent

구한 손실함수를 가지고 어떻게 가중치(weight) 와 편향(bais)을 조절할까?

가중치(weight)의 변할 때 Loss 값이 어떻게 변하는지를 구해 더 최적의 값을 찾아야한다.

$$ \nabla L = \frac{\partial L}{\partial w} $$

가중치(weight) 변화에 대한 Loss 가 어떻게 변하는지 편미분을 통해 Gradient를 구할 수 있다. Loss 값을 줄이는 것이 목표이므로 경사가 완만한 방향으로 이동시켜야한다. 즉, 구한 Gradient의 반대 방향으로 이동시켜야한다.

이를 경사하강법이라고 한다.

Optimizer

경사하강법을 이용해 구한 기울기를 이용해 새로운 가중치를 구할 때 최적화 알고리즘이 사용된다.

이때, Learning Rate 학습률이라는 값이 사용된다. 학습률은 경사하강법을 통한 기울기값을 통해 얼마나 이동할지를 나타낸 값이다.

대표적인 Optimizer

• SGD(Stochastic Gradient Descent)

    optimizer = optim.SGD(model.parameters(), lr=0.01)
  
    optimizer = optim.SGD(model.parameters(), lr=0.01, momentum=0.9)

• Adam(Adaptive Moment Estimation)

    optimizer = optim.Adam(model.parameters(), lr=0.00

SGD는 기울기가 완만한 곳에서는 느리고, 진동하며 하강하는 경향이 있어서 최적점에 도달하기 어렵다. Adam은 방향(Momentum)과 보폭(Scale)를 스스로 조절하며 내려가 학습 초기에 매우 빠르고 안정적이지만 SGD보다 계산량이 많고 세부적인 조절이 필요한 경우에는 SGD 보다 성능이 떨어질 떄가 있다.

Local minimum

손실함수는 단순한 아치 함수형대가 아니라 여러개의 골짜기가 생긴다(미분이 0이 되는 구간, 극소값) 우리는 Loss 값을 작은 값을 만들기 위해 경사가 완만한 쪽으로 가야한다. 하지만 이동한 곳이 가장 완만한 곳이 아니라면 제대로된 경사하강법을 했다고 말할 수 없다. 이러한 문제를 Local Minimum 문제라고 부른다.

• Local Minimum: 부분적으로 최저점인 곳. 여기서 기울기가 완만해져 학습이 멈출 수 있다.
• Global Minimum: 전체 구간에서 진짜 최저점.
• Saddle Point (안장점): 한 방향에서는 극소값이지만 다른 방향에극대값인 지점. 고차원 신경망에서는 Local Minimum보다 이 안장점에 갇히는 경우가 더 많다.

Multi-Layer Percenptron의 약자로 다층 퍼셉트론이라고도 불린다.

지도학습에 사용되는 인공신경망의 한 형태이며, 비선형 은닉계층을 포함하고 있다.

ANN ( 인공 신경망 ) 인간의 뇌에 상호 연결된 뉴런 네트워크 구조와 기능을 모방한 머신러닝 모델이다.

MLP의 특징

• 다층 구조 - 단순한 입출력만 있는 것이 아닌, 하나 이상의 은닉층을 포함하고 있다.
• 완전연결(Fully connected) - 계층의 모든 노드가 연결되어 있는 구조를 가지고 있다.
• 비선형 활성화 함수 - ReLU나 Sigmoid 같은 함수를 사용하여 복잡한 데이터를 분류, 예측할 수 있게 해준다.

MLP의 구성 요소

입력층

초기 입력 데이터를 받는 뉴런으로 구성. 각각의 뉴런은 입력 데이터의 특징이나 차원을 나타낸다. 입력층의 뉴럭 수는 입력 데이터의 차원성에 의해 결정된다.

은닉층

입력층과 출력 층 사이에는 하나이상의 뉴런 층이 존재할 수 있으며, 은닉층의 각 뉴런은 이전 층에서의 뉴런으로 부터 입력을 받고 출력을 생성한다.

출력 계층

최종 출력을 생성하는 뉴런들로 구성된다. 출력 계층의 뉴런 수는 작업의 목적에 따라 달라진다.

가중치 (weight) / 편향 (bias)

• 가중치 (weight) - 노드에 대한 중요도를 표현하는 것. 입력 데이터 별 비중을 크거나 작게 하여 곱해지는 값을 다르게 한다.
• 편향 (bias) - 노드의 민감도를 조정, 활성화 하는 역할을 한다. 가중치 만으로 세밀한 조정이 되지 않는 경우가 잇다.

Activation Function

입력변수에 가중치와 편향을 고려한 모든 값을 더한 선형결합 값을 비선형으로 변환하는 함수.

Acivation Function은 왜 사용할까?

각각의 계층에서의 출력값과 가중치, 편향의 연산을 통한 선형적인 계산은 복잡한 데이터 사이의 관계를 학습하기에 부족하다. 그래서 비선형적인 형태로 변환하고자 한다.

활성화 함수의 종류

• Sigmoid - 출력을 0과 1사이로 제한한다.
• ReLU - 0보다 작으면 0으로, 0보다 큰 값은 그대로 출력한다.
• Softmax - 출력 값들의 합이 1.00이 되도록 만든다.

Dropout

신경망을 훈련시킬 때, 일부 뉴런을 고의적으로 활설화 시키지 않는 방법이다.

위에 그림처럼 Drop-out Rate가 0.5 라면 50%의 뉴런이 활성화 되지 않는다. 4개의 뉴런중 2개의 뉴런이 활성화 되지 않는 모습이다. 이때 활성화 되지않는 뉴런은 랜덤하게 결정된다.

Dropout의 사용목적

결론적으로 Overfitting을 막기 위함이다. 훈련데이터셋에서는 모델의 목적에 맞게 출력값을 제공하지만 훈련데이터셋에만 너무 훈련되어있어 다른 데이터에서는 올바른 출력을 제공하지 못하는 경우이다.

DropOut를 통해 모델의 뉴런이 특정패턴에만 의존하지 못하게 한다.

AI란 Artificial Intelligence의 약자로 인공지능이라고 한다. 학습 능력, 추론 능력, 지각 능력, 자연어 이해 능력 등 지적능력을 컴퓨터 프로그래으로 구현하려는 과학기술 분야. 즉, 인간처럼 생각하고 학습하며 문제를 해결할 수 있는 기계를 만들기 위한 기술

학습(Learning) → 추론(Reasoning) → 개선(self-Improvement)

Machine Learning?

기계학습(Machine Learning)은 기계가 명시적인 프로그래민 없이 데이터를 통해 학습하고 그것을 바탕으로 에측이나 결정을 내릴 수 있도록 하는 알고리즘과 기술을 말한다.

Machine Learning의 종류

기계학습은 말할 때 크게 세가지 종류로 나누어 설명한다.

지도학습(Supervised Learning)

레이블이 있는 데이터를 사용하여 모델을 학습시킨다. 정답이 있는 상태에서의 학습 방법이다.

비지도학습(Unspuervised Learning)

레이블이 없는 데이터를 사용하여 모델이 직접 데이터의 패턴을 발견하도록한다.

강화학습(Reinforcement Learning)

보상과 벌칙과 함께 시행착오를 거쳐 학습하먀, 보상을 최대화하는 방향으로 학습하는 방법이다.

Deep Learning?

Machine Learning의 한 분야로 인공신경망을 기반으로 데이터에서 자동으로 패턴을 학습시키는 기술. 방대한 데이터와 높은 연산 능력을 활용해 인간의 뇌 구조를 모방한 네트워크로 동작한다.

Deep Learning의 구조

딥러닝의 기본적인 구조는 ANN으로 이루어져 있다.

• 입력층 - 데이터를 입력받는 계층
• 은닉층 - 데이터를 처리하고 특징을 찾는 부분 ( 하나 이상의 층을 이루고 있다. )
• 출력층 - 최종 결과를 출력하는 계층

Dataset?

Dataset은 인공지능의 Train, Validation, Test를 하는 데 사용되는 구조화된 데이터의 집합. Dataset은 머신러닝 개발에 핵심요소로 텍스트, 이미지, 음성, 동영상, 3D 등등 다양한 형태로 존재하며, 알고리즘이 패턴을 알아내고 결정을 내리며 예측을 할 수 있도록 도와준다.

Train? Validation? Test?

Train Data?

AI 모델을 훈련하는데 사용되는 데이터이다. 이때 사용되는 데이터들은 라벨링 된 데이터이다. 전체 데이터 셋에 대략 70%를 차지하며 AI 모델이 다양한 패턴과 특징을 학습할 수 있도록 도와주며 보다 정확한 예측을 할 수 있도록 한다.

Validation Data?

모델의 선능을 모니터링하고 파인튜닝 하는데 사용되는 데이터셋이다. 학습과정 중 모델이 과적합되지 않고 최적의 하이퍼파라미터를 찾기 위해 사용된다.

Test Data?

최종 모델의 성능을 평가하는데 사용되는 데이터이다. 이전 학습, 검증 과정에서 사용되지 않는 새로운 데이터로 구성된다.

무한 스크롤은 어떻게 구현하는 걸까? 단순하게 DB에 정보들을 한번에 다 넘기면 되는 걸까…? 결론은 그러면 안된다… 정보의 양이 많다면 생길 수 있는 문제들이… 어후

📁 무한스크롤

무한 스크롤은 페이징 방법과 다르게 사용자가 페이지를 계속 아래로 스크롤할 때마다 자동으로 새로운 콘텐츠를 불러오는 방식!

인스타그램 피드가 하나의 예시!

무한 스크롤을 구현하는 방법은 크게 Offset based Pagination과 Cursor based Pagination 방법이 있다.

이번 포스팅에서는 Cursor based Pagination 방법에 관해서 다루도록 하겠다.

⚙️ Cursor based Pagination

데이터를 페이지 단위로 나눠서 불러올 때, 기준이 되는 고유값(cursor) 을 사용해 다음 페이지 데이터를 가져오는 방식

Cursor 기반은 cursor=123&size=10 처럼 특정 데이터 기준 이후를 불러오는 방식이다.

ex) 요청

GET /posts?cursor=123&size=10

위에 요청은 cursor(특정 데이터 기준이 된다.) 이후 값 10개를 불러온다.

❗️offset의 경우 모든 데이터를 다 불러온 이후에 특정 데이터를 넘겨주지만 cursor는 특정 데이터 이후의 데이터만 불러오기 때문에 대용량의 데이터를 처리할 때 성능이 더욱 좋다!

📁 Cursor based Pagination 구현

⚙️ ScrollPaginationCollection

Cursor based Pagination을 보다 쉽게 사용하기 위한 클래스이다. 해당 클래스는 아래 포스팅에서 가져온 코드임을 밝힌다. 자세한 설명은 아래 포스팅을 참고하길 바란다.

https://velog.io/@orijoon98/Spring-%EB%AC%B4%ED%95%9C%EC%8A%A4%ED%81%AC%EB%A1%A4-%EA%B5%AC%ED%98%84-1-%EC%BB%A4%EC%84%9C-%EA%B8%B0%EB%B0%98-%ED%8E%98%EC%9D%B4%EC%A7%80%EB%84%A4%EC%9D%B4%EC%85%98

@RequiredArgsConstructor(access = AccessLevel.PRIVATE)
public class ScrollPaginationCollection<T> {

    private final List<T> itemsWithNextCursor;
    private final int countPerScroll;

    public static <T> ScrollPaginationCollection<T> of(List<T> itemsWithNextCursor, int size) {
        return new ScrollPaginationCollection<>(itemsWithNextCursor, size);
    }

    public boolean isLastScroll() {
        return this.itemsWithNextCursor.size() <= countPerScroll;
    }

    public List<T> getCurrentScrollItems() {
        if (isLastScroll()) {
            return this.itemsWithNextCursor;
        }
        return this.itemsWithNextCursor.subList(0, countPerScroll);
    }

    public T getNextCursor() {
        if (isLastScroll()) {
            return null; // 더 이상 다음 커서가 없을 경우 null 반환
        }
        return itemsWithNextCursor.get(countPerScroll - 1);
    }
}

⚙️ Service

데이터를 가져오기위한 service 코드이다.

@Override
    public PathHistoryResponse.PathHistoryList getAllPathHistory(int size, Long lastPathId) {
        Authentication authentication = SecurityContextHolder.getContext().getAuthentication();
        String providerId = authentication.getName();
        User user = userRepository.findByProviderId(providerId)
                .orElseThrow(() -> new UserException("해당 id를 가진 사용자를 찾을 수 없습니다. providerId : " + providerId, ErrorCode.USER_NOT_FOUND));
        PageRequest pageRequest = PageRequest.of(0, size + 1);

        List<PathHistory> pathHistories = pathHistoryRepository.findScrollByUserAndCursor(user, lastPathId, pageRequest);
        ScrollPaginationCollection<PathHistory> pathHistoriesCursor = ScrollPaginationCollection.of(pathHistories, size);

        List<PathHistoryResponse.PathHistoryInfoResponse> pathHistoryList = pathHistoriesCursor.getCurrentScrollItems().stream()
                .map(pathHistoryConverter::toResponse)
                .toList();

        PathHistoryResponse.PathHistoryList response = pathHistoryConverter.toResponseList(pathHistoriesCursor,pathHistoryList);

        return response;

    }

PageRequest, Pageable, Page 에 대해서 생소할 수 있다. 아래 글을 참고하길 바란다.

https://velog.io/@rude_ore098/Spring-Pageable-PageRequest-Page-%EA%B0%9C%EB%85%90

❓ 왜 pageRequest을 만들 때 요청된 size 값보다 +1 을 더해서 만들까?

그 이유는 “다음 페이지가 더 있는지 없는지”를 판단하기 위함이다.

예를 들어 10개의 데이터를 요청했다고 생각해보자. 그렇다면 service 코드에서는 10개 보다 한개 많은 11개의 데이터를 가져온다. 이때, 11개의 데이터를 가져왔다면 다음 페이지에도 데이터가 있기 때문에 스크롤이 끝나지 않는 것 이다. ( 클라이언트에 데이터를 줄때에는 요청한 size 값만큼준다. ) 만약 11개보다 적은 데이를 가져왔다면 클라이언트에서 더 이상 요청할 필요 없어요~ 하고 알려주면 된다. 보통 null이나 -1을 반환해 알려준다.**

⚙️ Response dto

    @Getter
    @Setter
    @Builder
    @AllArgsConstructor
    @NoArgsConstructor
    @ToString
    public static class PathHistoryList {
        private List<PathHistoryInfoResponse> pathHistoryInfoList;
        private Long nextCursor; // 다음 커서 값
        boolean isLast;
    }

요청된 데이터, 커서 값 그리고 다음 페이지의 유무를 담는 dto를 만들었다.

💫 TEST

@Test
    @DisplayName("사용자의 PathHistory를 커서 기반으로 페이징 조회한다")
    void getAllPathHistory_cursorPagingTest() {
        // given
        User user = userRepository.save(
                User.builder()
                        .provider(Provider.APPLE)
                        .providerId("testUser_cursor")
                        .role(UserRole.ROLE_USER)
                        .name("테스트 유저")
                        .credit(0L)
                        .build()
        );

        SubwayStation startStation = subwayStationRepository.save(
                SubwayStation.builder()
                        .stationName("출발역")
                        .line(Line.LINE_2)
                        .distance(0)
                        .accumulateDistance(0)
                        .timeMinSec("0:0")
                        .accumulateTime(100)
                        .build()
        );

        SubwayStation endStation = subwayStationRepository.save(
                SubwayStation.builder()
                        .stationName("도착역")
                        .line(Line.LINE_2)
                        .distance(0)
                        .accumulateDistance(0)
                        .timeMinSec("0:0")
                        .accumulateTime(180)
                        .build()
        );

        // 데이터 여러 개 삽입
        for (int i = 0; i < 5; i++) {
            PathHistory pathHistory = PathHistory.builder()
                    .user(user)
                    .startStation(startStation)
                    .endStation(endStation)
                    .build();
            pathHistoryRepository.save(pathHistory);
        }

        TestingAuthenticationToken auth = new TestingAuthenticationToken(user.getProviderId(), null);
        SecurityContextHolder.getContext().setAuthentication(auth);

        // when
        PathHistoryResponse.PathHistoryList response1 = pathHistoryService.getAllPathHistory(3, null);

        // then
        assertThat(response1.getPathHistoryInfoList()).hasSize(3);
//        log.info("PathHistoryInfo {}", response1.getPathHistoryInfoList());
        assertThat(response1.isLast()).isFalse(); // 더 있을 경우
//        log.info("cursorId {}", response1.getNextCursor());
    }

🍀 Spring security 카카오 로그인 구현

📁 소셜 로그인의 원리

카카오 로그인 버튼을 누를 시, 카카오에서 지정한 주소로 요청을 보낸다

주소에는 redirect_uri+ client_id + 등등 여러 정보들이 담겨 있다!

로그인 성공 시 카카오에서 정보를 바로 가지고 오는 것이 아닌, 정보를 가져올 수 있는 코드를 준다. ( 지정한 redirect uri로 코드를 확인할 수 있음)

코드와 함께 다시 요청을 보내야 원하는 정보를 가지고 올 수 있다.

아래는 카카오 로그인 플로우를 나타낸 사진이다

출처 | kakao developers

❗️ 로직 정리 로그인 요청 → 인가 code 발급 → token 요청 ( + code ) → token 발급 → 사용자 정보 요청 ( + token ) → 사용자 정보!

📁 카카오 로그인 적용하기

카카오 디벨롭퍼 | https://developers.kakao.com/

내 애플리케이션 → 애플리케이션 추가하기

이후, 내 애플리케이션 → 제품 설정 → 카카오 로그인 → 동의항목

여기에서 가져오고자 하는 개인정보에 대해서 “동의 항목 설정”을 설정해주면 된다.

본 포스팅에서는 카카오계정(이메일)에 대해서만 설정을 해주었다.

다음으로는 카카오 로그인을 보낼 url과 인가code를 받을 redirect_uri에 대한 등록이 필요하다

플랫폼 url : 내 애플리케이션 → 앱 설정 → 플랫폼

redirect_uri : 내 애플리케이션 → 제품 설정 → 카카오 로그인

로컬에서 테스트를 할 것이 때문에 http://localhost:8080로 지정해 주었다.

배포 시 배포 url를 등록해주어야 배포환경에서 제대로 작동한다.

redirect_uri도 지정해 주었다. 요청 시

http://localhost:8080/login/oauth2/code/kakao?code=v5tRBHV9CLRekMbYBoxOn2eWc0TdrCnRxLwBj3vWSmprnrJF0djCZQAAAAQKPCRZAAABlYRJ4O1APV-WDrAHcw

이런 방식으로 code값이 넘어온다.

kakao Developers 설정은 끝났다. 이제 소셜로그인 코드를 추가해보겠다.

⚙️ Service

code를 통해 accessToken 발급

public String getAccessTokenFromKakao(String code) {

        KakaoTokenResponseDto kakaoTokenResponseDto = WebClient.create(KAUTH_TOKEN_URL_HOST).post()
                .uri(uriBuilder -> uriBuilder
                        .path("/oauth/token")
                        .queryParam("grant_type", "authorization_code")
                        .queryParam("client_id", clientId)
                        .queryParam("code", code)
                        .queryParam("scope", "account_email")
                        .build(true))
                .header(HttpHeaders.CONTENT_TYPE, HttpHeaderValues.APPLICATION_X_WWW_FORM_URLENCODED.toString())
                .retrieve()
                .onStatus(HttpStatusCode::is4xxClientError, clientResponse -> Mono.error(new RuntimeException("Invalid Parameter")))
                .onStatus(HttpStatusCode::is5xxServerError, clientResponse -> Mono.error(new RuntimeException("Internal Server Error")))
                .bodyToMono(KakaoTokenResponseDto.class)
                .block();

        return kakaoTokenResponseDto.getAccessToken();
    }

accessToken을 통해 유저 개인 정보 가져오기

public KakaoUserInfoResponseDto getUserInfo(String accessToken) {

        KakaoUserInfoResponseDto userInfo = WebClient.create(KAUTH_USER_URL_HOST)
                .get()
                .uri(uriBuilder -> uriBuilder
                        .path("/v2/user/me")
                        .build(true))
                .header(HttpHeaders.AUTHORIZATION, "Bearer " + accessToken)
                .header(HttpHeaders.CONTENT_TYPE, HttpHeaderValues.APPLICATION_X_WWW_FORM_URLENCODED.toString())
                .retrieve()
                .onStatus(HttpStatusCode::is4xxClientError, clientResponse -> Mono.error(new RuntimeException("Invalid Parameter")))
                .onStatus(HttpStatusCode::is5xxServerError, clientResponse -> Mono.error(new RuntimeException("Internal Server Error")))
                .bodyToMono(KakaoUserInfoResponseDto.class)
                .block();

        if (userInfo == null || userInfo.getKakaoAccount() == null) {
            throw new RuntimeException("Invalid user info response");

        return userInfo;
    }

참고 블로그 | https://ddonghyeo.tistory.com/16

그렇다면 준비가 끝났다. 카카오에 올바른 요청을 보내면 원하는 정보를 가지고 올 수 있다.

• 요청 URI

https://kauth.kakao.com/oauth/authorize?client_id={REST_API_KEY}&redirect_uri={REDIRECT_URI}r&response_type=code&scope=account_email

REST_API_KEY는 아래에서 확인 할 수 있다.

내 애플리케이션 → 앱 설정 → 앱 키

Copyright 2025. @rude_ore098 All rights reserved.

분기 한정법(Branch and Bound)은 최적화 문제를 해결하기 위한 탐색 알고리즘

• backtrack 과 차이점

  • 최적해를 찾을 가능성이 없으면 분기를 하지 않는다.
  • 또한 Backtracking과 달리 최적화 문제를 푸는데만 사용한다.

• 설계전략

  • 노드에서 숫자(경계)를 계산하여 다음을 결정, 노드가 유망한지 여부
  • Bound는 이후 최적의 값을 예측하는 것.
  • 최적의 값이 best로 기록된 solution보다 안 좋을 시 분기를 하지 않음.

💫 Breadth-First Search - 너비 우선 탐색

지금까지 봤던 알고리즘들과 다르게 같은 수준 (level)에 있는 노드들 먼저 검색한다. 왼쪽 → 오른쪽 순서로 검색한다.

📢 알고리즘은 Queue를 사용해서 구현한다.

void breadth_first_search(tree T) {
    queue_of_node Q;
    node u, v;
    initialize(Q);       // Initialize Q to be empty
    v = root of T;
    visit v;
    enqueue(Q,v);
    while(!empty(Q)) {
       dequeue(Q,v);
       for(each child u of v) {
          visit u;
          enqueue(Q,u);
       }
    } 
}

📁 0-1 Knapsack Problem - 분기 한정법

Queue 사용방법

void knapsack2(int n, const int p[], const int w[], int W, int &maxprofit) {
    queue_of_node Q;   // 노드를 저장할 큐
    node u, v;         // 현재 노드(v)와 확장 노드(u)
    initialize(Q);     // 큐 초기화
    v.level = 0;       // 초기 노드 설정 (루트 노드)
    v.profit = 0;      // 초기 이익 0
    v.weight = 0;      // 초기 무게 0
    maxprofit = 0;     // 초기 최대 이익 0
    enqueue(Q, v);     // 초기 노드를 큐에 삽입

    // 큐가 비어 있지 않은 동안 탐색 반복
    while (!empty(Q)) {
        dequeue(Q, v); // 큐에서 노드 v를 꺼냄
        u.level = v.level + 1; // u는 v의 다음 레벨(다음 아이템을 고려)

        // u 노드가 아이템을 포함한 경우
        u.profit = v.profit + p[u.level];  // u의 이익 = v의 이익 + 현재 아이템의 이익
        u.weight = v.weight + w[u.level]; // u의 무게 = v의 무게 + 현재 아이템의 무게
        if ((u.weight <= W) && (u.profit > maxprofit)) // u가 배낭 용량을 초과하지 않고, 최대 이익을 갱신할 수 있다면
            maxprofit = u.profit; // 최대 이익 갱신
        if (bound(u) > maxprofit) // u 노드의 bound가 현재 최대 이익보다 크면 탐색할 가치가 있음
            enqueue(Q, u);        // u를 큐에 삽입

        // u 노드가 아이템을 포함하지 않는 경우
        u.weight = v.weight;     // u의 무게는 v의 무게와 동일
        u.profit = v.profit;     // u의 이익은 v의 이익과 동일
        if (bound(u) > maxprofit) // u 노드의 bound가 현재 최대 이익보다 크면 탐색할 가치가 있음
            enqueue(Q, u);        // u를 큐에 삽입
    }
}

float bound(node u) {
    index j, k;       // j: 다음 아이템 인덱스, k: 부분적으로 넣을 아이템의 인덱스
    int totweight;    // 현재까지 배낭에 넣은 총 무게
    float result;     // bound 값을 저장할 변수

    // 현재 노드의 무게가 배낭 용량을 초과하면 유망하지 않음
    if (u.weight >= W)
        return 0;

    else {
        result = u.profit; // 현재 노드까지의 이익을 result에 저장
        j = u.level + 1;   // 다음 아이템의 레벨로 초기화
        totweight = u.weight; // 현재까지 배낭에 넣은 무게를 totweight에 저장

        // 배낭 용량을 초과하지 않는 범위에서 가능한 모든 아이템을 완전히 넣음
        while ((j <= n) && (totweight + w[j] <= W)) {
            totweight = totweight + w[j];   // 무게를 누적
            result = result + p[j];         // 이익을 누적
            j++;                            // 다음 아이템으로 이동
        }

        k = j; // 부분적으로 넣을 수 있는 첫 번째 아이템의 인덱스

        // 부분적으로 넣을 수 있는 아이템이 남아 있으면 계산
        if (k <= n) 
            result = result + (W - totweight) * p[k] / w[k];

        return result; // 계산된 bound 반환
    }
}

분기한정 가지치기로 BFS를 하여 상태공간트리를 그려보면, 검색하는 노드의 개수는 17이다. 즉, backtrac보다 좋지 않다. 이것을 해결할 방법에 대해 알아보자!

📁 0-1 Knapsack Problem - 분기 한정법

바로 우선순위 큐를 사용하는 방법이다.

void knapsack3(int n, const int p[], const int w[], int W, int &maxprofit) {
    queue_of_node PQ;  // 우선순위 큐(Priority Queue)
    node u, v;         // 현재 노드(v)와 확장된 자식 노드(u)
    initialize(PQ);    // 우선순위 큐 초기화

    v.level = 0;       // 초기 노드의 레벨 (루트 노드)
    v.profit = 0;      // 초기 노드의 이익
    v.weight = 0;      // 초기 노드의 무게
    v.bound = bound(v); // 초기 노드의 bound 값 계산
    maxprofit = 0;     // 최대 이익 초기화
    insert(PQ, v);     // 초기 노드를 우선순위 큐에 삽입

    // 우선순위 큐가 비어 있지 않은 동안 탐색 반복
    while (!empty(PQ)) {
        remove(PQ, v);  // bound 값이 가장 큰 노드를 큐에서 꺼냄 (최적 후보 노드)

        // 현재 노드가 여전히 유망한 경우 탐색 진행
        if (v.bound > maxprofit) {
            // u 노드를 v 노드의 첫 번째 자식으로 설정 (아이템 포함)
            u.level = v.level + 1;             // 다음 레벨로 이동
            u.profit = v.profit + p[u.level];  // 현재 아이템의 이익 추가
            u.weight = v.weight + w[u.level]; // 현재 아이템의 무게 추가

            // u 노드의 무게가 배낭 용량을 초과하지 않고, 더 큰 이익을 제공할 경우 갱신
            if ((u.weight <= W) && (u.profit > maxprofit))
                maxprofit = u.profit;          // 최대 이익 갱신

            // u 노드의 bound 계산
            u.bound = bound(u);
            if (u.bound > maxprofit)           // u 노드가 유망한 경우 큐에 삽입
                insert(PQ, u);

            // u 노드를 v 노드의 두 번째 자식으로 설정 (아이템 미포함)
            u.weight = v.weight;              // 현재 아이템의 무게는 그대로 유지
            u.profit = v.profit;              // 현재 아이템의 이익은 그대로 유지
            u.bound = bound(u);               // bound 값 재계산
            if (u.bound > maxprofit)          // u 노드가 유망한 경우 큐에 삽입
                insert(PQ, u);
        }
    }
}

💫 The Traveling Salesperson Problem

집이 위치하고 있는 도시에서 출발하여 다른 도시들을 각각 한번씩만 방문하고, 다시 집으로 돌아오는 문제 → 가장 짧은 일주여행경로를 결정하는 문제

• 이 문제는 음이 아닌 가중치가 있는, 방향성 그래프로 나타낼 수 있다.
• 그래프 상에서 한 정점을 출발하여 다른 모든 정점을 한번씩만 거쳐서 다시 그 정점으로 돌아오는 경로
• 여러 경로 중 최소가 길이가 최소가 되는 경로

📁 동적계획법을 이용한 접근 방법 - 외판원문제

• V 는 모든 정점의 집합, A는 V의 부분 집합

$$ D[v_1][V - {v_1}] = \min_{2 \leq j \leq n} \left( W[1][j] + D[v_j][V - {v_1, v_j}] \right) $$

$$ D[v_i][A] = \min_{v_j \in A} \left( W[i][j] + D[v_j][A - {v_j}] \right) \quad \text{if } A \neq 0 $$

$$ D[v_i][0] = W[i][1] $$

📁 분기한정법 - 외판원문제

노드가 5개이기 때문에 4개의 마디까지만 그리면 된다.

📁 lower bounds

외판원문제에서 bound를 설정하는 것이다. 이때는 하한이다.

설명을 위해 예시의 값을 계산하면서 진행하도록 하겠다.

첫 번째로 초기 bound를 정할 때, 노드들의 합을 구한다.

v1 min(14, 4, 10, 20) = 4 v2 min(14, 7, 8, 7) = 7 v3 min(4, 5, 7, 16) = 4 v4 min(11, 7, 9, 2) = 2 v5 min(18, 7, 17, 4) = 4

4 + 7 + 4 + 2 + 4 = 21

1번 노드를 시작한다.

다음 으로 [1,2], [1,3], [1,4], [1,5] 노드들을 큐에 넣는다.

[1,3]에 대한 bound 계산

v2 min(14, 8, 7) = 7 v3 min(5, 7, 16) = 5 << - 1번에서 3번 노드로 이동하였기 때문에 1번노드로 이동하는 edge를 제거한다. v4 min(11, 7, 2) = 2 v5 min(18, 7, 4) = 4

(현재 이동한 간선) + (나머지 간선들의 최소 값) = 4 + 7 + 5 + 2 + 4 = 22

…..

(생략)

계산 요약

• 이미 방문 한 노드의 간선의 가중치는 제외한다.
• 방문한 노드에서 방문하는 경우 출발지 ( 예시에서는 v1 )의 의 가중치도 빼야한다.

void travel2(int n, const number W[][], ordered_set &opttour, number &minlength) {
    priority_queue_of_node PQ;  // 탐색할 노드를 저장하는 우선순위 큐
    node u, v;                 // 현재 노드(v)와 확장할 자식 노드(u)

    initialize(PQ);            // 우선순위 큐 초기화
    v.level = 0;               // 초기 노드는 레벨 0
    v.path = [1];              // 시작 정점(1)에서 출발
    v.bound = bound(v);        // 현재 노드의 bound 계산
    minlength = INFINITE;      // 최소 경로 길이를 무한대로 초기화
    insert(PQ, v);             // 초기 노드를 우선순위 큐에 삽입

    // 우선순위 큐가 비어 있지 않은 동안 탐색 반복
    while (!empty(PQ)) {
        remove(PQ, v);          // 큐에서 bound가 가장 작은 노드를 꺼냄
        if (v.bound < minlength) { // 현재 노드의 bound가 최소 길이보다 작을 때만 탐색
            u.level = v.level + 1; // u는 v의 다음 레벨 노드

            // 현재 경로(v.path)에 포함되지 않은 정점 i를 탐색
            for ((all i such that 2 < i < n) && (i is not in v.path)) {
                u.path = v.path;       // u의 경로를 v의 경로로 초기화
                put i at the end of u.path; // 경로 끝에 정점 i를 추가

                // 모든 정점을 방문한 경우 (u.level == n-2)
                if (u.level == n-2) {
                    put index of only vertex
                    not in u.path at the end of u.path; // 마지막 남은 정점을 추가
                    put 1 at the end of u.path; // 출발점(1)으로 돌아오는 경로 추가

                    // u의 경로 길이가 현재 최소 길이보다 작으면 갱신
                    if (length(u) < minlength) {
                        minlength = length(u); // 최소 경로 길이 갱신
                        opttour = u.path;      // 최적 경로 갱신
                    }
                }
                else {
                    u.bound = bound(u);      // u의 bound 계산
                    if (u.bound < minlength) // bound가 최소 경로 길이보다 작을 경우만 탐색
                        insert(PQ, u);       // u를 우선순위 큐에 삽입
                }
            } // for 문 종료
        } // if 문 종료
    } // while 문 종료
}

배낭 문제를 상태공간트리에 적용하여 문제를 해결한다. 뿌리마디에서 왼쪽으로 가면 첫번째 아이템을 배낭에 넣는 경우이고,오른쪽으로 가면 첫번째 아이템을 배낭에 넣지 않는 경우이다.

상태공간트리를 구출하여 되추적 기법으로 문제를 해결한다.

최적의 해를 찾는 문제이므로 검색이 완전히 끝나기 전에는 해답을 알 수 없다.

→ 검색하는 과정 동안 항상 이전까지 찾은 최적의 해를 기억해 두어야 한다.

📁 주요개념

알고리즘은 $w_i$ 와 $p_i$를 각각 i 번째 아이템의 무게와 값어치라고 하면, $p_i$/$w_i$ 의 값이 큰 것 부터 내림차순한다.

• profit : 그 노드에 오기까지 넣었던 아이템 값어치의 합
• weight : 그노드에 오기까지 넣었더 아이템 무게의 합
• bound : 노드가 수준 i에 있다고 하면, 수준 k에 있는 노드에서 총 무게가 W를 넘는다고 하자. 그리면 아래와 같이 bound응 구할 수 있다.

$$ \text{bound} = \text{profit} + \sum_{j=i+1}^{k-1} p_j + (W - \text{totweight})\cdot\frac{p_k}{w_k} $$

$$ \text{totweight} = \text{weight} + \sum_{j=i+1}^{k-1} w_j $$

(weight< W ) and (bound> maxprofit )이면, 검색을 계속한다 → 무게가 초과하지 않았고, 향후 가치가 최대 가치보다 클 수 있다면

이때, 계산을 하다보면 남은 아이템을 모두 넣어도 W를 넘지 않을 때에는 남은 아이템의 값어치를 bound에 다 더해주면 된다.

📁   The 0-1 Knapsack Problem

void knapsack (index i, int profit, int weight) {
    // 현재 무게(weight)가 배낭 용량(W)을 초과하지 않고,
    // 현재 이익(profit)이 최대 이익(maxprofit)보다 클 경우 최대 이익 갱신
    if (weight <= W && profit > maxprofit) { 
        maxprofit = profit; // 최대 이익 갱신
        numbest = i;        // 현재까지 가장 좋은 해에서 포함된 아이템의 인덱스 저장
        bestset = include;  // 현재 아이템 선택 상태를 최적 해(bestset)로 저장
    }

    // 현재 노드가 유망(promising)한 경우 탐색 진행
    if (promising(i)) {
        include[i+1] = "YES";  // 현재 아이템 w[i+1]을 포함시키는 경우
        knapsack(i+1, profit + p[i+1], weight + w[i+1]); // 다음 아이템 탐색 (포함)

        include[i+1] = "NO";   // 현재 아이템 w[i+1]을 포함하지 않는 경우
        knapsack(i+1, profit, weight); // 다음 아이템 탐색 (미포함)
    } 
}

bool promising(index i) {
    index j, k;
    int totweight;
    float bound;

    // 현재 무게(weight)가 배낭 용량(W)을 초과하면 유망하지 않음
    if (weight >= W)  
        return FALSE;

    else {
        j = i + 1;              // 다음 아이템 인덱스
        bound = profit;         // 현재까지의 이익으로 초기화
        totweight = weight;     // 현재까지의 무게로 초기화

        // 남은 배낭 용량으로 완전히 넣을 수 있는 아이템들을 추가
        while ((j <= n) && (totweight + w[j] <= W)) {
            totweight = totweight + w[j]; // 무게 누적
            bound = bound + p[j];         // 이익 누적
            j++;                          // 다음 아이템으로 이동
        }

        k = j; // 부분적으로 넣을 수 있는 첫 번째 아이템의 인덱스

        // 아직 고려하지 않은 아이템이 남아 있다면, 부분적으로 추가
        if (k <= n)
            bound = bound + (W - totweight) * p[k] / w[k];

        // 계산된 bound가 현재 최대 이익(maxprofit)보다 크면 유망
        return bound > maxprofit;
    }
}

• 알고리즘 적용

📁 시간 복잡도

시간복잡도 : $2^n$

주어진 그래프에서 모든 정점을 정확히 한 번씩 방문하고 출발점으로 돌아오는 경로(순환), 즉 해밀턴 순환(Hamiltonian Circuit)이 존재하는가?

📁 유망한 노드인지 판단여부

• 상태 이상 트리에서 기준이 되는 노드의 부모노드, 자식노드가 기준이 되는 노드와 같은지 판단한다.
  • 부모 노드, 자식 노드와 색이 같다 ⇒ 유망하지 않다.
  • 노드, 자식 노드와 색이 색이 같지 않다. ⇒ 유망하다.

📁  *Graph Coloring *

bool promising(index i) {
    int j;
    bool switch;

    // 현재 정점이 마지막 정점(n-1)일 경우, 시작 정점(0)으로 돌아갈 간선이 없는지 확인
    if (i == n - 1 && !W[vindex[n - 1]][vindex[0]])
        switch = FALSE;

    // 현재 정점이 1 이상일 때, 이전 정점(i-1)에서 현재 정점(i)으로의 간선이 없는지 확인
    else if (i > 0 && !W[vindex[i - 1]][vindex[i]])
        switch = FALSE;

    else {
        switch = TRUE; // 기본적으로 유망하다고 가정
        j = 1;

        // 현재 정점까지의 경로에서 중복된 정점이 있는지 검사
        while (j < i && switch) {
            if (vindex[i] == vindex[j]) // 동일한 정점이 경로에 다시 등장하면 유망하지 않음
                switch = FALSE;
            j++;
        }
    }

    return switch; // 유망 여부를 반환
}

• 알고리즘 적용

📁 시간 복잡도

$$ 1 + m + m^2 + \cdots + m^n = \frac{m^{n+1} - 1}{m - 1} $$

시간복잡도 : $2^n$

지도에 m가지 색을 가지고 색칠하는 문제. m개의 색을 가지고 인접한 지역이 같은 색이 되지 않도록 지도에 색칠해야 한다.

📁 유망한 노드인지 판단여부

• 상태 이상 트리에서 기준이 되는 노드의 부모노드, 자식노드가 기준이 되는 노드와 같은지 판단한다.
  • 인접한 노드들과 색이 같다 ⇒ 유망하지 않다.
  • 인접한 노드들과 색이 같지 않다. ⇒ 유망하다.

📁 Graph Coloring ****

void m_coloring (index i) {
    int color;
    // 현재 노드 i에서 유망한지 확인
    if (promising(i)) {
        // 만약 i가 마지막 정점이라면 (모든 정점이 색칠 완료된 상태)
        if (i == n) 
            // vcolor 배열에 저장된 각 정점의 색상을 출력
            cout << vcolor[1] through vcolor[n];
        else
            // 각 색상 (1부터 m까지)을 정점 i+1에 시도
            for (color = 1; color <= m; color++) {
                vcolor[i+1] = color; // 정점 i+1에 현재 색상 할당
                m_coloring(i+1); // 다음 정점으로 재귀 호출
            }
    }
}

bool promising(index i) {
    int j;
    bool switch;
    switch = TRUE; // 초기 상태에서 유망하다고 가정
    j = 1;

    // 현재 노드와 이전 노드 간 색상 충돌 여부를 확인
    while (j < i && switch) {
        // 두 정점이 연결되어 있고, 색상이 같다면 유망하지 않음
        if (W[i][j] && vcolor[i] == vcolor[j]) 
            switch = FALSE;
        j++;
    }

    // 유망 여부 반환 (TRUE: 유망, FALSE: 유망하지 않음)
    return switch;
}

• 알고리즘 적용

📁 시간 복잡도

$$ 1 + m + m^2 + \cdots + m^n = \frac{m^{n+1} - 1}{m - 1} $$

시간복잡도 : $2^n$

주어진 정수 집합과 목표 합계를 기반으로, 집합의 부분 집합 중에서 원소들의 합이 주어진 목표 값과 일치하는 경우를 찾는 문제

📁 유망한 노드인지 판단여부

조건 - 가중치를 오름차순으로 정렬한 경우, 노드가 유망하지 않음을 판단

1. 현재까지 선택한 가중치의 합 (weight)

   weight : 현재 노드의 레벨 까지 포함된 가중치의 합.

   상황 :   $weight + w_{i+1} > W$ 

   → 현재까지의 가중치 합 에 다음 가중치 를 추가했을 때, 목표값 를 초과하면 유망하지 않은 노드로 간주

2. 남은 모든 가중치의 총합 (total)

   $total$ : 아직 선택되지 않은 남은 가중치들의 합.

   상황 :   $weight + total < W$ 

   → 현재까지의 가중치 합 와 남은 모든 가중치의 합 을 더해도 목표값 에 도달할 수 없다면, 유망하지 않은 노드로 간주

📁  Sum-of-subsets Problem

void sum_of_subsets (index i, int weight, int total) {
   if (promising(i)) {
      if (weight ==W)
          cout << include[1] through include[i];
      else {
          include[i+1] = “yes”;
          sum_of_subsets(i+1, weight+w[i+1], total-w[i+1]);
          include[i+1] = “no”;
          sum_of_subsets(i+1, weight, total-w[i+1]);
   } 
}

bool promising (index i) {
   return (weight+total >= W)
           && (weight == W || weight+w[i+1] <= W);
}

• Example

• 알고리즘 적용

📁 시간 복잡도

$$ 1 + 2 + 2^2 + \cdots + 2^n = 2^{n+1} - 1. $$

시간복잡도 : $2^n$

모든 경우의 수를 전부 고려하는 알고리즘. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다.

어떤 노드에서 유망성을 점검한 후, 유망하지 않다고 판정되면 그 노드의 부모노드로 돌아가서(”backtrack”) 다음 후손노드에 대한 검색을 계속 진행하는 과정이다.

Promising : 해답이 나올 가능성이 있다. → 유망하다.

non - Promising : 해답이 나올 가능성이 없다.→ 유망하지 않다.

📁 backtrack

일반적인 되추적 알고리즘

void checknode (node v) {
      node u;
   if (promising(v))
      if (there is a solution at v)
         write the solution;
      else
          for (each child u of v)
                   checknode(u);
}

개선된 되추적 알고리즘

void expand (node v) {
        node u;
        for (each child u of v)
                if (promising(u))
                if (there is a solution at u)
                        write the solution;
                else
                        expand(u);
}

💫 Depth - First Search ( 깊이우선검색 )

뿌리 노드 ( root )가 되는 노드( node )를 먼저 방문한 뒤, 그 노드의 모든 후손노드들을 차례로 방문 / 왼 → 오

💫 4-Queen Problem

4개의(n개도 가능) Queen을 서로 상대방을 위협하지 않도록 상대방의 Queen을 위협하지 않기 위해 같은 행이나, 같은 열, 대각선 상에 위치하지 않아야한다. ( 엥 근데 체스는 1:1 게임인데… ?)

문제를 어떻게 접근할까..?

❗️ 무작정 알고리즘 각 Queen을 각각 다른 행에 할당한 후에, 어떤 열에 위치하면 해답은 얻을 수 있는지를 차례대로 점검해 보면 된다. 이때, 각 Queen은 4개의 열 중에서 한 열에 위치할 수 있기 때문에, 해답을 얻기 위해서 점검해 보아야 하는 모든 경우의 수는 4 x 4 x 4 x 4 = 256가지가 된다.

📁 4-Queens 문제의 상태공간 트리

❓ 상태공간 트리

뿌리 노드에서 잎노드 까지의 경로가 해답 후보가 되는 것. → 깊이우선검색을 하여 그 해답후보 중에서 해답을 찾을 수 있다.

상태공간트리에서 깊이우선검색을 하면 해답을 찾을 수 있지만 모든 후손노드들을 방문애햐 하므로 굉장히 비효율적이다.

📁 의사 코드

행렬을 체스판이라고 생각!

void queens (index i) {
 index j;
        if (promising (i))
           if (i == n)  cout << col[1] through col[n];
     else
           for (j=1; j<=n; j++) {
              col[i+1] = j;
              queens(i+1);
          }
}

 bool promising (index i) {
   index k;
   bool switch;

   k = 1;
   switch = TRUE;
   while (k<i && switch) {
      if (col[i]==col[k] || abs(col[i]–col[k])==abs(i-k))
         switch = FALSE;
      k++ 
   }
   return switch;
}

N-Queens에서 코드 분석

• 같은 열인 경우 non promising
  • If (col(i) == col(k)) nonpromising;
• 대각선인 경우 non promising
  • If (abs(col(i) - col(k)) == abs(i - k)) nonpromising;

📁 n - Queens Problem 분석 - 1

상태공간트리 전체에 있는 노드의 수를 구함으로서, 가지 친 상태공간의 노드의 개수의 상한을 구한다.

깊이가 i인 노드의 개수는 $n^i$개 이고, 이 트리의 깊이는 n이므로, 노드의 총 개수의 상한은 아래 식과 같다.

$$ 1 + n + n^2 + n^3 + \cdots + n^n = \frac{n^{n+1} - 1}{n - 1} $$

열심히 적었지만…. 이 분석은 별 가지가 없다. ㅠ

왜냐, 되추적함으로서 점검하는 노드 수를 얼마나 줄였는지 상한값을 구해서는 전혀 알 수 없기 때문이다.

📁 n - Queens Problem 분석 - 2

유망한 노드만 카운트해 상한을 구한다.

→ 어떤 두 개의 Queen이 같은 열에 위치할 수 없다는 사실을 이용하면 된다.

$$ 1 + n + n(n-1) + n(n-1)(n-2) + \cdots + n! $$

하지만… 2번 또한 그렇게 가치있는 분석은 아니다.

위 2가지 분석은 알고리즘의 복잡도를 정확히 얘기해주지 못하고 있다.

• 대각선을 점검하는 경우를 고려하지 않음

  → 실제 유망한 노드의 수는 훨씬 더 작을 수 있다.

• 유망하지 않은 노드의 일부만 포함하고 있다.

  → 유망하지 않은 노드는 훨씬 더 많을 수 있다.

💫 Monte Carlo Algorithm

어떤 입력이 주어졌을 때 점검하게 되는 상태공간 트리의 “전형적인” 경로를 무작위로 생성하여 그 경로 상에 있는 노드의 수를 센다. → 과정을 반복하여 나오는 결과의 평균치를 추정치로 한다.

이 기법을 적용하기 위한 필수 조건

• 상태공간트리에서 같은 level에 있는 모든 노드에서는 같은 유망함수를 사용해야함
• 상태 공간트리에서 같른 수준에 있는 모든 노드들은 같은 수의 자식노드들을 가지고 있어야 한다.

📁 백트랙킹 알고리즘 수행시간 추정 방법

1. 뿌리노드의 유망한 자식노드의 개수를 $m_0$이라고 한다.
2. 상태공간트리의 수준 1에서 유망한 노드 하나를 무작위로 정하고, 그 노드의 유망한 자식노드의 개수를 $m_1$이라고 한다.
3. 위에서 정한 노드의 유망한 노드 하나를 다시 무작위로 정하고, 그 노드의 유망한 자식노드의 개수를 $m_2$라고 한다.
4. 더 이상 유망한 자식노드가 없을 때까지 이 과정을 반복한다.

$$ 1 + t_0 + m_0 t_1 + m_0 m_1 t_2 + \cdots + m_0 m_1 \cdots m_{i-1} t_i + \cdots $$

• $m_i$는 수준 i에 있는 노드의 유망한 지식노드의 개수이 평균 추정치
• $t_i$는 수준 i에 있는 한 노드의 자식노드의 총 개수
• 식의 처음 1은 root

가중치가 있는 방향성 그래프에서 한 특정 정점에서 다른 모든 정점으로 가는 최단경로 구하는 문제

📁 수도 코드

F := 0;
Y := {v1};
While (the instance is not solved)
        select a vertex v from V- Y, that has a shortest path // selection procedure
        from v1, using only vertices in Y as intermediate; // and feasibility check

        add the new vertex v to Y;
        add the edge (on the shortest) that touches v to F;
        if (Y == V) // solution check
                the instance is solved;

📁 Dijkstra’s Algorithm

void dijkstra (int n, const number W[][], set_of_edges& F) {
    index i, vnear; 
    edge e;
    index touch[2..n]; // v1부터 i까지의 현재 최단 경로에서 i 이전의 정점을 저장
    number length[2..n]; // v1에서 i까지의 최단 경로의 길이를 저장
    F = 공집합; // 최단 경로 트리의 간선 집합 초기화

    // 모든 정점에 대해 v1을 경로의 마지막 정점으로 초기화하고,
    // v1에서 i까지의 경로 길이를 초기화 (v1에서 i로 가는 간선의 가중치로 초기화)
    for(i = 2; i <= n; i++) { 
        touch[i] = 1; // 초기에는 모든 정점의 이전 정점을 v1로 설정
        length[i] = W[1][i]; // 초기에는 v1에서 정점 i로 가는 경로의 길이를 W[1][i]로 설정
    }                          

    // 모든 n-1개의 정점을 최단 경로 집합 Y에 추가
    repeat(n-1 times) { 
        min = "infinite"; // 현재 최단 경로의 최소 거리를 무한대로 초기화

        // 모든 정점을 검사하여 최단 경로를 가지는 정점을 선택
        for(i = 2; i <= n; i++) 
            if (0 <= length[i] && length[i] <= min) { 
                min = length[i]; // 최단 경로의 최소 값을 갱신
                vnear = i; // 최단 경로를 가지는 정점 vnear을 기록
            }

        // touch[vnear]에서 vnear로 가는 간선을 e로 추가
        e = edge from vertex indexed by touch[vnear] to vertex indexed by vnear; 
        add e to F; // e를 최단 경로 트리에 추가

        // vnear을 통해 연결된 정점들의 경로를 업데이트
        for(i = 2; i <= n; i++) 
            if (length[vnear] + W[vnear][i] < length[i]) { 
                length[i] = length[vnear] + W[vnear][i]; // vnear을 통해 i로 가는 더 짧은 경로가 발견되면 업데이트
                touch[i] = vnear; // 경로에서 i의 이전 정점을 vnear로 업데이트
            } 

        length[vnear] = -1; // vnear를 Y 집합에 추가 (처리 완료)하고 더 이상 선택되지 않도록 함
    } 
}

tounch[i] = 현재까지의 최단 경로에서, v1에서 vi로 가는 경로의 마지막에 위치한 Y에 속한 정점의 인덱스

length[i] = v1에서 vi로 가는 현재 최단 경로의 길이 Y에 속한 정점들만을 경유할 수 있음

(Y는 현재 최단 경로 집합을 의미)

• 알고리즘 적용

📁 시간 복잡도

$T(n) = 2(n-1)^2$ 시간 복잡도 : $n^2$

용어 정리

• 비방향성 그래프 ( undirected graph )G = (V,E)

  → V 는 Set of Vertex

  → E 는 Set of Edge

• 경로 path

• 연결된 그래프 ( connected graph ) - 어떤 두 정점 사이에도 경로가 존재

• 부분 그래프 ( sub graph )

• 가중치 포함 그래프 ( weight graph )

• 순환경로 ( cycle )

• 순환적 그래프 (cyclic graph ), 비순환적 그래프 ( acyclic graph )

• 트리 tree - 비순환적이며, 연결된, 비방향성 그래프

• 뿌리 있는 트리 ( rooted tree ) - 한 정점이 뿌리로 지정된 트리

💫 Spanning Tree ( 신장 트리 )

연결된 비방향성 그래프 G에서 순환 경로를 제거하면서 연결된 부분 그래프가 되도록 이음선 제거 즉, 트리는 G안에 있는 모든 정점을 다 포함하면서 트리가 되는 “연결된 그래프 “

Spanning tree의 예시.

그래프를 보면 모든 정점들이 연결되어 있고 순환된 경로가 제거되어 있는 모습이다.

💫 Minimum Spanning Tree ( 최소비용 신장트리 )

A spanning tree with minimum weight

연결된, 비방향성 그래프 G에서 순환경로를 제거하면서 연결된 부분그래프가 되도록 이음선 제거

최소의 가중치를 가진 부분그래프는 반드시 트리가 되어야한다!

왤까..? 만약 트리가 아니라면 분명하게 순환경로(cycle)가 있을 것이다. 그렇게 되면 순환경로 상의 한 이음선을 제거하면 더 작은 비용의 신장트리가 되기 때문이다.

💫 Prim’s Algorithm

📁 수도 코드

F := 공집합; //  간선 집합 F를 빈 집합으로 초기화
Y := {v1}; // 정점 집합 Y에 첫 번째 정점 v1을 추가 <- v1 부터 시작
                        // contain only the first one
While (the instance is not solved) {
select a vertex in V-Y that is nearest to Y; // 인스턴스가 해결되지 않았을 때(즉, 모든 정점이 MST에 추가되지 않았을 때) 반복합니다.
                                                                                    // feasibility check
add the vertex to Y;
add the edge to F;

if (Y == V) // solution check
the instance is solved;
}

📁 Prims Algorithm

void prim(int n, const number W[][], set_of_edges& F) {
     index i, vnear; number min; edge e;
    index nearest[2..n]; number distance[2..n];
    F = 공집합;
    for(i=2; i <= n; i++) {  // 초기화
        nearest[i] = 1;        // vi에서 가장 가까운 정점을 v1으로 초기화
        distance[i] = W[1][i];    // vi과 v1을 잇는 이음선의 가중치로 초기화
    }

    repeat(n-1 times) {  // n-1개의 정점을 Y에 추가한다{
    min = “infinite”;
     for(i=2; i <= n; i++) // 각 정점에 대해서
         if (0 <= distance[i] <= min) { // distance[i]를 검사하여
             min = distance[i]; // 가장 가까이 있는 vnear을
             vnear = i; // 찾는다.
        }
      e = edge connecting vertices indexed by vnear and nearest[vnear]; 
      add e to F;
      distance[vnear] = -1;   // 찾은 노드를 Y에 추가한다.
      for(i=2; i <= n; i++)
      if (W[i][vnear] < distance[i]) {   // Y에 없는 각 노드에 대해서 
          distance[i] = W[i][vnear];    // distance[i]를 갱신한다.
          nearest[i] = vnear;
      }
    } 
}

nearest[i] = Y가 속한 정점 중에서 $v_i$중에서 가장 가까운 정점의 인덱스 → distance 값이 작은지도 검사한다.

distance[i] = $v_i$와 nearest[i]를 잇는 이음선의 가중치

• 그래프의 표현

• 알고리즘 적용

📁 시간 복잡도

• 단위 연산 : repeat-루프 안에 있는 두 개의 for-루프 내부에 있는 명령문
• 입력 크기 : 마디의 개수, n
• 분석 : repeat - 루프가 n-1 반복

$T(n) = 2(n-1)(n-1)$

시간복잡도 : $n^2$

💫 Kruskal’s Algorithm

📁 수도 코드

F := 공집합; // initialize set of edges
                // to empty
create disjoint subsets of V, one for each
vertex and containing only that vertex;

sort the edges in E in nondecreasing order;

While (the instance is not solved) {
        select next edge; // selection procedure
        if (the edge connects 2 vertices
                in disjoint subsets) { // feasibility check
                    merge the subsets;
                    add the edge to F;
    }
    if (all the subsets are merged) // solution check
            the instance is solved;

}

📁 Kruskal’s Algorithm

void kruskal(int n, int m, set_of_edges E, set_of_edges& F) { 
     index i, j;
    set_pointer p, q;
    edge e;
    Sort the m edges in E by weight in nondecreasing order; 
    F = 공집합;
    initial(n);
    while (number of edges in F is less than n-1) {
        e = edges with least weight not yet considered;         
        i, j = indices of vertices connected by e;
        p = find(i);
        q = find(j);
        if (!equal(p,q)) {
            merge(p,q);
            add e to F; 
        }
    } 
}

Sort the m edges in E by weight in nondecreasing order; 크루스칼 알고리즘의 종료 조건은 MST에 포함된 간선의 수가 n-1이 될 때

코드를 보면 find(i) / find(j)를 볼 수 있다 이것이 뭘까..? 서로 집합 데이터를 이용해 검사를 한다.

코드를 보면 최소 가중치를 가지는 순서대로 간선들을 정렬하고 순서대로 추가하며 MS를 찾는다. 이때, cycle이 생길 수 있다. 그래서 집합안에 추가하고자 하는 vertax가 있는지 검사를 해야한다.

그래서 Disjoint Set Data Structur 를 사용한다.

📁 Disjoint Set Data Structure

Disjoint Set Data Structure 1

const int n = the number of elements in the universe;

typedef int index;
typedef index set_pointer; 
typedef index universe[1..n]; 

universe U;

// 원소 i에 대해 i 자신의 집합을 생성
void makeset (index i) { 
    U[i] = i; 
}

// 원소 i가 속한 집합의 대표 원소(루트)를 반환
set_pointer find (index i) { 
    index j; 
    j = i;
    while (U[j] != j) 
        j = U[j]; 
    return j; 
}

// p와 q가 속한 두 집합을 하나의 집합으로 합침
void merge (set_pointer p, set_pointer q) { 
    if (p < q) 
        U[q] = p; 
    else 
        U[p] = q; 
}

// p와 q가 같은 집합에 속하는지 확인
bool equal(set_pointer p, set_pointer q) { 
    if (p == q) 
        return TRUE; 
    else 
        return FALSE; 
}

// 모든 원소에 대해 각각의 개별 집합을 생성
void initial (int n) { 
    index i;
    for (i = 1; i <= n; i++) 
        makeset(i); 
}

Disjoint Set Data Structure 2

typedef index set_pointer; 

// 각 노드의 부모와 깊이 정보를 저장하는 구조체
struct nodetype { 
    index parent; // 부모 노드의 인덱스
    int depth; // 트리의 깊이 (랭크) 
};

typedef nodetype universe[1..n]; 

universe U;

// 원소 i에 대해 i 자신의 집합을 생성
void makeset (index i) { 
    U[i].parent = i; // 초기에는 자기 자신이 부모
    U[i].depth = 0; // 초기 깊이는 0
}

// 원소 i가 속한 집합의 대표 원소(루트)를 반환
set_pointer find (index i) { 
    index j; 
    j = i;
    while (U[j].parent != j) 
        j = U[j].parent; 
    return j; 
}

// p와 q가 속한 두 집합을 하나의 집합으로 합침 (랭크에 따른 합치기)
void merge (set_pointer p, set_pointer q) { 
    if (U[p].depth == U[q].depth) { 
        U[p].depth += 1; // 깊이가 같다면 p의 깊이를 1 증가
        U[q].parent = p; // q의 부모를 p로 설정
    } 
    else if (U[p].depth < U[q].depth) 
        U[p].parent = q; // p의 깊이가 더 작다면 p를 q의 자식으로 연결
    else 
        U[q].parent = p; // q의 깊이가 더 작다면 q를 p의 자식으로 연결
}

// equal과 initial 함수는 이전 버전과 동일
// equal: 두 원소가 같은 집합에 속하는지 확인
// initial: 모든 원소에 대해 각각의 개별 집합을 생성

// 최악의 비교 횟수: O(m log m)

• 그래프 표현

• 알고리즘 적용

📁  시간 복잡도

• 단위 연산 : 비교문
• 입력 크기 : 정점의 수 n, 이음선의 수 m

m ≥ n - 1 시간 복잡도 : $mlgm$

최악의 경우 - 모든 정점이 다른 모든 정점과 연결이 되어있는 경우

시간 복잡도 : $n^2 lg n$