마이크로소프트 Azure 공식 문서의 가이드를 따라 Flask 프로젝트를 Azure Web App에 배포해 보자.

Azure Pipelines를 사용하여 Python 웹 앱을 빌드하고 Linux 기반의 Azure App Service에 자동 배포하는 CI/CD 환경을 구축

단순히 앱을 서버에 올리는 것을 넘어, 코드 레포에 커밋이 발생할 때마다 파이프라인이 자동으로 실행되어 빌드, 테스트, 배포가 이루어지는 MLOps의 기초 파이프라인을 경험할 수 있는 실습

1. 프로젝트 시작: 로컬 환경 준비하기

가장 먼저 공식 가이드에 따라 실습에 필요한 샘플 앱을 준비하고 로컬 환경에서 구동 여부를 확인했다.

• Microsoft의 샘플 저장소인 https://github.com/microsoft/python-sample-vscode-flask-tutorial 을 포크

• 포크한 레포를 로컬로 클론

• 가상환경 구축 및 활성화

• 의존성 설치: 가상환경 내에서 pip install --upgrade pip로 관리 도구를 최신화하고, pip install -r ./requirements.txt를 실행하여 앱 실행에 필요한 패키지들을 모두 설치

• 로컬 테스트: 로컬 환경에서 flask run을 실행하고 브라우저에서 http://localhost:5000에 접속하여 "Visual Studio Flask Tutorial"이라는 제목이 정상적으로 뜨는지 확인

2. Azure CLI로수동 배포하기

본격적으로 az webapp up 명령어를 써서 Azure 서버에 내 코드를 올려봤는데, 내 계정 환경 때문에 몇 가지 추가 설정이 필요했다.

• 지역 문제: 처음엔 기본 지역으로 설정됐는데, 구독 정책상 허용되지 않는 지역이라 RequestDisallowedByAzure 에러가 떠서, 그래서 한국 지역인 --location koreacentral을 붙여주니 해결됐다.
• 할당량 문제: 학생 계정이라 고성능인 PremiumV2 사양을 쓸 수 없어서 에러가 났다. 무료 티어인 --sku F1 옵션을 붙이면 된다.

az webapp up --name first-flask-app --location koreacentral --sku F1

3. Azure Pipelines로 자동 배포 환경 구축

이제 GitHub에 push 자동으로 배포되는 파이프라인을 만들어보자.

• Azure DevOps 연결: 서비스 연결을 통해 내 Azure와 DevOps 프로젝트를 연결
• YAML 파일 설정: Azure Pipelines이 자동으로 생성한 YAML 파일을 실습 환경에 맞춰 파이썬 버전만 수정했다.

설정을 다 끝내고 파이프라인을 돌렸는데 빌드가 시작조차 안 되고 실패했다.

Azure Pipelines 공식 트러블슈팅 페이지에 따르면 Azure의 최신 보안 정책 때문에... 신규 조직은 무료 호스팅 서버를 쓸 권한을 수동으로 신청해서 승인받아야 한다고 한다.

그래서 안내에 따라 무료 병렬 처리 요청 폼에 내 정보를 적어 제출했다.

승인 떨어지면 코드 간단하게 변경 후 push해서, 배포하는 과정을 진행하면 된다..

References

https://learn.microsoft.com/ko-kr/azure/devops/pipelines/ecosystems/python-webapp?view=azure-devops

이미지 이상 탐지 (Image Anomaly Detection)는 입력 이미지가 정상인지 비정상인지 판별하는 분류 문제이며, 이상 위치 추정 (Anomaly Localization) 은 이미지 내에서 결함이 존재하는 구체적인 픽셀 단위의 영역을 찾아내는 문제이다.

그러나 실제 산업 현장에서 이상 탐지 방법론을 적용하는 데에는 데이터 불균형이라는 큰 장벽이 존재한다. 제조 공정의 특성상 정상 데이터는 풍부한 반면, 이상(불량) 데이터는 매우 희소하기 때문이다. 또한 이상 형태는 얇은 스크래치 같은 미세한 결함부터 부품 누락과 같은 구조적 결합까지 매우 다양하고 공통된 패턴이 부족하여, 지도 학습(Supervised Learning) 방식으로 모든 이상 케이스를 학습하는 것은 사실상 불가능하다.

따라서 최근 연구들은 정상 데이터만으로 정상 분포를 학습하고, 테스트 시 정상 분포에서 벗어난 패턴을 이상으로 간주하는 비지도 학습(Unsupervised Learning) 또는 One-Class Classification 설정을 주로 따르고 있다.

PaDiM, PatchCore와 같은 기존 SOTA 방법론들은 높은 정확도를 달성했으나, 실용성 측면에서 한계를 보인다. 현장 적용 시에는 정확도뿐만 아니라 추론 속도, 메모리 사용량, 구현 난이도가 중요한 요소이다. 하지만 기존 방법들은 고차원 특징의 처리를 위해 복잡한 통계 모델을 사용하거나, 대규모 메모리 뱅크를 구축해야 하므로 현장 적용에 대한 한계가 존재한다.

SimpleNet은 이러한 문제점을 해결하고자, 복잡한 알고리즘을 배제하고 특징 공간에서의 간단한 노이즈 주입만으로 높은 정확도와 빠른 추론 속도, 적은 메모리 사용량을 동시에 달성하는 것을 목표로 제안되었다.

기존 연구의 한계

기존 이상탐지 방법론은 크게 (1) 재구성 기반, (2) 합성 기반, (3) 임베딩 기반으로 구분할 수 있다.

1) 재구성 기반 (Reconstruction-based)

재구성 기반 방법은 정상 데이터만으로 학습된 모델은 이상 영역을 정확히 복원하지 못할 것이라는 가정에 의존하며, 입력 이미지와 복원된 이미지 간의 픽셀 단위 오차를 이상 점수로 사용한다. 대표적으로 MemAE (ICCV 2019), GAN (2014 NerIPS)와 같이 Auto-Encoder나 GAN을 활용하는 방식이 있으며, 이미지 일부를 가리고 복원하는 Inpainting 기법을 사용하는 RIAD (Pattern Recognition 2021), SSPCAB (CVPR 2022) 등이 제안되어 왔다.

그러나 이상 영역이 정상 데이터와 유사한 저수준 패턴(Local edge, texture 등)을 공유하거나 Decoder의 성능이 과도하게 뛰어난 경우, 이상 영역까지 정상처럼 잘 복원해버리는 '일반화(Generalization)' 문제로 인해 비정상 이미지가 그대로 비정상 이미지로 복원되는 문제점이 존재한다.

2) 합성 기반 (synthesizing-based)

합성 기반 방법은 정상 이미지에 인위적으로 이상 영역을 합성하여 정상과 이상 사이의 결정 경계를 학습하는 방식이다. 대표적으로 정상 이미지의 작은 패치를 잘라내어 무작위한 위치에 붙여넣어 비정상 이미지로 합성하고, 정상 이미지와 합성된 이미지(비정상 이미지)를 구별하도록 학습하는 CutPaste(CVPR 2021)가 있다.

그러나 합성된 이미지가 현실적이지 못하고, 실제 현장의 다양한 불량 이미지와 외관상 일치하지 않아 모델이 실제 이상을 놓치거나, 정상 분포의 경계를 느슨하게 학습하여 미세한 결함을 정상으로 오탐지하는 문제가 생길 수 있다.

3) 임베딩 기반 (embedding-based)

최근 SOTA 성능을 기록하고 있는 임베딩 기반 방법은 ImageNet으로 사전학습된 CNN으로 특징을 추출한 뒤 통계 알고리즘을 활용해 정상 특징 분포를 모델링하는 방식이다.

대표적으로 사전 학습된 네트워크에서 추출된 패치별 특징을 다변량 가우시안 분포로 임베딩하여 정상 분포를 추정하는 PaDiM(ICPR 2021), 대표성 있는 특징들만 선별(Coreset sampling)하여 저장하여 메모리 뱅크(Memory Bank)를 구축하고, 테스트 시 저장된 특징들과의 최근접 이웃 거리를 계산하여 이상을 탐지하는 PatchCore(CVPR 2022), Normalizing Flow를 활용하여 복잡한 정상 특징의 분포를 가우시안 분포로 변환하여 모델링하는 CS-Flow(WACV 2022) 등이 있다.

그러나 산업 도메인과 ImageNet 간 도메인 차이(편향)로 인한 Mismatch 문제가 발생할 수 있으며, 공분산 역행렬/최근접 탐색/flow 등에서 오는 높은 계산 및 메모리는 실시간 탐지 적용에 제약이 된다.

이 외에도 Teacher 네트워크와 이를 모방하도록 정상 데이터로만 학습된 Student 네트워크를 활용하는 지식 증류 기반 방식이 있으며, 대표적으로 Student-Teacher AD (CVPR 2020)와, 이를 역방향으로 구조화하여 성능을 높인 Reverse Distillation (CVPR 2022) 등이 있다. 그러나 입력 이미지가 Teacher, Student 네트워크를 모두 통과해야 하므로, 단일 네트워크 모델에 비해 계산 복잡도가 높고 연산량이 많다는 단점이 있다.

제안 방법론

SimpleNet은 합성 기반 (synthesizing-based)과 임베딩 기반 (embedding-based) 방식의 장점을 활용하면서 해당 방법론들의 한계점에 대응되는 전략들을 제시한다.

1. Pre-trained feature를 그대로 사용하지 않고 Feature Adaptor를 통해 Target-Oriented Feature를 만들어 Domain Bias을 줄이고 타깃 도메인에 맞게 변환한다.

2. 이미지에 직접 이상 영역을 합성하는 대신, 특징 공간에서 정상 특징에 노이즈를 주입해 이상 특징을 생성한다.

3. 복잡한 통계 알고리즘 대신 단순한 MLP Layer로 구성된 Discriminator가 정상/이상 특징을 구분하도록 학습해 계산 효율을 높인다.

Feature Extractor

사전학습된 백본 네트워크 로부터 다중 계층 Feature를 추출하고, 각 특징 맵의 위치 (h, w)에 대해, 패치 크기 p를 갖는 이웃 를 다음과 같이 정의한다.

이웃 안의 Feature들을 집계함수로 계산하며, Adaptive Average Pooling을 사용하여 Local Pacth Feature를 획득한다.

서로 다른 계층에서 얻은 Local Feature Map 들을 가장 큰 해상도 로 resize한 뒤, 채널 방향으로 이어붙여(Channel-wise concat) 최종 Feature Map 를 만든다. 이를 하나의 Feature Extractor로 정의한다.

Feature Adaptor

산업 이미지의 분포는 사전 학습에 사용된 ImageNet과 상이하므로, 단순히 사전 학습 Feature를 그대로 사용하는 경우 도메인 불일치 문제가 발생할 수 있다. 이를 완화하기 위해 SimpleNet 은 Feature Adaptor 𝐺𝜃를 도입하여, 사전 학습된 특징을 타겟 도메인에 적합한 특징 공간으로 전이시킨다.

Feature Adaptor는 FC layer나 MLP와 같은 간단한 신경망으로 구성될 수 있으며, 실험 결과 단일 FC Layer를 사용하는 경우에도 충분한 표현력을 확보할 수 있었고, 오히려 복잡한 구조보다 더 우수한 성능을 보였다.

Feature Adaptor를 거친 adapted feature는 각 차원별 표준편차가 보다 일정한 분포를 형성하는 경향을 보이며, 이는 정상 특징과 이상 특징을 구분하는 과정에서 특징 공간이 더욱 조밀하고 안정적으로 형성되었음을 의미한다. 결과적으로, 이러한 특징 공간의 특성은 이상 특징과 정상 특징 간의 분리를 보다 용이하게 만들고, 이렇게 Feature Adaptor를 통해 생성된 특징은 이후 특징 공간에서 합성된 이상 특징과 함께 Discriminator에 입력된다.

Anomalous Feature Generator

직접적으로 이상 영역을 합성하기에는 실제 산업 환경에서의 이상 데이터가 극히 제한적이고 다양하므로, 이를 보완하기 위해 논문에서는 이미지 공간에서 결함을 조작하여 생성하는 기존 방식과 달리, 특징 공간에서 정상 특징에 간단한 노이즈를 추가하는 방법을 제안한다.

이상 특은 정상 특징 (Feature Adaptor를 통해 변환된 정상 특징)에 가우시안 노이즈 ε를 더하여 생성되며, 이러한 방식으로 생성된 이상 특징은 정상 특징과 함께 판별기(Discriminator)의 학습에 사용되며, 이를 통해 정상 특징 공간의 경계를 보다 명확하게 학습할 수 있다.

Discriminator

Discriminator는 각 위치 (h, w)에서 정상성을 직접 추정하는 점수 측정기로 작동한다.

학습 단계에서는 Feature Adaptor를 거친 정상 특징과, 가우시안 노이즈를 통해 생성된 이상 특징이 모두 입력된다. Discriminator는 정상 특징에 대해서는 높은 값, 이상 특징에 대해서는 낮은 값(음수 값)을 출력하도록 학습된다.

Discriminator는 일반적인 분류기와 유사하게 2- layer MLP 구조로 구성되며, 복잡한 통계 모델 대신 단순한 구조를 사용함으로써 계산 효율을 확보한다.

Loss function and Training

정상 특징과 이상 특징을 효과적으로 구분하기 위해, 본 논문에서는 Truncated L1 loss를 사용한다. 각 위치 (ℎ, w) 에서의 손실 함수는 다음과 같이 정의된다.

th+와 th-은 truncation 항으로 Discriminator의 출력이 일정 범위를 넘어서더라도 추가적인 Loss 증가를 제한함으로써 과도한 출력 값으로 인한 과적합을 방지하는 역할을 한다. 본 논문에서는 기본적으로 0.5, -0.5 로 설정된다.

이 손실 함수는 정상 특징에 대해서는 출력이 0.5 이상이 되도록 유도하고, 이상 특징에 대해서는 출력이 -0.5 이하가 되도록 유도한다. 이를 통해 정상과 이상 특징 간의 명확하지만 과도하지 않은 결정 경계를 설정할 수 있으며, 이는 다양한 형태의 결함에 대해 일반화 성능을 높이는 데 기여한다.

전체 학습 목적 함수는 모든 학습 샘플과 위치에 대해 평균 손실을 최소화하는 방식으로 정의된다. 학습 과정에서 Feature Extractor는 사전 학습된 가중치를 유지한 채 고정되며, Feature Adaptor와 Discriminator만이 역전파를 통해 업데이트된다. 이를 통해 일반적인 시각적 특징 표현은 유지하면서도, 타겟 도메인에 특화된 이상 판별 기준을 효율적으로 학습할 수 있다.

Inference and Scoring function

추론 단계에서는 Anomalous Feature Generator를 제거하고, Feature Extractor와 Feature Adaptor, Discriminator로만 구성된 단일 스트림 구조를 사용한다. 입력 이미지는 Feature Extractor와 Feature Adaptor를 순차적으로 통과하여 특징을 얻는다.

이상 점수는 Discriminator의 출력에 음수를 취한 값으로 정의된다.

이를 이용해 이상 영역을 나타내는 이상 map은 다음과 같이 정의된다.

이상 map은 입력 이미지 크기로 보간된 후, 경계의 부드러운 표현을 위해 가우시안 필터링이 적용되며, 최종적으로 이미지 단위의 이상 점수는 이상 map의 최대값으로 정의된다.

해당 과정들을 요약하면, 학습 단계에서는 정상 이미지 𝑥를 입력으로 하여, 사전 학습된 Feature Extractor 𝐹를 통해 정상 특징을 추출하고, Feature Adaptor 𝐺를 통해 타겟 도메인에 적응된 특징을 생성한다. 이후 적응된 특징에 가우시안 노이즈를 추가하여 이상 특징을 생성하고, 정상 특징과 이상 특징에 대해 Discriminator 𝐷를 학습한다.

이 과정에서 Feature Extractor는 고정되어 업데이트되지 않으며, Feature Adaptor와 Discriminator만 역전파를 통해 학습된다. 이를 통해 사전 학습 특징의 일반성을 유지하면서도, 타겟 도메인에 특화된 이상 판별 경계를 효율적으로 학습할 수 있다.

결과

실험 환경

논문에서는 모든 입력 이미지를 데이터 증강 없이 256×256으로 리사이징한 후, 224×224 크기로 center crop하여 실험을 수행하였다. 또한, 산업 이상 탐지뿐만 아니라 일반적인 원-클래스 이상 탐지 성능을 평가하기 위해 CIFAR-10 데이터셋을 활용한 One-Class Novelty Detection 실험도 함께 수행하였다.

평가 지표

이상 탐지 성능 평가는 이미지 단위 이상 탐지 성능을 측정하는 I-AUROC와, 픽셀 단위 이상 위치 추정 성능을 평가하는 P-AUROC를 기준으로 수행되었다.

구현 세부사항

모든 실험에서는 ImageNet으로 사전 학습된 백본 네트워크를 사용하였으며, 기본 설정으로 WideResNet50을 채택하였다. Feature Extractor에는 백본의 layer 2와 3에서 추출한 특징을 활용하였고, 이상 특징 생성을 위해 가우시안 노이즈의 표준편차 σ를 0.015로 설정하였다. Discriminator는 Linear–Batch Normalization–Leaky ReLU–Linear 구조로 구성되었으며, 모델은 총 160 epoch 동안 학습되었다.

실험 결과

실험 결과, SimpleNet은 전체 15개 클래스 중 9개 클래스에서 가장 높은 이상 탐지 성능을 기록하였다. Texture 클래스와 Object 클래스에 대해 I-AUROC는 각각 99.8%, 99.5%, 전체 평균 I-AUROC는 99.6%을 달성하였다. 이상 위치 추정 성능 측면에서도 평균 98.1%의 P-AUROC를 기록하여 비교 대상 방법들 중 가장 우수한 성능을 보였다. 또한 추론 속도 측면에서 Nvidia RTX 3080Ti GPU 기준 약 77 FPS를 기록하여, PatchCore(약 10 FPS 수준) 대비 약 8배 빠른 속도를 보여주었다.

Ablation Study

Ablation study에서는 (1) 특징 추출 설정, (2) Feature Adaptor 구조, (3) 노이즈 스케일 σ, (4) 손실 함수 및 백본 의존성을 중심으로 성능 변화를 분석하였다.

그 결과, 이웃 크기 p=3 및 Layer 2+3 조합이 가장 우수한 성능을 보였다. Feature Adaptor 구성에서는 편향이 없는 단일 FC Layer가 가장 안정적이고 높은 성능을 보였으며, 복잡한 Adaptor 구조는 과적합으로 인해 성능이 저하되는 경향이 관찰되었다.

또한 노이즈 스케일 σ는 성능에 큰 영향을 주었으며, σ가 너무 크면 경계가 느슨해지고 너무 작으면 학습이 불안정해지는 경향이 나타났다. 논문에서는 σ=0.015에서 최적의 성능을 보고하였다.

손실 함수 측면에서는 제안된 Truncated L1 loss가 Cross-Entropy loss 대비 약 0.2%의 I-AUROC 성능 향상을 보였고, 백본 의존성 실험에서는 ResNet18, ResNet50, ResNet101, WideResNet50 전반에서 비교적 안정적인 성능이 유지됨을 확인하였다. 추가로 CIFAR-10 기반 One-Class Novelty Detection 실험에서도 86.5%의 AUROC를 기록하여 비교 방법론들보다 우수한 성능을 보였으며, 이를 통해 산업 이상 탐지뿐만 아니라 일반적인 one-class 이상 탐지 문제에서도 효과적임을 확인하였다.

Unsupervised Anomaly Detection

• Density-based : 정상 데이터의 분포를 통해 비정상 데이터 탐지
• Classification-based : one- class classification 적용하여 비정상 데이터 탐지
• Reconstruction-based : 정상 데이터만을 복원하도록 학습하여 비정상 데이터 추론 시 재구축된 결과와의 차이로 비정상 데이터 탐지

Density-based

• 사전 학습된 모델 사용
• 추가적인 학습 필요 X

Related Work

• SPADE

  • 사전 학습된 네트워크로 추출한 feature를 그대로 사용
  • kNN 기반 anomaly score 측정

• PaDiM

  • 각 patch 위치별로 정상 분포의 mean, covariance를 추정

    → Mahalanobis distance로 anomaly score 계산 (같은 위치의 패치들끼리만 score 측정, 가장 먼 거리로 anomaly score 측정)

  • 한계 : input 이미지 크기 고정, patch alignment에 의존 (동일 위치의 patch feature끼리 비교)

PatchCore

• locally aware한 patch feature 만들기

• coreset subsampling → 계산 시간 줄이기

• PatchCore: 패치들이 공유 메모리 뱅크를 사용 → 다양한 정상 패턴을 전역적으로 저장

  이미지 정렬 요구가 줄어들고, 더 큰 범위의 정상 문맥을 활용 가능

• 다양한 크기/비율의 이미지를 처리할 수 있다는 점도 장점

Method

• Locally Aware Patch Features
• Coreset-Reduced Memory Bank
• Anomaly Detection & Localization

Locally Aware Patch Features

사전 학습 네트워크(ResNet-50, WideResNet-50-2)에서 feature를 추출

High level feature은 공간적 정보가 많이 사라짐 + 분류 작업에 최적화 되어있음

→ mid-level의 feature를 사용

• 예: ResNet block 2, 3의 feature 사용 (WideResNet-50-2의 2/3 블록)

  Local Neighbourhood 집계

추출한 feature map의 주변 patch들을 함께 사용

• feature map의 patch 중심 (h, w)를 기준으로 p × p 크기의 패치 영역

주변 이웃의 feature들을 모아 adaptive average pooling으로 하나의 벡터로 합침 (aggregation)

→ Locally Aware Patch Feature

Patchcore는 여러 계층 feature를 결합해 사용

• 계층 j, j+1 두 레벨에서 feature map를 뽑고
• 상위 계층 feature를 bilinear upsampling해서 해상도를 맞춤 (다음 계층 feature는 해상도가 낮으므로)

최종적으로 patch feature set 구축

• s : stride
• p : local neighbourhood window 크기

Memory Bank 구축

• 모든 정상 이미지를 대상으로 위 과정을 수행하고 합쳐 메모리 뱅크 생성

Coreset-Reduced Memory Bank

만든 메모리 뱅크는 정상 이미지의 모든 패치를 포함 → 크기가 매우 크고 연산 비용이 높음

Coreset 기반 서브샘플링

• 정상 분포를 충분히 대표하면서도 크기를 줄인 subset
• 단순 random subsampling에 비해 효율적

1. 처음 임의의 포인트를 선택
2. 매 단계마다 현재 선택된 집합에서 가장 멀리 떨어진 포인트를 추가
3. 원하는 개수가 될때까지 반복

• feature 차원이 크기 때문에 거리 계산이 느릴 수 있어, Johnson–Lindenstrauss으로 random linear projection 후 거리 계산 (feature를 저차원으로 임베딩 후 거리 계산)

Reduced memory Bank

• PatchCore-25% : M의 25%만 사용
• PatchCore-10% : 10%
• PatchCore-1% : 1%

메모리 뱅크의 1%만 사용해도 성능 거의 유지 + 속도 크게 향상

Anomaly Detection & Localization

Coreset으로 압축된 메모리 테스트 이미지의 각 패치가 정상 패치 공간으로부터 얼마나 떨어져 있는지를 계산하여 이상 여부를 판단

테스트 이미지의 모든 위치에 대한 patch-level feature

arg min : m test와 가장 가까운 정상 패치를 찾는 kNN

arg max : 모든 패치중에 가장 멀리 떨어져있는 이상치 패치 선택

→ 테스트 이미지에서 정상 분포와의 최소 거리가 가장 큰 패치를 선택

s∗이 anomaly score가 됨

*보정식 *

정상 패치의 국소 밀도(local density) 기반 weight를 곱해 희귀(normality가 낮은) 영역에서의 anomaly를 더 강하게 반영하는 보정식

Experiments

MVTec AD

• 15 클래스, 총 5354장, test 1725장
• 클래스별로 정상 train 이미지 + 정상/불량 test 이미지 + pixel GT mask 제공
• 이미지 전처리: resize + center crop (256→224 등)
• 평가:
  • Image-level AUROC
  • Pixel-wise AUROC
  • PRO (Per-Region Overlap) score: 다양한 anomaly 크기를 고려하는 segmentation 평가지표

Ablation Study

Low-shot Anomaly Detection

• 정상 샘플 개수를 1, 2, 5, 10, 16, 20, 50으로 줄여 실험

• 결과:
  • 정상 이미지의 20% 이하만 써도 기존 SOTA와 거의 비슷한 성능
  • 5-shot/10-shot에서도 SPADE/PaDiM보다 높은 이미지/픽셀 AUROC

정상 데이터가 많지 않은 상황에서도 성능이 잘 유지 → 실제 현장에서 유리

알파 알고리즘은 event log를 입력으로 받아 petri-net을 산출하는 알고리즘이다. Process Discovery와 관련해서 baseline이 되는 가장 기본적이며 단순한 알고리즘이다.

먼저 α-Algorithm의 Basic Idea에 대해 알아 보자.

입력과 출력

• 입력: 이벤트 로그 $( L \in B(A^*) )$

  • $( A )$: 활동 집합 (activities)
  • $( L )$: 여러 trace들의 multiset

• 출력: WF-net 형태의 Petri net

로그 기반 순서 관계 (Log-based Ordering Relations)

이벤트 로그에서 activity 간 순서 관계를 정의하는 네 가지 규칙

• directly follows $( a >_L b )$: 로그의 어떤 trace에서 a 바로 뒤에 b가 나옴

• causality $( a \to_L b )$: $( a >_L b )$ 이면서 $( b \not>_L a )$ → a 뒤에 b는 나오지만 b 뒤에 a는 나오지 않음

• parallel $( a \parallel_L b )$: $( a >_L b )$ 그리고 $( b >_L a )$ → a와 b는 서로 순서가 바뀌어 나타남 → 동시 실행 가능

• no relation $(a #_L b)$ : $( a \not>_L b )$ 이고 $( b \not>_L a )$ → 둘 사이에 직접적 순서가 없음

Footprint Matrix

위 4가지 relation을 기반으로 행렬 형태로 정리한 것

Discovery Patterns

α-algorithm은 log footprint를 가지고 패턴을 식별한다.

• Sequence: a → b → …

• XOR-split / XOR-join

  • 로그에서 a → b, a → c 이면서 b # c → split (둘 중 하나 선택)
  • a → c, b → c 이면서 a # b → join(둘 중 하나에서 c로 이어짐)

• AND-split / AND-join

  • a → b, a → c 이면서 b ∥ c → 병렬 실행 (AND-split)
  • a → c, b → c 이면서 a ∥ b → 동시 실행 후 join (AND-join)

이제 본격적으로 알파 알고리즘이 어떻게 이벤트 로그가 주어졌을 때, 이를 Petri Net으로 생성하는 지 알아보자.

1. $T_L$: 로그에 등장하는 모든 activity 집합

• 어떤 activity들이 로그에 나타나는 지 확인한다. → Petri Net의 transition으로 대응

2. $T_I$: 로그에서 시작 activity 집합 (trace의 첫 번째 activity들)

3. $T_O$: 로그에서 종료 activity 집합 (trace의 마지막 activity들)

4. $X_L$ : 입력 activity 집합 A, 출력 activity 집합 B 쌍들 중에서,

   $a \to_L b$ (인과관계) 찾기

   • A 내부 activity들은 서로 no relation (#)
   • B 내부 activity들도 서로 no relation (#)

5. $Y_L$ : $X_L$에서 최대 쌍(maximal pairs)만 선택 (중복/부분 집합 제거)

6. $P_L$: $Y_L$의 각 쌍 (A,B)에 대해 place $p(A,B)$ 생성 + 시작 place $i_L$, 종료 place $o_L$ 추가

7. $F_L$: $a \in A$이면 $(a, p(A,B))$ / $b \in B$이면 $(p(A,B), b)$ 시작 activity $(i_L, t)$, 종료 activity $(t, o_L)$

8. 결과: $\alpha(L) = (P_L, T_L, F_L)$

→ 이벤트 로그에 맞는 Petri Net 생성

References

Process Discovery는 event log를 통해 process model을 도출하는 과정이다.

(여기서 event log는 이전 글에서 소개했듯 multiset of traces이고, process model은 set of traces를 정의한다.)

DFG(Directly Follows Graph)

process discovery의 기본적인 접근 방식인** DFG(Directly Follows Graph)**의 경우 node와 arc로 구성된다. nodes는 시작/종료를 포함한 activity, arcs는 직접적으로 이어지는 activity의 관계를 나타낸다.

DFG는 직관적이며 이해하기 쉽고, 구현이 간단하다는 장점이 있지만 복잡한 흐름을 정확히 표현하지 못하는 구조적인 한계가 존재한다.

Petri Net

직관적이며, 동시성, 분기 등의 흐름을 명확히 표현할 수 있다는 장점이 있다.

*Petri-Net N = (P, T, F) *

P: place 집합 T: transition 집합 F : Directed arcs

Petri net은** node를 Place/Transition 2가지로 구분**한다.

Place : 원으로 표시되며, token이 머물 수 있는 node이다. Transition : 사각형으로 표시되며, activity를 나타낸다. input place에서 token을 소비하고, output place에 token을 생성한다. Arc : 화살표로 표시되며, place와 Transition을 연결한다. (P-P / T-T는 연결하지 않는다.)

Marked Petri-Net = (N, M) 여기서 N은 Petri-Net / M은 Marking의 집합이다.

Marking이란 현재 token의 상태/분포를 의미하는데, token은 검은 원으로 표시되며, marking에 따라 현재 상태를 결정한다.

*Labeled Petri-Net N = (P, T, F, A, I) * Petri-Net + A - activity에 label을 붙인 형태, I - labeling 함수 실제 activity 명을 붙여 현실의 프로세스를 모델링

위 사진을 통해 구조를 설명하면,

Place (○) : c1, c2, c3, c4, c5 (원) → 상태를 의미

Transition (□) : a, b, c, d, e, f, g, h (사각형) → activity

Token (●) : start에 있는 검은 점 → 현재 상태

Label Transition에는 단순 기호뿐 아니라 실제 활동명이 라벨링되어 있음. a: register request / b: examine thoroughly 등 ..

위 그림 예시에서 흐름을 정리해보면

시작 (start) : 토큰 1개가 위치

a (register request) 실행

AND-split → 토큰이 c1, c2 두 곳에 분산

• c1에서는 XOR-split -> b (examine thoroughly) 또는 c (examine casually) 중 하나 선택
• c2에서는 d (check ticket) 실행

c3, c4의 토큰이 AND-join 되고 e (decide) 실행

c5에서 XOR-split → g (pay compensation) 또는 h (reject request) 선택 ( f로 갈 경우 루프 )

end place에서 종료

추가 개념 정리

enabled : 특정 Transtion의 input place에 모두 token이 있는 상태 Firing : 특정 Transiton이 Enabled일 때, input place의 token을 소비 -> output place에 token을 생성

Initial Marking : 처음 상태의 Marking Reachable marking : Transition Firing을 통해 도달할 수 있는 marking Unreachable marking : Transition Firing을 통해 도달할 수 없는 marking

References

1. A practitioner's guide to process mining: Limitations of the directly-follows graph https://www.vdaalst.com/publications/p1101.pdf

2. https://www.researchgate.net/figure/Processing-of-the-directly-follows-graph_fig7_378827766 (DFG 사진 자료)

손실 함수(Loss Function)는 모델의 예측값이 실제 값과 얼마나 차이가 나는지를 수치적으로 나타내는 함수이다. 모델 학습의 목표는 이 손실 값을 최소화하는 방향으로 파라미터를 업데이트하는 것이다

따라서 어떤 손실 함수를 선택하느냐는 모델 성능에 매우 중요한 요소가 된다.

Cross-Entropy Loss의 한계

분류 문제에서 가장 널리 사용되는 손실 함수는 Cross-Entropy Loss이다. Cross-Entropy는 모델이 예측한 확률 분포와 실제 정답 분포 사이의 차이를 측정한다.

그러나 Cross-Entropy Loss는 클래스 불균형(Class Imbalance)에 취약하다는 한계를 가진다.

Hard Example과 Easy Example을 구분하지 못함

• Easy example: 이미 잘 맞히는 샘플
• Hard example: 모델이 반복적으로 틀리는 샘플

Cross-Entropy는 이미 잘 맞히는 easy example에도 동일한 loss을 부여한다. 결과적으로 중요한 hard example에 충분히 분류하지 못하는 문제가 발생한다.

이를 보완하기 위해 class weight를 추가한 Balanced Cross-Entropy가 활용된다.

Balanced Cross-Entropy

Balanced Cross-Entropy는 각 클래스에 가중치(α)를 부여하여 클래스 불균형 문제를 완화한다.

• α는 클래스 빈도의 역수이거나 하이퍼파라미터로 설정 가능

하지만 이 방식 역시 hard / easy example을 구분하지는 못한다는 한계를 가진다.

→ 이 문제를 해결하기 위해 등장한 것이 Focal Loss이다.

Focal Loss

Focal Loss의 핵심 아이디어는 다음과 같다.

“잘 맞히는 샘플의 영향은 줄이고, 모델이 어려워하는 샘플에 더 집중하자.”

이를 위해 Cross-Entropy Loss에 modulating factor(조절 항) 를 추가한다.

*γ (Gamma)의 역할 *

• gamma = 0 → 일반적인 Cross-Entropy Loss와 동일

• gamma > 0

  • 예측 확률 𝑝𝑡가 큰 easy sample → loss 값이 크게 감소
  • 예측 확률 𝑝𝑡가 작은 hard sample → loss 값이 거의 유지됨

즉, 모델이 이미 잘 맞히는 샘플보다, 틀리는 샘플에 집중하게 된다.

Cost-sensitive Learning 관점에서의 Focal Loss

Focal Loss는 본질적으로 Cost-sensitive Learning의 확장된 형태로 볼 수 있다.

• Cost-sensitive Learning → 소수 클래스의 오류에 더 큰 비용 부여
• Focal Loss → 소수 클래스 + hard example에 더 큰 비용 부여

특히 불균형 데이터에서는

• 다수 클래스 샘플 = easy example
• 소수 클래스 샘플 = hard example

인 경우가 많기 때문에, Focal Loss는 자연스럽게 클래스 불균형 문제까지 완화하는 효과를 가진다.

References

https://towardsdatascience.com/focal-loss-a-better-alternative-for-cross-entropy-1d073d92d075/

Event Log는 프로세스에서 발생한 activity들을 기록한 데이터이다.

하나의 프로세스는 여러 케이스(cases)로 이루어지고, 또 하나의 케이스는 여러 이벤트(events)로 이루어지며, 각 이벤트는 정확히 하나의 케이스와 관련된다.

이벤트는 다양한 속성(attributes)을 가질 수 있다. 필수적인 속성은 CaseID, Activity, Timestamp로, 이벤트 로그는 이 세 가지 속성을 반드시 가져야 한다.

• Case ID : 하나의 프로세스를 구분 (예: 고객 주문 번호, 환자 ID)

• Activity : 수행된 작업 (예: 주문 등록, 결제 확인, 배송 처리)

• Timestamp : activity가 발생한 시간(언제 실행되었는지)

추가적인 속성 Resource: 누가/어떤 시스템이 수행했는지, Costs: 발생한 비용

이벤트 로그는 위와 같이 Trace들의 multiset(중복 집합)으로 표기된다.

여기서 Trace란 activity들의 sequence (순서가 있는 나열)로, <a, b, c, d>가 Trace이며, 안의 a, b, c, d 등은 activity이다.

위 예시의 Case 1에서 “register request(요청 등록)”이 “reject request(요청 거절)”보다 먼저 발생해야 하는 것처럼, activity에는 순서가 존재하며, 표기에 반영된다.

따라서 이벤트 로그 전체에서, <a, b, c, d>의 순서를 가지는 케이스가 3개, <a, c, b, d>의 순서를 가지는 케이스가 2개, <a, e, d,>의 순서를 가지는 케이스가 1개 발생한 것으로 해석할 수 있다.

References

1. Process Mining: Data Science in Action http://repo.darmajaya.ac.id/5409/1/Process%20Mining_%20Data%20Science%20in%20Action%20%28%20PDFDrive%20%29.pdf

대부분의 분류 알고리즘은 각 클래스의 표본 수가 비슷할 때 각 범주의 특징을 고르게 학습할 수 있다. 하지만 현실 세계의 데이터에서는 특정 클래스의 비중이 극단적으로 작은 경우가 매우 흔하다.

• 표본 수가 많은 클래스 → Majority class
• 표본 수가 적은 클래스 → Minority class

이러한 데이터 불균형 상황에서는 모델이 다수 클래스에 과적합되어, 중요한 소수 클래스에 대한 예측 성능이 크게 저하되는 문제가 발생한다.

현실 세계의 대표적인 불균형 문제

• 암 발생 여부 예측
• 제조업 불량품 탐지
• 신용카드 사기 탐지
• 이상 탐지(Anomaly Detection)

-> 대부분의 경우, ‘정상’보다 ‘이상’을 정확히 잡아내는 것이 핵심 목표가 된다.

데이터 불균형 상황에서 Accuracy의 문제점

EX) 제조업 불량품 탐지

• 정상: 95%
• 불량: 5%

이때 모델이 모든 샘플을 정상으로 예측하면,

• Accuracy = 95%

하지만, 불량을 하나도 탐지하지 못하는 실제로는 전혀 쓸모없는 모델이 된다.

따라서 Accuracy는 불균형 데이터에서 신뢰할 수 없는 지표가 된다.

데이터 불균형 상황에서 적절한 평가 지표

F1 Score

F1 Score = Precision과 Recall의 조화 평균

• Precision: 소수 클래스라고 예측한 것 중 실제로 맞은 비율
• Recall: 실제 소수 클래스 중에서 얼마나 맞췄는가

F1 Score는 소수 클래스 탐지 성능을 균형 있게 평가할 수 있어 불균형 분류 문제에서 가장 널리 사용되는 평가 지표이다.

G-mean

• 양성 클래스 Recall × 음성 클래스 Recall의 기하평균
• 한쪽 클래스만 잘 맞추면 값이 낮아짐
• 두 클래스의 균형 잡힌 성능을 평가

-> 불균형 데이터에 비교적 강건한 지표

Sampling 기반 해결 방법

Undersampling

다수 클래스의 샘플을 제거하여 소수 클래스와 비율을 맞추는 방식

Random Undersampling

• 다수 클래스에서 무작위로 샘플 제거

• 장점: 계산 비용이 낮고 빠름

• 단점:

  • 중요한 샘플이 제거될 가능성
  • 샘플링마다 분류 경계가 달라질 수 있음

Tomek Links

Tomek Link 정의

어떤 관측치 $( x_k )$ 에 대해 $d(x_i, x_k) < d(x_i, x_j) \quad \text{or} \quad d(x_j, x_k) < d(x_i, x_j) $ 를 만족하는 관측치 $x_k$ 가 존재하지 않는 경우

두 샘플 ( x_i, x_j ) 는 Tomek link를 형성한다.

• 두 샘플 $( x_i, x_j )$ 서로가 서로의 최근접 이웃(Nearest Neighbor) 이다.

1. 서로 다른 클래스 샘플이 서로의 가장 가까운 이웃이면 → Tomek link 형성
2. 이 중 다수 클래스 샘플을 제거한다.

####

-> 결정 경계를 더 명확하게 만드는 효과

CNN (Condensed Nearest Neighbor Rule)

1. 다수 클래스에서는 무작위로 일부 샘플 선택
2. 소수 클래스에서는 모든 샘플 유지
3. 1-NN으로 원본 데이터를 분류
4. 정상적으로 분류된 다수 클래스 샘플 제거

-> 경계에 중요한 샘플만 남기는 방식

One-Sided Selection (OSS)

Tomek Links + CNN 결합 방식

• Tomek Links → 경계 근처 noisy 데이터 제거
• CNN → 경계에서 멀리 떨어진 다수 클래스 제거

-> 불필요한 다수 클래스 샘플을 효율적으로 제거

Oversampling

소수 클래스의 샘플 수를 증가시키는 방법

Random Over-Sampling

소수 클래스 샘플을 단순 복제

단점: 소수 클래스에 대한 과적합 위험

SMOTE

(Synthetic Minority Oversampling Technique)

소수 클래스에서 가상의 새로운 샘플 생성

절차

1. 소수 클래스 샘플 하나 선택
2. K개의 최근접 이웃 선택 (예: K=5)
3. 이웃 중 하나를 무작위로 선택
4. 두 점 사이에서 새로운 샘플 생성

두 점 간 차이 계산

새로운 관측치 생성

모든 소수 클래스에 대해 반복

장점

• 단순 복제보다 일반화 성능 우수

단점

• 클래스 경계가 겹치는 경우 노이즈 생성 가능

Borderline-SMOTE

• 분류 경계 근처의 샘플에 집중

핵심 개념

• 소수 클래스 샘플을 다음과 같이 구분

  • Safe
  • Borderline
  • Noise

• 이 중 Borderline 샘플에 대해서만 Oversampling 수행

ADASYN

(Adaptive Synthetic Sampling)

Borderline-SMOTE보다 한 단계 더 나아간 방식

• 다수 클래스 이웃이 많은 샘플일수록 더 많은 synthetic sample 생성

• 자동(adaptive)으로 생성 비율 조절

• 학습이 어려운 영역에 집중

References

• https://www.researchgate.net/figure/Illustration-of-Tomek-Links-technique_fig4_374101430

Logistic Regression (로지스틱 회귀)란 Binary Classification (이진 분류) 문제를 해결하기 위한 모델이다.

ex) 스팸 메일, 질병 양성/음성 분류 등

Sigmoid Function을 이용하여 특정 입력 데이터가 양성 class에 속할 확률을 계산한다.

Sigmoid Function

s자형 곡선을 갖는 함수

• x값이 무한하게 커질 경우 함수는 점점 1에 수렴하고, x값이 무한하게 작아질 경우 함수는 점점 0에 수렴한다.

• x가 어떤 값이 되더라도 함수의 값은 0 ~ 1 사이의 범위 내에 있으며, 0 ~ 1 사이의 값을 확률로 해석 가능하다.

• 미분 결과를 아웃풋의 함수로 표현 가능

Cross Entropy

성능 지표로 분류를 위한 Cross-entropy를 활용

Odds

Odds란 성공 확률을 p로 정의할 때, 실패 대비 성공 확률 비율로, 성공 확률을 실패 확률로 나눈 것이다.

로지스틱 회귀의 관점으로는, 범주 0에 속할 확률 대비 범주 1에 속할 확률을 의미한다.

Odds vs Probability

Odds와 Probability(확률)은 다른 개념이다.

• Odds는 사건이 발생할 확률 / 발생하지 않을 확률
• Probability는 사건이 일어날 경우의 수 / 전체 경우의 수로 표현된다.

Odds Ratio

어떤 사건이 발생활 확률

Odds Ratio가 Logistic Regression과 어떻게 관련이 있을까?

로지스틱 회귀 분석에서 독립 변수의 오즈비는 다른 모든 변수가 일정하게 유지될 때 단위당 오즈 변화가 해당 변수를 어떻게 증가시키는지를 나타낸다.

범주 0에 속할 확률 대비 범주 1에 속할 확률

Logit Transform (로짓 변환)

-> Odds에 log를 취해 선형결합으로 변환 가능

예측값이 0 ~ 1 사이의 값을 가져야 하는데, 로짓 변환을 통해 이를 해결함

Log-Odds

Odds에 log를 취한 것

베타1 : x가 한 단위 증가했을 때 log(Odds)의 증가량

파라미터 추정 - Maximum Likelihood Estimation (최대 우도 추정법)

최대 우도법은 주어진 데이터에서 모델의 파라미터를 최적화하는 방법이다. 로지스틱 회귀에서는 우도를 최대화하는 방법을 사용한다.
◦ 데이터를 관찰함으로써 이 데이터가 추출되었을 것으로 생각되는 최적의 분포를 찾는 것

log likelihood function이 최대가 되는 파라미터 결정 로그 - 우도함수는 명시적인 해가 존재하지 않는다. (No closed-form solution exists) 수치 최적화 알고리즘을 이용하여 해를 구해야함

Cross entropy : 두 확률분포의 차이 Cross entropy : 음의 log likelihood function의 기대값

Log likelihood function을 최대 = Cross entropy를 최소

Threshold

이진 분류를 위한 임계값 (threshold) 설정

로지스틱 회귀의 결과 값은 분류 확률이므로, 임계값을 통해 특정 클래스에 속할 지 말지 결정한다.

대부분의 임계값은 0.5이며, 값이 0.5를 초과하면 대상에 1이 할당되고 그렇지 않으면 0이 된다.

References

1. https://aws.amazon.com/ko/what-is/logistic-regression/

2. https://medium.com/analytics-vidhya/logistic-regression-understand-the-math-behind-the-algorithm-fe76ee591d70

3. https://medium.com/towards-data-science/https-towardsdatascience-com-what-and-why-of-log-odds-64ba988bf704

Vector space V 와 유한한 수의 벡터 x1,…,xk ∈V 가 있을 때, 아래의 형태를 만족하는 모든 v∈V (λ1 ,…,λk ∈R) 를 벡터 x1, …,xk 의 linear combination 이라고 한다.

간단하게 말하면 벡터를 스칼라곱과 벡터끼리의 합으로 표현한 것이고, 이때 스칼라 값은 0을 포함한 모든 실수가 될 수 있다.

Linear Independence (선형 독립)

주어진 벡터

v1, ... Vp ∈ Rn 에 대하, Vj가 이전 벡터 v1, ... vj-1 의 선형 결합으로 표현 가능하지 않은 경우

어떠한 Vj라도 발견되지 않는 경우 -> linear independent (선형 독립) 어떠한 Vj 라도 발견이 가능한 경우 -> linear dependent (선형 종속)

위의 식에서

x1, x2, ... , xn = 0 으로, 오직 한 개의 해만 존재하는 경우 - > linear independent (선형 독립) 다른 해가 존재하는 경우 -> linear dependent (선형 종속)

특정한 vector를 다른 vector의 연산으로 도출이 안되는 경우 -> linear independent (선형 독립) 특정한 vector를 다른 vector의 연산으로 도출이 가능한 경우 -> linear dependent (선형 종속)

Evaluating Linear Indenpendent

$\det \ =\ 0\ ->\ linear\ dependent$det = 0 −> linear dependent​ $\det \ \ne \ 0\ ->\ linear\ independent$det ≠ 0 −> linear independent​

Basis (기저벡터)

subspace W의 기저벡터는 아래 두 조건을 만족하는 벡터들의 부분집합이다.

1. 주어진 subspace W를 Full Span 하는 벡터

2. Linearly independent (선형독립으로만 이루어진 벡터)

• finite - dimensinal 의 vector space V에서 V의 차원은 Basis 의 수 이다.
• 직관적으로 vector space (벡터 공간)의 차원은 vector space 상의 독립적인 방향의 수라고 생각하면 된다.
• vector 개수 > dimension 개수이면 linearly dependent (선형 종속) 이다.
• dimension 미만의 개수의 vector가 만드는 집합은 subspace를 생성할 수 없다.

데이터를 가장 잘 설명하는 모델을 찾아 입력값에 따른 결과값을 예측하는 알고리즘

완벽한 예측은 불가능하기 때문에, 데이터의 실제값과 예측값의 차이를 최소한으로 하는 선을 찾아야한다.

선형 회귀는 크게 두 가지 종류로 나눌 수 있다.

• Simple Linear Regression (단순 선형 회귀)
• Multi Linear Regression (다중 선형 회귀)

Simple Linear Regression (단순 선형 회귀)

데이터를 설명하는 모델을 직선형태로 가정하며, 독립변수와 종속변수가 1개

데이터를 가장 잘 설명하는 모델이란 ? 실제값과 예측값과의 차이가 가장 작은 것

Yi (Dependent Variable)

• 종속 변수로, 예측하고자 하는 값

Constant/Intercept

• y 절편으로, 독립 변수 X 가 0일 때의 종속 변수 Y 값

Slope/Coefficient

• 기울기, 독립 변수X가 1 단위 증가할 때 종속 변수 Y가 얼마나 변하는지를 나타냄

Independent Variable

• 독립 변수 또는 입력 값으로, 종속 변수에 영향을 미치는 요인

목표 : 데이터를 가장 잘 설명하는 직선을 찾는 것

• 직선을 구성하는 y절편과 기울기가 찾아야 할 파라미터이며, 결국 선형 회귀는 최적의 파라미터를 찾는 문제라고 할 수 있다.

Multi Linear Regression (다중 선형 회귀)

독립 변수 여러 개 (2개 이상), 종속 변수 1개

다중 선형 회귀는 입력값이 1개일 경우 적용하는 단순 선형 회귀 알고리즘과 달리 입력값 X가 여러 개일 때 사용할 수 있는 회귀 알고리즘이다.

LinearRegression 클래스를 다중 선형 회귀에서도 사용이 가능하다.

Polynomial Regression (다항 회귀)

다항 회귀는 2차, 3차 방정식과 같은 다항식을 사용한 회귀

각 특성(feature)의 제곱을 새로운 특성으로 추가하여 선형 모델을 학습

fit()은 새롭게 만들 특성 조합을 찾고, transform()은 실제로 데이터를 변화한다.

from sklearn.preprocessing import PolynomialFeatures

np.random.seed(0)
X = 3 * np.random.rand(50, 1) + 1
y = X**2 + X + 2 + 5 * np.random.rand(50, 1)

poly = PolynomialFeatures(degree=2, include_bias=True)
poly_X = poly.fit_transform(X)

poly = PolynomialFeatures(degree, include_bias): Polynomial 객체 poly를 생성한다.

degree: 다항식의 차수 include_bias : 편향 변수의 추가 여부 (True/False) True로 설정하게 되면, 해당 다항식의 모든 거듭제곱이 0일 경우 편향 변수를 추가한다.

poly.fit_transform(X): 데이터 X와 X의 degree 제곱을 추가한 데이터를 반환

Polynomial이 더 잘 나타냄

Loss Function

그럼 어떻게? -> 실제 값과 예측 값 차이의 제곱의 합으로 비교하자

• 머신러닝이나 딥러닝 모델이 예측한 값과 실제 값 사이의 차이를 측정하는 함수

• 손실함수의 값을 최소화하는 것이 모델 학습의 목표

• 비용 함수(cost function) = 손실 함수(loss function) = 오차 함수(error function) = 목적 함수(objective function) 다 같은 말

References

1. https://www.jeremyjordan.me/linear-regression/

2. https://medium.com/@RaharditoDP/multiple-linear-regression-in-r-80098155ea5e

3. https://prasad07143.medium.com/a-brief-overview-of-simple-linear-regression-and-its-implementation-in-python-e6b5c180ff08

4. https://sixsigmadsi.com/multiple-regression-line/

Simple Linear Regression

import numpy as np
import matplotlib.pyplot as plt
from sklearn.linear_model import LinearRegression
from sklearn.model_selection import train_test_split''' 


```python 
np.random.seed(0) 
X = 5 * np.random.rand(100, 1)
y = 2 * X + np.random.rand(100, 1)```

train_X, test_X, train_y ,test_y = train_test_split(X, y, test_size = 0.3)


model = LinearRegression()
model.fit(train_X, train_y)

predicted = model.predict(test_X)

print("학습 데이터 평가점수 : {}".format(model.score(train_X, train_y)))
print("학습 데이터 평가점수 : {}".format(model.score(test_X, test_y)))

beta_0 = model.intercept_
beta_1 = model.coef_

plt.figure(figsize = (12, 6))
plt.scatter(train_X, train_y)
plt.scatter(test_X, test_y)
plt.plot(test_X, predicted, color='b')
plt.show()```

학습에 사용된 데이터가 아닌 처음 보는 새로운 데이터에 대해 올바른 예측을 수행하는 능력

what is good model ?

머신러닝에서 좋은 모델이란 현재 데이터를 잘 설명하며, 미레 데이터에 대한 예측 성능이 좋은 모델이다.

현재 데이터를 잘 설명하는 모델은, 곧 training error를 최소화하는 모델이다.

Error는 다음과 같이 나타낼 수 있다.

• Bias : 예측값의 평균과 실제값의 차이
• Variance : 예측 값들의 흩어진 정도
• Irreducible Error : 제거할 수 없는 오류

Error를 줄이기 위해서 Bias와 Variance를 줄여야 하는데,

Bias와 Variance는 Trade-Off 관계로 Bias와 Variance 사이의 균형을 맞추어야 오차를 최소화할 수 있다.

• Variance가 높을수록 예측값들이 서로 흩어져있다.

• Variance가 높으면 모델 학습이 과하게 학습된 것이다.

• Bias가 높을 수록 예측값들이 실제값들과 떨어져 있다.

• Bias 가 높으면 모델 학습이 제대로 되지 않았고, 모델 학습이 부족한 상태이기 때문에 더 학습을 해야한다.

그 중간 지점인 optimal capacity 를 찾아야하며, 이 부분이 훈련 데이터셋과 평가 데이터셋 모두에서 준수한 예측을 낼 수 있다.

Overfitting (과대적합)

High variance -> overfitting

모델이 주어진 훈련 데이터에 과도하게 맞춰져 새로운 데이터가 입력 되었을 때 잘 예측하지 못하는 현상

즉, 모델이 과도하게 복잡해져 일반성이 떨어진 경우를 의미함

과적합 - unstable, variance 증가 ( 모델의 복잡성이 올라가면 증가)

학습 데이터를 많이 모으면 variance가 줄어든다..

Underfitting (과소적합)

모델이 너무 단순하여 훈련 데이터에 적절히 훈련되지 않은 경우 훈련 데이터보다 테스트 데이터의 점수가 높거나, 두 점수가 모두 낮은 경우

지금까지의 내용을 종합한 그림

• Capacity : 모델의 복잡도

• Underfitting Zone : 과소적합 발생

• Overfitting Zone : 과대적합 발생 -> 일반화 성능이 떨어진다.

• Variance (초록색 곡선) : High variance -> overfitting

• Bias (파란색 곡선) : High bias -> underfitting

• Generalization Error (빨간색 곡선) : Bias와 Variance를 합한 총 오류, Optimal Capacity 지점(적절한 Bias와 Variance의 지점) 에서 Generalization Error가 최소화

References

1. https://djsaunde.wordpress.com/2017/07/17/the-bias-variance-tradeoff/

이를 방지하기 위해 feature selection(특성 선택) 이 필요하다.

feature selection의 핵심 목적은 Bias–Variance Trade-off에서 최적의 균형점을 찾는 것이다. 불필요한 feature를 제거하면 variance를 줄일 수 있지만, 너무 많은 feature를 제거하면 bias가 증가할 수 있으므로 신중한 선택이 요구된다.

Supervised Variable Selection — Exhaustive Search

Exhaustive Search(완전 탐색)는 가능한 모든 feature 조합을 평가하여 최적의 subset을 찾는 방법이다.

• 총 p개의 feature가 있을 때, 가능한 subset의 개수는 2ᵖ − 1
• 각 subset에 대해 모델을 학습하고 성능을 평가
• Training set이 아니라 Test set 성능 기준으로 최적 조합을 선택

이 방법은 이론적으로 최적해를 보장한다는 장점이 있다. 그러나 feature 수가 조금만 커져도 경우의 수가 기하급수적으로 증가하여 계산 시간이 현실적으로 감당 불가능해진다는 치명적인 단점이 있다.

Forward Selection

Forward Selection은 feature가 하나도 없는 상태에서 시작한다.

• 가장 성능 향상에 기여하는 feature를 하나씩 순차적으로 추가
• 한 번 선택된 feature는 절대 제거하지 않음

비교적 계산량이 적고 직관적이지만, 초기에 잘못 선택된 feature가 이후 단계에 영향을 미칠 수 있다는 한계가 있다.

Backward Elimination

Backward Elimination은 Forward Selection과 반대 방식이다.

• 모든 feature를 포함한 상태에서 시작
• 성능에 거의 영향을 주지 않는 feature를 순차적으로 제거
• 한 번 제거된 feature는 다시 선택되지 않음

초기 모델이 복잡해 계산 비용이 크며, 역시 전역 최적해를 보장하지는 않는다.

Stepwise Selection

Stepwise Selection은 Forward와 Backward를 번갈아 수행하는 방식이다.

• feature를 추가했다가, 필요 없으면 다시 제거
• 더 유연하게 subset을 탐색 가능

계산 시간은 증가하지만, Forward/Backward 단독 방법보다 더 나은 subset을 찾을 가능성이 높다.

전통적인 Feature Selection 방법의 한계

이러한 Exhaustive, Forward, Backward, Stepwise 방법들은 공통적인 단점을 가진다.

• feature 수가 커질수록 계산 시간이 급격히 증가
• 탐색 공간이 제한되어 최적 subset을 놓칠 가능성
• 시간 대비 성능 개선 효과가 낮은 경우도 많음 → 즉, 가성비가 떨어진다

그렇다면 이런 질문이 자연스럽게 생긴다.

모델이 error를 최소화하는 과정 자체에서 feature selection을 자동으로 수행할 수는 없을까?

Feature Selection 방법의 분류

이 질문에 대한 해답으로 feature selection 방법은 크게 세 가지로 나뉜다.

Filter Method

• 모델과 무관하게 feature 자체의 통계적 특성을 기준으로 선택
• 예: Correlation, ANOVA 등
• 빠르지만 feature 간 상호작용을 고려하지 못함

Wrapper Method

• 특정 모델을 사용해 feature subset의 성능을 직접 평가
• 예: Forward, Backward, Stepwise
• 성능은 좋지만 계산 비용이 큼

Embedded Method

• 모델 학습 과정에 feature selection을 내재화
• 대표적으로 Regularization(정규화) 기반 방법

Embedded Method의 장점

Embedded Method는 Wrapper Method의 장점을 일부 유지하면서 단점을 보완한다.

• 모델이 학습 과정에서 자동으로 feature subset을 선택
• feature 간 상호작용을 고려
• 반복적인 subset 탐색 없이도 비교적 효율적인 계산

이때 핵심 역할을 하는 것이 바로 Penalty Term이다.

Penalty Term (정규화 항)

Penalty Term는 축구 경기에서 반칙 시 부과되는 벌 과 같은 개념이다.

모델에서는 불필요하거나 중요도가 낮은 feature에 대해 계수 값이 커지는 것을 억제하는 벌점을 부여한다.

즉, 모델은

• Error를 최소화하면서
• 동시에 불필요한 feature의 영향력을 줄이도록 학습된다.

이 과정에서 자연스럽게 중요한 feature만 살아남게 되며, 모델 스스로 feature selection을 수행하게 된다.

L2 Regularization (Ridge Regression)

Regularization에서 L1은 절댓값, L2는 제곱을 사용한다.

L2 Regularization은 회귀 계수 β의 제곱합(L2-norm) 에 penalty term을 부여하는 방식이다. 즉, 모델은 제곱 오차(MSE)를 최소화하면서 동시에 계수의 크기를 제한하도록 학습된다.

이때 penalty term이 포함된 모델에서는 feature 간 스케일 차이가 결과에 직접적인 영향을 미치므로 scaling이 필수이다.

기하학적 해석 (MSE Contour)

MSE contour는 타원 형태를 가지며, 중심에서 멀어질수록 error가 증가한다.

• 제약 조건이 없는 경우 → MSE가 최소가 되는 지점은 LSE(Least Squares Estimator)

• 제약 조건(L2-norm 제한)이 있는 경우 → 타원(MSE contour) 과 원(L2 constraint) 이 만나는 지점이 제약을 만족하면서 error가 최소가 되는 해가 된다.

이 과정은 train error를 약간 증가시키는 대신 variance를 줄이는 과정으로 볼 수 있으며, overfitting을 방지하는 효과를 가진다.

계수의 크기를 줄이는 특성 때문에 Ridge Regression은 shrinkage method라고도 불린다.

Ridge Regression의 특징

• Feature selection은 수행되지 않음
• 불필요한 feature라도 계수는 0에 매우 가깝게만 수렴
• feature 스케일에 민감 → 정규화 필수
• Multicollinearity(다중공선성) 문제 완화에 효과적

릿지 회귀는 선형 회귀와 구조는 같지만, 각 feature가 출력에 미치는 영향을 전반적으로 줄이도록 규제를 거는 모델이다.

다중공선성 문제는 두 개 이상의 feature가 강한 상관관계를 가질 때 발생하며, Ridge Regression은 이를 완화하여 모델의 안정성을 높여준다.

Lasso Regression

L1 Regularization

Lasso는 회귀 계수의 절댓값 합(L1-norm) 에 penalty term을 부여한다.

기하학적으로 보면,

• Ridge (L2) → 원 형태의 제약 조건
• Lasso (L1) → 마름모 형태의 제약 조건

이 차이 때문에 Lasso는 최적해가 좌표축과 만나는 경우가 많아지고, 그 결과 일부 계수가 정확히 0이 된다.

→ 해당 feature는 모델에서 완전히 제외됨

즉, Lasso는 Regularization + Feature Selection을 동시에 수행한다.

Lasso의 최적화 특성

Lasso는 절댓값을 사용하기 때문에 미분이 불가능하며, Ridge와 달리 closed-form solution이 존재하지 않는다.

따라서 실제 학습에서는 Numerical optimization 방법을 사용한다.

λ (lambda)의 역할

• λ가 클수록 → 선택되는 변수 수 감소 → 단순한 모델 → underfitting 위험 증가

• λ가 작을수록 → 많은 변수 사용 → 복잡한 모델 → overfitting 위험 증가

Ridge와 Lasso 모두 λ가 커질수록 계수의 크기는 줄어든다.

• Ridge → 크기가 큰 계수부터 빠르게 감소 (제곱 penalty)

• Lasso → 중요하지 않은 계수가 먼저 0이 됨 → 명확한 feature selection 효과

Ridge vs Lasso 정리

• Ridge

  • 계수를 전반적으로 줄임
  • feature는 제거되지 않음
  • 다중공선성 완화에 효과적

• Lasso

  • 중요하지 않은 feature를 0으로 만듦
  • feature selection 가능
  • 해석 가능성이 높은 모델 생성

Elastic Net Regularization

Elastic Net은 L1-norm과 L2-norm을 결합한 정규화 기법이다. 즉, Ridge와 Lasso의 장점을 동시에 활용하는 방식이다.

• L1-norm → feature selection
• L2-norm → 계수 안정화 및 다중공선성 완화

Elastic Net의 목적 함수는 오차를 최소화하면서, L1과 L2 penalty를 동시에 제어하는 것이다.

Elastic Net의 핵심 특징

Elastic Net은 상관관계가 강한 feature들을 함께 선택하거나 함께 제거하는 경향을 가진다.

• Lasso의 경우 → 상관관계가 높은 변수 중 하나만 선택하는 경향
• Elastic Net의 경우 → 상관관계가 높은 변수들을 그룹처럼 동시에 유지

이 특성 때문에 Elastic Net은 feature 간 상관관계가 강한 데이터셋에서 특히 유리하다.

λ₁, λ₂ (또는 α)의 역할

Elastic Net에서는 두 개의 penalty 강도를 조절한다.

• λ₁ (L1 penalty) → sparsity(희소성) 조절, feature selection 영향
• λ₂ (L2 penalty) → 계수 안정화, 다중공선성 완화

실제로는 일정 범위 내에서 λ₁, λ₂를 함께 조정하며 실험하고, 가장 좋은 예측 성능을 보이는 조합을 선택한다

Elastic Net의 단점

• Ridge나 Lasso에 비해 튜닝해야 할 하이퍼파라미터가 많음
• 더 많은 실험과 계산 비용 필요

현실 데이터에서의 안정성과 성능은 더 뛰어난 경우가 많다.

해 공간 관점에서의 이해

Elastic Net의 제약 조건은 L1과 L2 제약이 혼합된 형태의 해 공간을 만든다.

• Ridge → 원형 해 공간
• Lasso → 마름모 해 공간
• Elastic Net → 두 형태가 섞인 부드러운 제약 공간

이로 인해 계수가 0이 되기도 하고, 동시에 안정적으로 shrinkage 되는 특성

확장된 Regularization 기법들

Elastic Net을 확장한 다양한 정규화 기법들도 존재한다.

• Fused Lasso → 인접한 feature 간의 차이까지 함께 규제
• Group Lasso → feature를 그룹 단위로 선택/제거
• GRACE → feature 간의 그래프 구조를 반영한 정규화
• Non-convex Penalties → L0에 가까운 sparsity를 유도하기 위한 비볼록 정규화

구조적 특성을 가진 데이터에서 특히 유용하게 사용된다.

정리

• Ridge → 계수 안정화, 다중공선성 완화
• Lasso → 명확한 feature selection
• Elastic Net → 두 장점을 결합한 실전형 정규화 기법

특히 고차원 데이터 + 강한 feature 상관관계 환경에서는 Elastic Net이 가장 현실적인 선택이 되는 경우가 많다.

Machine Learning is “the field of study that gives computers the ability to learn without being explicitly programmed.”
- Arthur Samuel, 1959

머신러닝이란 명시적인 프로그래밍 없이, 컴퓨터가 학습하는 능력을 갖추게하는 연구 분야이다.

A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E." - Tom M.Mitchell, 1997

작업(T)에 대해 기준(P)로 측정한 성능이 경험(E)로 인해 향상되었다면, 프로그램은 E로부터 학습한다고 말할 수 있다.

즉, 머신러닝은 전통적인 프로그래밍 방식과 다르게 컴퓨터가 스스로 학습할 수 있는 능력을 갖게 하는 것이다.

학습 (Learning)

머신러닝에서 학습이란 데이터를 가장 잘 설명하는 모델을 찾는 과정으로, 실제 정답과 예측 결과 사이의 오차를 줄여나가는 최적화 과정이다.

머신러닝의 분류 (Supervised, Unsupervised, Reinforcement)

1. Supervised Learning (지도 학습)

입력 데이터에 대한 정답(Label)을 예측하기 위해 학습하는 방식이다. 데이터에 정답(Label)이 존재하며, 크게 회귀(Regression)과 분류(Classification)으로 나눌 수 있다.

2. Unsupervised Learning (비지도 학습)

지도학습과 달리 데이터에 정답이 존재하지 않으며, 입력 데이터 속에 숨어있는 규칙성을 찾기 위해 학습하는 방식이다.

3. Reinforcement Learning (강화학습)

어떠한 환경(Environment)에서 정의된 주체(Agent)가 행동(Action)을 선택하면 그 행동에 맞는 보상(Reward)를 주어 보상을 최대화하는 행동을 선택하도록 학습하는 방식이다.

References

1. https://medium.com/towards-data-science/supervised-vs-unsupervised-learning-14f68e32ea8d
2. https://medium.com/towards-data-science/reinforcement-learning-101-e24b50e1d292

이미지 처리(Image Processing)는 이미지를 입력으로 받아 의미 있는 정보를 향상, 변환, 추출하는 기술을 의미한다.
처리 방식에 따라 크게 아날로그 이미지 처리와 디지털 이미지 처리로 구분된다.

Analog Image Processing

• 물리적 수단을 이용한 이미지 조작
• 광학 필터, 렌즈, 필름 현상 과정 등이 포함
• 연속적인 신호 기반 처리

Digital Image Processing

• 컴퓨터가 디지털 이미지를 대상으로 수행
• 수학적 알고리즘과 계산 기법에 기반
• 이미지 향상(Image Enhancement), 이미지 복원(Image Restoration), 특징 추출(Feature Extraction) 등이 포함됨

디지털 이미지 처리를 이해하기 위해서는 모든 이미지의 최소 단위인 픽셀(pixel)의 역할을 이해하는 것이 중요하다.

디지털 이미지와 픽셀(Pixel)

디지털 이미지는 유한한 픽셀의 집합으로 구성된다.
각 픽셀은 색상(color)과 밝기(intensity)에 대한 정보를 담고 있다.

• 픽셀(pixel)은 picture + element의 합성어
• 이미지를 확대하면 보이는 가장 작은 단일 점
• 이미지 처리 알고리즘은 픽셀 단위 또는 픽셀 집합에서 작동함

특히 흑백(그레이 스케일) 이미지에서 단일 픽셀 값은 밝기 정보를 나타내는 숫자로 해석된다.

이미지 처리의 주요 단계

이미지 획득 (Image Acquisition)

• 카메라, 스캐너, 캡처 장치 등을 통해 이미지 획득
• 아날로그 신호를 디지털 형식으로 변환하여 컴퓨터에서 처리 가능하게 함

이미지 개선 (Image Enhancement)

• 이미지 품질을 향상시키는 단계
• 주요 작업:
  • 노이즈 제거 (Noise Reduction)
  • 명암 조절 (Contrast Adjustment)
  • 색상 보정 (Color Correction)
• 히스토그램 평활화(Histogram Equalization), 샤프닝(Sharpening), 필터링 기법 활용

목표: 이미지를 더 명확하고 해석하기 쉽게 만드는 것

이미지 분석 (Image Analysis)

• 이미지에서 유용한 정보 추출
• 주요 작업:
  • 특징 추출 (Feature Extraction)
  • 패턴 인식 (Pattern Recognition)
  • 객체 검출 (Object Detection)
• 대표 기법:
  • 에지 검출 (Edge Detection)
  • 코너 검출 (Corner Detection)
  • 텍스처 분석 (Texture Analysis)

이미지 해석 및 이해 (Image Interpretation & Understanding)

• 분석 결과를 기반으로 의미 있는 판단 수행
• 이미지 분류, 검색, 인식 등의 고수준 작업 포함
• 머신러닝, 딥러닝, 패턴 매칭 기법이 활용됨

이미지 처리의 활용 분야

이미지 처리는 다양한 산업 및 일상 환경에서 핵심 기술로 활용된다.

• 의료 영상 (X-ray, CT, MRI)
• 위성 및 항공 영상
• 자율주행 차량
• 스마트폰 카메라 및 보정 기술

해상도(Resolution)와 픽셀 밀도

해상도(Resolution)

이미지가 보유한 픽셀의 총량을 의미한다.

• 표기 예: 1920 × 1080
  → 가로 1920픽셀, 세로 1080픽셀
• 해상도에 영향을 주는 요소:
  • 카메라 센서 크기
  • 스캐너 정밀도

대표 해상도 용어

• WVGA: 800 × 480
• HD (720p): 1280 × 720
• FHD (1080p): 1920 × 1080
• QHD (1440p): 2560 × 1440
• 4K / UHD: 가로 픽셀 약 4000 이상

픽셀 밀도 (PPI, Pixel Per Inch)

• 디스플레이에서 픽셀이 얼마나 촘촘히 배열되어 있는지 나타내는 지표
• PPI가 높을수록 이미지와 텍스트가 더 선명
• VR, AR과 같은 몰입형 기술에서 특히 중요

서브 픽셀(Sub-pixel)

• 하나의 픽셀을 구성하는 RGB 색상 단위
• 디스플레이는 RGB 서브 픽셀의 빛 강도를 조절하여 다양한 색상 표현

색 공간(Color Space)

Grayscale

• 색상 정보 없이 밝기(intensity)만 표현
• 값 범위: 0(검정) ~ 255(흰색)
• 에지 검출, 텍스처 분석 등에서 색상 정보가 오히려 방해가 될 수 있어 유용

RGB

• Red, Green, Blue 세 채널로 구성
• 각 채널은 독립적인 색상 정보 저장
• 디지털 디스플레이에서 가장 일반적으로 사용

CMYK

• Cyan, Magenta, Yellow, Key(Black)
• 인쇄물에서 사용
• 빛을 더하는 RGB와 달리 빛을 빼는 방식으로 색상 표현

HSV

• 인간의 색 인지 방식에 맞춘 색 공간
• Hue(색조), Saturation(채도), Value(밝기)
• 색상 조작 및 분할(Segmentation)에 유리

비트(Bit)와 색 깊이(Color Depth)

비트는 디지털 정보의 최소 단위이며, 이미지에서는 표현 가능한 색상 범위를 결정한다.

• 1비트: 흑백 이미지 (0 또는 1)
• 8비트: 0~255, 일반적인 그레이 스케일
• 16비트: 의료 영상 등 고정밀 표현
• 24비트: RGB 이미지 (일반적인 컬러 이미지)
• 48비트: 전문 색상 작업에 사용

정리

• 디지털 이미지는 픽셀의 집합이며, 픽셀 단위 처리가 이미지 처리의 핵심
• 이미지 처리는 획득 → 개선 → 분석 → 해석의 단계로 구성
• 해상도, 픽셀 밀도, 색 공간, 비트 깊이는 이미지 품질과 직결됨
• 이후 머신러닝, 딥러닝 기반 컴퓨터 비전의 기초가 되는 개념들

결정변수와 목적함수 (최대화 or 최소화), 제약조건들에 대한 식을 만들 수 있다.
선형계획법(LP: linear programming) : 최적화 기법 중 하나이자, 제약조건들과 목적함수가 선형적인 관계를 유지해야한다. ex) f(x1, x2) = 3x1x2 + 2x2 의 형태면 비선형적이기 때문에 선형계획법을 적용시키지 못한다.

예제) 수공예 하회탈 제조업체인 안동하회탈은 양반탈과 각시탈, 두 가지 탈을 만들어 팔고 있다. 양반탈의 개당 판매가는 2만 7천 원이고, 재료비는 1만 원이며, 가변비용(노동비, 간접비 등 탈 하나 만들 때마다 발생하는 비용)은 1만 4천 원이다. 각시탈의 경우, 개당 판매가는 2만 1천 원이고, 재료비는 9천 원, 그리고 가변비용은 1만 원이라고 한다. 하회탈을 만드는데는 목공기술과 마무리기술, 두 종류의 기술이 필요하다. 목공기술이란 나무를 양반이나 각시 모양으로 깎는 기술을 말하고, 마무리기술은 도색작업, 마무리 등의 상품화 기술을 말한다. 양반탈 한 개를 만드는 데는 1시간의 목공기술과 2시간의 마무리기술이 필요하고, 각시탈 한 개를 만드는 데는 1시간의 목공기술과 1시간의 마무리기술이 필요하다. 매주 안동하회탈에서는 필요한 재료는 모두 구입할 수 있으나 노동력에는 한계가 있어 매주 80시간의 목공기술과 100시간의 마무리 기술을 이용할 수 있다. 과거의 경험으로 볼 때 각시탈의 수요는 무제한이고, 양반탈은 많아야 40개가 팔렸다. 안동하회탈은 주당 이윤을 최대화하기 위한 제품 생산 계획안을 마련하고자 한다. 즉, 주당 양반탈과 각시탈을 각각 몇 개씩 생산하는 것이 안동하회탈의 주당 이윤을 최대화시킬 수 있겠는가?

Decision Variables (결정 변수) : X1 : 주당 양반탈 생산 개수, X2 : 주당 각시탈 생산 개수

Objective function (목적 함수) : 주당 이윤 = (양반탈 1개 이윤) x X1 + (각시탈 1개 이윤) x X2

양반탈 이윤 = 27000 (판매가) - 10000 (재료비) -14000 (가변비용) = 3000

각시탈 이윤 = 21000 - 9000 - 10000 = 2000

주당 이윤을 최대화해야 하므로 MAX Z = 3X1 + 2X2

Constraints (제약 조건) : 목공기술은 80시간, 마무리기술은 100시간 양반탈은 많아야 40개가 팔림

How to find optimal solution ?

Graphical method

문제의 제약조건들을 순서대로 (1), (2), (3), (4) 라고 하고 그래프를 그려보면 위와 같은 형태가 나온다. 각각의 범위를 고려해 봤을 때 노란색으로 칠해진 부분이 feasible region (실현 가능한 대안들의 집합) 이 되고 여기에서 optimal solution 을 찾기 위해 목적함수 Z = 3X1 + 2X2 역시 그래프 상에서 표현해준다.

목적함수 Z = 3X1 + 2X2 는 기울기가 1.5인 직선으로 표현할 수 있고 feasible region에서 영역이 최대가 되게끔 이동시켜주면 X1 = 20, X2 = 60 이 된다. 이에 따라 최대 이윤은 Z = 3 x 20 + 2 x 60 = 180, 천 원단위로 바꿔주면 180000원으로 구할 수 있다.

Finding vertices

꼭짓점으로 찾는 방법은 feasible region의 모든 꼭짓점을 표시하고 각 꼭짓점에서 목적 함수의 최댓값을 찾는 방법이다. 위 그림에서 꼭짓점은 (0, 0), (0, 80), (20, 60), (40, 20), (40, 0) 이고, 각 꼭짓점에서의 Z 값은 0, 160, 180, 160, 120 이며, 최댓값은 180이고 이때의 X1 X2 값은 20, 60으로 최적해를 찾을 수 있게 된다.

Graphical method의 단점은 변수의 개수가 2개 초과일 경우 적용하기 어렵다는 단점이 있는데, 3개 이상의 변수가 존재할 경우 Simplex method 으로 해결할 수 있다.

Simplex method

Convert to Standard Form slack ( s1 s2 s3 ) 를 활용하여 주어진 제약 조건을 등식으로 만들어준다.

​X1 + X2 + S1 = 80

2X1 + X2 + S2 = 100

X1 + S3

Initial Simplex Tableau

각 변수의 계수들로 안의 내용을 채워준다. Z = 3X1 + 2X1 목적함수의 식의 경우 Z - 3X1 - 2X2 = 0으로 변형하여 넣어준다. (최대화하는 문제의 경우 목적함수의 계수가 음수이다.)

다음으로는 Pivot Column과 Pivot Row를 찾는다. 목적함수를 기준으로 가장 최소가 되는 값을 찾고, 그 값을 포함하는 열이 Pivot Column이 된다. 예시에서는 -3 의 값이 가장 작고, 피벗 열은 X1 이 된다.

Pivot Row는 Pivot Column에 대해 RHS / Pivot Column 의 값이 최소가 되는 행이 된다. 예시에서는 40/1 이 40으로 가장 작으므로 S3가 Pivot Row가 된다.

그 다음으로는 Pivot Row를 제외하고 나머지 행들을 모두 0으로 만들어야하는데, Pivot Row를 활용하여 행 연산을 진행한다. (가우스 소거법에 적용시키는 행 연산 그대로 적용하면 된다.) (X1 열의 S3 행을 제외한 나머지 행들이 모두 0이 된 형태)

다음으로 X2열에서 -2가 포함 되어 있으므로 X1 열에 한 계산과 똑같이 RHS / Pivot Column 값의 계산을 한 후 최소가 되는 값을 찾아 이후 과정을 똑같이 수행한다.

계산을 마치면 최종 형태는 아래 그림과 같이 나온다.

목적함수의 행에 모두 양수가 나왔으므로 이 형태가 최종 형태가 되고, 표에서 X1 = 20, X2 = 60, Z = 180 임을 알 수 있다.

참고영상 : https://www.youtube.com/watch?v=9YKLXFqCy6E

Google OR-Tools - Solver

Solver를 활용하여 해결할 수도 있다.

결국 선형계획법 문제가 주어졌을 때는, 결정 변수와 목적 함수를 설정하고, 올바른 식들을 도출해내기만 하면 위 방법론들로 문제를 해결할 수 있다.