• 
• 위처럼 convex한 함수는 항상 최적의 해를 찾음(local과 global이 같음)
  • 하지만 실제모델은 저런 모양은 아니다
• 
• 경사하강법으로 최적의 해를 찾아도 에러가 크면 다른 모델을 사용해야할 필요가 있다

Batch Gradient Descent

• 모든 트레이닝 데이터를 사용하는 일반적인 방법
  • 트레인 데이터가 많으면 전부 사용하지 않는 방법도 있긴한데 여긴 없음

행렬

• (3,2) -> 밑으로 먼저 3
• 벡터 : nx1형태의 행렬이 벡터

선형회귀

• 
• 선형모델 유지를 위해 제곱형태가 없어야함
• 세타0를 바이오스로 사용할때 벡터곱에서 1를 곱하는 형식으로 따로 세타0을 더하는 과정을 생략하기도 함
• feature의 범위
  • 
  • 피처들을 동시에 바꾸기 때문에 범위가 다르면 범위가 큰 피처가 최적해를 잘 찾아가지만 작은 피처는 그렇지 않음
  • 피처들의 범위를 맞춰줘야함 -> feature scaling

제곱이 있는 선형

• 
• x제곱, 세제곱을 x2,x3로 치환하여 평면의 개수를 늘려 선형성을 유지할 수 있음

분류(regression)

• loss함수를 로그함수로 사용하는 이유 -> convex형태로 만들어서 local미니멈에 머물지 않게 하기 위해
• 
• 정답값이 1, 0일때의 로스함수를 하나로 합친 형태
  • y에 1이나 0을 대입할때 뒤, 앞 부분이 날아감
• 시그모이드 미분(과정?) -> 시그모이드(1-시그모이드)

군집화(Clustering)

k-means

• 랜덤한 점 k개를 찍음 -> 기준점

• 모든 점을 기준점중 가까운 기준점에 매칭

• 매칭된 점들의 평균값으로 기준점을 이동시킴

• 위의 단계를 평균이 편하지 않을때까지 반복

• 처음 찍는 기준점의 위치에 따라 결과가 달라질 수 있음

NN(Neural Networks)

• 
• 각 색깔에서 하나의 곱셉이 하나의 화살표를 의미
  • 연결된 모든 선이 결과에 관여함

bagging and boosting

• bagging
  • 데이터셋을 여러개 만드는 것
  • 
  • 분산값이 떨어져서 성능이 향상됨

Oauth

• 
• 클라이언트가 우리가 만든 서비스, 리소스 오너가 사용자, 리소스 서버는 구글, 카카오등 믿을만한 그런 서버(리소스 오너가 가입되어있음), 어떤 기능을 제공해주는 존재
• Oauth는 위 3자간의 관계를 정리한것

등록

• 일단 Client가 Resource server에 등록되어야함(이걸 register라고함, client의 아이디와 비밀번호가 같이 저장)

인증

• 등록이 끝나면 Resource Owner가 Client에 접속
• 이때 로그인을 하라고함
  • 
  • 위처럼 리소스 오너가 클라이언트에 페이스북,카카오등을 통해 로그인을 하면 클라이언트가 보낸 링크로 리소스오너가 리소스 서버로 접속하는것
  • 그럼 리소스 서버는 그 링크를 받아서 링크에 있는 클라이언트 id이 있는지 확인함
  • 
  • 있으면 스콥에 해당하는 기능을 허용할건지 물어봄(리소스 서버가 리소스 오너한테)
• 위의 과정은 리소스 오너의 허락을 받은것

• 그리고 리소스 서버의 허락도 받아야함
• 리소스 서버가 리소스 오너에게 임시 코드를 보냄, 그러면 리소스 오너가 그 코드를 가지고 클라이언트에게 접속, 클라이언트는 그 코드를 받아서 리소스 서버로 접속
• 리소스 서버가 클라이언트가 접속했을때 클라이언트의 id에 해당하는 임시코드가 일치하는지 확인함
• 임시코드 : authorization 코드

• 그 다음단계가 엑세스 토큰을 발급하는 것
• authorization코드를 지우면서 AccessToken을 리소스 서버가 생성해서 클라이언트에게 보내줌
• 그 이후엔 클라이언트가 그 토큰으로 접속하면 리소스 서버가 스콥에 해당하는 기능과 유저의 정보를 클라이언트에게 제공하는것
• 이 기능을 api라고함

• refresh token
• 위의 access token은 수명이 있음
• 수명이 끝나면 api를 제공받지 못함
• 그때 위의 과정을 처음부터 안하고 다시 access 토큰을 받게 해주는게 refresh token
• access와 refresh를 보통 같이 발급함, api를 제공받을때 access token을 제출하다 수명이 다하면 refresh token을 리소스 서버에게 제출하면 됨

Network

• ARP level

  • ARP spoofing

    • ARP 단계(MAC주소를 속이는것)
    • 
    • 라우터인척하거나 서버인척해서 sniffing까지함

  • man in the middle attack

    • 위에서 B가 공격한 방법이 MIMA

  • Smurf attack

    • 원래 관리자가 서브넷 관리를 위해 만든 전체로 ping보내는 명령어를 공격자가 페킷의 SIP를 희생자의 ip로 설정해서 여러번(매우 많이) 실행하는것

  • Packet sniffing(MAC Flooding)

    • 허브, 스위치 나오면서 나온거
    • 허브는 연결된 모든 노드에게 보내고 스위치가 목적지한테만 보냄(이건 매핑 테이블을 통해 가능 이게 꽉차면 기존걸 지워야하고 매핑 테이블에 저장되어 있지 않으면 브로드케스트 해서 허브랑 결국 똑같아짐)

    • 공격자가 가짜 MAC주소를 만들어 저장하게 만드는 공격(그 후엔 허브처럼 변해서 페킷 훔치기 쉬워짐

• TCP/IP level

  • IP spoofing

    • 출발지 ip(SIP)를 속이는 것(raw socket프로그래밍으로 속이기가 가능)
    • ip spoofing 때문에 dos, ddos, session hijacking이 가능
    • ingress/egress 필터로 막을 수 있음
      • egress가 밖으로 나가는 페킷을 관리하는거(굿 시티즌 필요해서 달성하기 어려움)

  • Session hijacking

    • ip 스푸핑에서는 공격자가 페킷을 가로채는것 까지는 불가능한데 여기선 가능함
    • 세션을 가로채서 공격자가 희생자인척 하고 서버에서 페킷을 보내는것
    • TCP 세션을 가로채려면 ISN을 알아야함(ip,port,key,time 들어감)
    • 세션 가로채서 sip에 희생자 ip를 넣어서 ip스푸핑 공격도 들어가는거고 희생자가 서버에게 페킷을 보내지 못하게 희생자를 다운 시키기고 싶으니까dos,ddos공격도 사용함

  • Injecting false routing information

    • 공격자가 라우터를 점령해서 라우팅 테이블을 망치는 공격
    • 요즘엔 라우터에 key값을 사용해서 메세지랑 같이 해쉬해서 보내면서 방어함

  • Port scan

    • 열려있는 포트(열려있으면 취약하니까)를 찾는 공격
    • TCP연결에서 사용하는 flag비트를 특정하게 설정하면 그에따른 응답이 오는데 이걸 이용

• Firewall

  • 얘는 기본적으로 모든 페킷을 다 열어본 뒤 기준에 맞는거만 통과시키거나 방어하는거임
  • Stateful/Stateless
    • 연결의 상태를 기억하냐 안하냐의 차이, 일반적으로 stateful이 처리가 빠름, 보안적 측면에서는 떨어질수도 있음
    • stateful : 한 번의 허용된 연결이나 패킷이 있다면 해당 연결에서 발생하는 페킷도 허용하는 방식
  • DMZ : 서비스를 위한 웹서버와 보안이 중요한 DB를 방화벽의 다른 쪽에 두는 방식(웹서버가 DMZ에 있음)
    • 웹서버에서 DB로 가는건 서비스를 위해 필수적인데 위처럼 해두고 DB로 가는쪽은 PORT를 하나만 열어두면 보안이 쉬움

• High Availability

  • 여기서 L4/L7 스위치 나옴
  • 방화벽이 여러개일때 스위치가 알맞은 방화벽으로 보내야함(ip,port로 XOR사용 xor은 순서 바뀌어도 동일해서 오고갈때 같은 방화벽 사용 가능)
  • 
  • 최근에는 위 방법으로 꼭 같은 방화벽 통과 아내도 되게함(커널 단계에서의 세션 동기화라고함)
  • 여기서 라우터 vs 스위치도 나옴
    • 스위치는 MAC주소 기반이고 라우터가 IP주소 기반(그래서 라우터를 통한 VRRP 로드 밸런싱이 나옴)
  • VRRP
    • 모든 라우터가 공통된 가상 IP를 가짐
    • 마스터가 먼저 가상 IP를 사용, 마스터는 주기적으로 슬레이브에게 자기가 살아있다는 메세지를 보냄
    • 살아있다는 메세지가 안오면 슬레이브가 마스터가 죽었다고 판단하고 가상 IP를 사용(마스터가 되는 것), 가용성 달성
      • 일반적으로 ping을 사용 db에서는 heartbeat
    • 당연히 슬레이브 중 그 다음 누가 마스터가 될지 선정하는 정책이 필요 이걸 Election process라고함)
    • 슬레이브가 쉬는게 맘에 만들면 가상 ip를 여러개 사용할 수 있음 서로가 서로의 마스터이자 슬레이브가 되는 것

  • 어떤 지점이 고장났을때 전체 서비스가 실행이 불가능 해지면 그 지점을 single point of failure라고 부름

    • 그걸 제거하기 위해 방화벽, db, 스위치 라우터 다 2개 이상씩두었는데 911때 그걸 한번에 날려버려서 아얘 똑같이 다른 지역에 2개를 만들어버림 -> Disaster Recovery Center, DR센터라고 부름
    • GSLB -> DR센터 중에서 한가한 서버의 주소를 리턴해줌 그때 TTL도 같이 보냄(TTL이 길면 성능 좋고 짧으면 고장에 잘 대응)

  • 가용성 확률 계산해보기

• Intrusion Detection System

  • 이상탐지 시스템,
  • 위치, 알고리즘 각각 2개씩 총 4개의 조합이 있음
    • 위치 : network, host
    • 알고리즘 : signature, anomaly-based
    • network, signature를 일반적으로 많이 사용
  • True/False, Positive/Negative 구분할줄 알아야함
  • Snort
    • 
• DDOS
  • botnet이라는 개념이랑 같이 나옴
    • bot master(공격자), bots(감염 피시), C&C서버(bot들을 관리하는 pc)
  • C&C서버에 bot들이 접속하게 해야함, 똑같은 도메인 네임 생성 알고리즘을 심어서 실행, 주기적으로 바꿈(추적이 어려워짐)
• Intrusion Prevention System
  • IDS + FW(방화벽)의 개념
    • ISN를 중간에서 체크해서 ip spoofing을 하는지 안하는지 검사

Web

• WEB Overview

  • http나옴, stateless다
  • Request, Reply 메세지 정도 보기

• Web Shell

  • exe파일을(주로 shell을 실행하는 파일)을 서버가 저장하게 만듬(자소서 같은걸로 위장)
  • 공격자가 브라우저를 통해 위의 exe파일에 접속해 실행하면 공격 성공(위치를 다 알아야해서 어려움)
  • 디렉토리에 실행권한을 제거하거나 확장자명, 파일크기를 제한하는식으로 막아야함

• Cookie

  • 클라이언트에 저장, 서버에 같이 내면 쿠키를 사용하여 이전 연결의 정보를 사용가능함(이게 http에 state를 부여하는 역할)
  • 공격자가 쿠키를 가로채면 문제가 생기니까 쿠키의 원래 내용 value와 key를 concat해 해쉬를 씌워 T를 만들고 value에 T를 붙여 같이 보냄

• Session management

  • 세션 토큰을 사용해서 사용자의 세션을 유지,관리 하는것
  • 위의 쿠키도 세션 토큰 중 하나고 여러 가지가 있음
  • 여기서 referer라는게 나옴(tcp해더에 클라이언트의 이전 접속 url을 추가해서 보낸것)
    • 세션 토큰은 아니고 비슷한 역할 가능
    • 서버는 이게 갑자기 바뀌는지 확인 가능하지만 공격자는 역으로 이걸로 클라이언트인척 가능

• XSS(Cross Site Scripting)

  • 피해자가 클라이언트
  • Persistent(stored), non Persistent(reflected)가 있음
    • Persistent는 공격자가 글을 작성(서버에 저장)피해자가 글을 누르면 글에 포함된 악성 코드가 자동 실행
    • Non, persisten, 검색할때 악성 코드를 주소에 넣어서 검색하게 만들면 그 코드가 바로 실행될 수 있음
  • HTML sanitization해서 막아야함
  • Sanitization : 입력부분에서 유해한 부분을 제거하거나 미리 지정한 분자로 치환하게 하는 방법

• CSRF

  • 피해자가 서버, 주로 위의 XSS와 같이 많이 사용함
  • XSS로 피해자한테 비밀번호 변경 명령을 실행한다고 가정
    • 비밀번호가 공격자가 지정한 것으로 바뀜
    • 공격자가 피해자의 id, 바꾼 비밀번호로 서버에 접속(만약 권한이 높은 피해자였다면 피해가 심각)
    • 만약 사이트 자체가 비밀번호를 바꿀때 기존 비밀번호도 입력하는 형태였다면 위 명령어에 기존 비밀번호도 들어가야하는 것이라 보안이 좋아짐

• SQL Injection

  • 웹에서 로그인, 회원가입은 사용자가 빈칸에 입력한 값을 가지고 SQL쿼리문을 만들어 실행하는 건데
  • 빈칸에 악의적인 SQL명령어를 입력하면 이게 실행 되는것
  • SQL에서 --뒤가 가 주석처리되는걸 이용함
  • 이것도 Sanitization으로 막을 수 있다

• Insecure Direct Object Reference

  • url주소를 찍어서 맞춰서 링크를 통해 접속하지 않는 것
  • 관리자 페이지 접속을 위해 admin, manager등의 단어를 많이 사용함, 그래서 관리자 페이지 접속할때는 특정 ip만 허락하는등의 정책 필요

• Access Control for Administration

  • 위에거랑 이어지는 내용, 관리자 권한에 대해서 잘 관리해라 그런 내용임

• Vulnerability Scanner

  • 웹의 취약점을 파악해주는 도구, 취약한 공격방법을 알려줌(양날의 검)
  • 수업에서는 쇼단으로 예시 보여줌

단어정리

• OWSAP : 년마다 이슈였던 공격방식 순위 메기는 곳

• SBOM(Software Bill of Materials) : 소프트웨어 만들때 구성요소를 정리해야한다

• Dark Web, Tor, Onion Routing : Dark Web이 안좋은 사이트, 접속할때 추적을 피하기위해 p2p를 사용해 목적지 ip를 양파껍질처럼 계속 추가하는게 onion routing, 이걸 사용하기위해 쓰는 특별한 브라우저가 Tor

• FDS(Fraud Detection System) : 신용카드 같은게 사용자가 평소 잘 안가는 곳에서 결제되면 의심하는 것

• IT, ICT vs OT CPS(Cyber-Physical System). 이란 핵발전소 스턱스넷(stuxnet) : OT CPS가 물리적으로 관리하는 개념, 완벽한줄 알았는데 이란 저기서 USB꽂아버려서 거기있던 악성코드 감염됨

• APT(Advanced Persistent Attack) : 긴 시간을 가지고 집요하게 공격하는 방식

• 사회공학적 기법 : 사회적으로 사람을 이용하는 것

• spear phising : 피싱 공격, 이메일이나 문자등

• MITRE : MITRE회사가 만든 취약점이나 보안을 평가하는 프레임워크임

• BCP (Business Contingency Plan) : 기업의 지속적인 운영을 보장하며 재난이나 위기 상황에서의 영향을 최소화하는 것

• 제로트러스트 : 기존 보안은 외부에서 내부로 오는 것을 위주로 차단하고 했는데 이거는 내부에 있는 애들도 다 안믿어서 뭐 할때마다 검사하고 인증하는 거임

• 제로데이 취약점 : 아직 방어방법이나 대응방안이 없는 취약점

• 공급망 공격 : 공급망이 여러 회사를 거치니까 그 중에 하나를 공격하면 공급망 전체가 망가진다는 개념

• SOAR(Security Orchestration, Automation and Response) : 보안 사건이 발생하면 기록하고, 이를 활용해 대응 프로세스를 자동화해 실행하자는 것

String Matching

• 
• 단어를 찾아라

Naive Algorithm

• 
• 한칸씩 밀면서 모든 글자를 다 비교함 O(MN)
  • 여기서 패턴 길이만큼 다 비교안하고 다른글자나오면 다음 위치로 미는 식으로 할 수 있음
• 
• 패턴의 길이와 j가 같아지면 종료

• 위에서 한칸씩 비교하다 다른 글자가 나오면 시작위치를 뒤로 돌리는걸 roll-back이라고 하는데 이게 없어야 시간을 줄일 수 있음
• 

DFA(Deterministic Finite State Automaton)

• 
• 하나의 state에서 특정 문자가 왔을때 갈수 있는 다른 state가 단 1개로 명확하기 때문에 Deterministic이라 함
• 
• 0에서 A가오면 1로, 6에서 B가오면 4번으로
• 
• 
• 선이 없으면 무조건 처음으로 가는식으로 그림 간소화
• 이거는 DFA가 만들어졌다고 가정한것, 만들어져만 있으면 O(N), roll-back이없음
• 
• DFA 사진 한장으로 요약

DFA Construction

• 위는 DFA가 만들어졌다고 가정 후 한것, DFA는 어떻게 만들것인가
• 
• 미스매치가 일어난 지점(j라고하면)의 문자를 패턴의 1번부터 j-1까지 갔을때의 스태이트를 j가 왔을때의 위치임
• 
• 
• 스테이트에서 미스매치가 일어나면 1번 문자(BABA부터)를 스테이트 0번부터 돌려서 최종적으로 위치한 곳(X)에서 미스매치가 일어난 문자를 한번더 한 state가됨
• X위치(BABA해서 위치한 곳)을 매번 구하는게 아님
• 6번에서 미스매치되면 X의 위치는 0번 스테이트에서 BABA대신 BABAC를 한것 이전 X에서 한번만 더하면 됨
• 
• X의 갱신은 이전 X에서 패턴의 그다음 글자 하나를 추가
• 일단 제일 왼쪽 초기화, 다음 줄은 이전 x번 줄을 복사(미스매치) 그 후 매칭되는 알파벳 갱신, x를 이전 x값에서 이번에 매칭된 알파벳을 넣는것으로 갱신

KMP

• prefix, suffix
  • 
  • NULL과 전체 단어도 접두사,접미사에 해당됨
• 미스매치 후에 그 다음 시작위치를 그냥 틀린위치부터 하자는 아이디어
  • 
• 텍스트의 시작을 트린위치에서 하는거고 추가로 패턴매칭은 처음부터 안하고 패턴의 시작과, 이전에 매칭했던 곳에서 같은 부분은 건너띔
  • 
  • 매칭하다 틀린 부분의 바로 앞을 기준으로 짜르고, 그것의 prefix, suffix가 겹치는 부분만큼 부터 다시 시작(0칸이나, 전체는 뺴고)
  • 
  • 
  • 
  • 틀리면 텍스트는 롤백을 맥시멈 오버랩부터 하지만 매칭은 틀린곳부터 해도됨, 패턴은 맥시멈 오버롤의 길이의 다음 위치부터 매칭하면 됨
  • fail펑션
    • 패턴에서 실패한 위치에 따라 멕시멈 오버랩을 구하는 것
    • 
    • 
    • 이거 할줄알기
  • 

Websecurity(1)

http, web

• web : TCP에서 동작
  • HTTP로 동작한다
    • 
  • HTTP는 stateless 프로토콜임
    • http로 페이지를 하나보고 다른 페이지로 갈때 하이퍼링크를 누르면 새로운 http를 읽어들어야 함(행동행동이 연관이 없어서 stateless)
  • stateless는 웹 쇼핑 같은 기능을 구현이 불가능해서 http에 쿠키가 세션을 붙여서 사용하는데 공격자가 이 쿠키, 세션을 훔치는 공격이 존재함
• 

Web shell

• MITRE : 전세계의 취약점을 공통된 이름으로 정리하는 단체 CWE-434로 web shell을 구분지음
• web shell은 웹 서버의 exe파일을 클라이언트가 접속할때 발생
  • 공격자가 올린 파일(지원서로 위장한 exe 파일 등)을 서버가 지원서로 착각해 디렉토리에 저장하고 공격자가 서버의 디렉토리에 접속해서 실행시키는 공격
  • exe파일을 보통 shell실행 코드로 보내서 web shell공격이라고 부름(shell이 실행되면 취약하기 떄문)
• countermeasure
  • 파일을 업로드 하지 못하게 하면 차단되지만 업로드를 해야만 하는 경우 확장자명이나 파일 크기의 제한을 두는 방법으로 방어
  • 디렉토리의 실행권한을 제거

Cookie

• stateless인 http를 state를 유지하고 싶어서 만듬(보안을 고려하지 않았음)
• 보안을 고려한 쿠키 생성방법
  • 쿠키에 integrity체크를 위한 T(태그)를 붙임
  • 서버에서 쿠키를 생성할때 키 k와 원래 쿠키의 내용인 value를 concat후 해쉬, 이걸 T로 사용
  • 

Session management

• 이것도 http의 state를 부여하고 싶어서 만듬
• 
• 세션을 만들고 페킷을 주고 받을때 위에서 referer는 클라이언트가 서버로 GET명령을 실행할때 이전에 접속했던 사이트 주소를 같이 보내질수 있다(보안측면에서 안좋을 수 있음)
• referer필드로 해커가 클라이언트인척 하는지 체크할 수도 있다는 측면도 있음

• Session hijecking
  • http레벨에서의 하이제킹
  • 공격자가 정상적인 클라이언트와 서버의 통신 과정에서 쿠키값이나 세션정보를 빼와 클라이언트인척 서버에 명령어를 내리고 서버가 응답해주는 것
• 
• SID를 만들때 규칙적으로 하지말고, 서버만아는 k로 해쉬 만들기, http는 application단계인데 ip주소도 사용해서 보안을 강화할수도 있음

XSS(Cross-Site-Scripting)

• 피해자가 클라이언트
• CEW-79라고 이름 지어져있음
• 어떤 입력이 들어왔을때 입력내용중 공격내용이 들어오면 무시해줘야함 -> 이게 Newtralization
• 데이터는 보통 data와 control로 나누는데 100+100을 실행한다고 하면 100,100을 data +를 control로 보는 것, write,read등의 명령어도 control임
• user의 인풋중 control 부분을 잘 처리하지(newtralization)하지 못하게 하는것이 XSS
• code injection이라고도 볼 수 있음

• 정상적이면 클라이언트가 웹 서버에 접속하면 alert등의 control명령어가 실행됨
• Persistent XSS
  • 공격자가 웹 서버에 악의적인 control 명령어(쿠키 정보를 어디로 보내라 등의)가 들어간 글을 작성함
  • 
  • 유저가 게시글을 읽으면 명령어가 실행됨
  • 
• 게시글이 서버에 저장되어있다해서 Persistent라고 함

• Non-persistent XSS(reflected xss)
  • 주로 URL 파라미터(특히 GET 방식)에 스크립트를 넣어 서버에 저장하지 않고 그 즉시 스크립트를 만드는 방식 공격자가 HTTP 요청에 악성 콘텐츠를 주입하면 그 결과가 사용자에게 반사되는 형태

• 
• sanitization
  • 입력부분에서 유해한 부분을 거부하거나 미리 지정한 문자로 치환하는 방법
• 그냥 script를 전부 사용하지 못하게 할수도있음(서비스보단 아주 강한 보안이 필요할경우)

Websecurity(2)

CSRF(Cross-Site Request Forgery)

• one-click attack or sessin riding이라고도 부름
• 피해자가 서버임
• 공격자가 서버가 신뢰하는 유저가 명령어를 서버에게 실행하도록 함

• 클라이언트가 비밀번호를 바꾸는 명령어를 활용한 공격
  • 이전 비밀번호를 입력하지 않는 경우 -> CSRF에 취약
  • 공격자가 일단 쿠키나 세션정보를 탈취했다고 가정(그래서 일반적으로 CSRF 이전에 XSS로 이것을 달성함)
    • 이 쿠키를 사용해서 공격해도되고 그냥 XSS로 바로 실행하게도 함
  • 공격자가 클라이언트가 악성 명령어를 서버에게 실행하게 하면 서버는 이것을 믿어 실행해주면서 문제가 발생
  • 이때 명령어를 비밀번호 변경 명령어를 실행하는 것
    • 
    • 위와같은 멸령어에 기존 명령어의 입력이 들어가지 않으면 위같은 쿼리를 예측당하기 쉬워 취약한거임
  • 클라이언트가 서버 관리자라고 가정하면 매우 치명적이게 됨 그 비밀번호를 공격자가 알게되기 때문

SQL Injection

• SQL 쿼리에 입력되는 데이터의 Sanitize를 실패한 것
• 이것도 code injection
• Injection : 데이터가 아닌 어떤 control명령어를 강제로 주입하는 형태

• SQL명령어
• 
• 
• 
• 웹에서 빈칸에 입력하는 내용이 sql쿼리문에 들어가서 실행됨
• 저 칸에 다른 어떤 명령어가 실행되도록 입력하면 sql쿼리에서 변수 대신 명령어 값이 들어가고 이상한 명령어가 실행되게됨
• id또는 password에 or '1=1' --를 입력한 경우?
  • 
  • sql에서 --는 주석임
  • 저러면 id,password에 상관없이 모든 id,password를 가져오게됨
• select말고 다른 명령어를 사용하면 더 치명적일 수 있음
  • 
• Countermeasure
  • ','',/,; 등의 특수문자를 사용 못하게
  • 에러 메시지를 보여주지 말기
  • 권한부여를 제한적으로

Insecure Direct Object Reference

• 
• 링크를 눌러서 정상적으로 접근해야 하는데 url을 찍어서 맞추는것
• 
• 이런식으로 많이 시도함
• 그래서 admin, manager권한을 접속할때 잘 관리해야함
  • 
  • 특정 ip에서 접근 가능하게 하는식으로

Vulnerability Scanner

• 웹의 취약점을 파악해주는 도구
• 취약한 공격방법을 알려줌

OWSAP

단어

• SBOM
  • 개발자들은 소프트웨어의 각 부분에 대한 목록을 작성하여 소프트웨어 부품 목록을 구성하고, 이를 통해 보안 취약점을 식별하고 관리할 수 있습니다.
• Dark Web, Tor, Onion Routing
  • onion routing -> Dark web으로 가기위한 페킷에 p2p를 계속 이어 목적지 ip를 계속 쌓는 것 이를 위해 특별한 브라우저가 필요한데 이게 Tor
• FDS
  • 신용카드 정보등이 엉뚱한 곳에서 결제가 되는 등을 추적하는것
• IT,ICT vs OT CPS
  • OT CPS : 인터넷 환경을 끊고 물리적 프로세스로 제어
  • 인터넷이 끊어서 보안이 완벽하다 생각했지만 이란 핵발전소가 USB로 악성코드 감염이 된 사례가 있음
• APT
  • 긴 시간을 가지고 집요하게 공격하는 방식
• 사회공학적 기법
  • 사회적으로 사람을 이용하는 것
• spear phising
  • 피싱 공격, 이메일이나 문자등
• MITRE
  • 공격의 단계를 체계를 만들어 테이블로 만듬, 보안 대첵을 개발할때 사용
• BCP
  • 백업 센터
• 제로데이 취약점
  • 아직 대첵이 발견되지 않은 취약점
• 제로트러스트
  • 서버에서 접근제어 정책을 두는것
• SOAR(Security Orchestration, Automation and Response)
  • 보안 사건이 발생하면 기록을 해두고 이를 활용해 대응 프로세스를 자동으로 실행하도록 하는 것

• 
• 특징
  • 주요특징은 사용자 상호작용을 데이터 추상화 및 데이터 처리와 분리하는 것
  • 데이터 추상화와 프레젠테이션 간의 느슨한 결합
  • 느슨한 결합은 명시적인 메서드 호출이나 암시적인 등록, 알림 메서드 호출과 같은 방식으로 구현

• 
• interaction-oriented 아키텍처의 주요 2가지 스타일
  • MVC, PAC
  • 둘다 상호작용 및 사용자 작업이 있는 대화형 응용 프로그램에 사용
  • 제어 흐름과 조직에서 차이가 있음
  • PAC
    • 에이전트 기반의 계층 구조 아키텍처
  • MVC
    • 계층 구조가 없으며 세 모듈이 모두 연결되어 있는 구조

Principal Component Analysis

• 주 성분 분석
  • 데이터의 분포를 결정하는 핵심 성분을 찾는 것
  • 
  • 다차원 데이터에서 핵심성분을 찾아 1차원으로 표현할 수 있음
  • 
  • 공의 위치를 결정하는 주 성분은 스프링의 힘, 1차원으로 표현
• 주성분 분석은 수학적으로 분산을 최대화하면서 서로 직교하는 새로운 축을 찾는 것
  • 

• 차원 축소 방법
  • 
• 방법 1)
  • 아무 차원이나 지우기
  • 
  • 
  • 위 중에서는 2번째가 분산이 더 커서 좋다
• 방법 2)
  • 새로운 축을 찾기
  • 

• 주성분 찾기
• 
• 주황색이 x
• 주황색 데이터를 벡터 A를 사용해 선형변환 시킨 것(Y = XA)
  • 이때 벡터 A를 찾아야 하는 것
• Y = XA의 주성분은 A의 고유벡터
  • Av = λv를 만족하는 v가 고유벡터이고 λ는 고윳값이라 함
  • 
• 1) 일단 Y에대한 A를 구해야 함
  • Y의 공분산 행렬을 사용
• 2) A의 고유벡터 구하기
  • 

• 주성으로 데이터 표현
• pc1, pc2를 찾고 2개르 축으로 사용
  • 

• 최종 주성분
• 
• pca를 더 찾을수록 일반적으로 분산이 줄어듬
• 0에 수렴하기 전까지의 pca까지를 주성분으로 사용

Deep Model Compression

Knowledge Distillation(지식 증류)

• 메모리, 전력을 효율적으로 사용하면서 성능을 유지하기 위해 나온 것이 Model compression

  • 

• 레이어가 더 많은 네트워크에서 적은 쪽으로 정보를 내줌(일반적으로 레이어가 많으면 성능이 좋다)

  • 
  • Teacher의 정보를 활용해 Student를 학습

• 모델을 경량화

• 처음엔 teacher의 마지막 아웃풋을 student에게 전달하는 방법으로 구현했었음

• 

  • 위는 소프트맥스를 합은 항상 1이 되면서(확률이기 때문) T로 나누어 y값의 차이를 줄여 평평하게 만듦
    • teacher의 아웃풋을 평평하게 만들어 정답값으로 쓰는 것
    • teacher에서 강아지라고 100% 확인했지만 강아지의 특성 중 늑대와 비슷하거나 털이 있는 등의 특성을 사용하기 위해 T를 사용하는 것
    • T의 값이 클수록 평평해짐(평평할수록 다른 특성을 더 많이 보겠다는 의미)

• attention map

  • 정보를 넘겨줄때 픽셀의 값을 모두 더해서 한장으로 만들어서 넘겨주기
  • 
  • 위에서 가로세로 각 픽셀마다 C장 만큼 절대값으로 다 더해서 같은 가로세로 크기의 attention map을 만들어서 넘겨줌
  • 중간중간 피처를 넘겨주는 의미
  • 

• Factor Transfer

  • teacher, student의 레이어, 피처의 크기와 개수가 다른데 teacher만의 결과를 넘겨주는것은 알맞지 않다고 생각하여 나온 방법
  • 
  • 각각의 결과를 모듈을 통과시켜 크기를 중여 factor로 추출
  • 
  • teacher의 결과를 압축후 다시 복원했을때 압축전과 복원 후의 결과가 비슷하면 할수록 가운데의 크기가 가장 작은 부분은 원본의 특징을 가장 잘 표현했다고 말할 수 있음
  • 이것은 teacher의 결과를 잘 표현하면서 크기를 잘 줄여준것임
  • 
  • student도 학습후 결과를 factor로 압축하고 teacher와 student의 factor의 차이를 줄여서 사용
  • 
  • FT의 성능
    • 
    • k : 압축 작으면 압축을 더 많이 한것(압축을 많이한다는 것은 factor의 크기가 작아지는 것)
    • ST는 teacher를 활용하지 않는 결과
    • 일반적으로 압축을 많이하고 teacher의 정보를 활용한것이 성능이 좋음

Quantization(양자화)

• 연속적인 신호를 디지털화 하는 것
  • 
  • Full precision : 32비트 체제라하면 32비트를 모두 사용 하는 것
  • Low Precision : 32비트 중 8비트정도만 사용한다하면 히스토그램에서 막대의 개수가 2^32에서 2^8로 줄어드는 것
• 연산량을 줄임
• 크게 QAT, PTQ로 나눔
  • QAT(Quantization Aware Training)
    • 최대 성능(FP))를 학습하고 난 후 양자화된 데이터를 가지고 더 학습함
  • PTQ(Post-Training Quantization)
    • FP를 학습하고 난 후 그 결과를 활용해 양자화하는 방법
  • FP는 무조건 하고 그 후에 둘 중 하나를 사용함
    • 
• QAT가 성능이 좋긴하지만 학습하는데 시간도 오래걸리고 어려움 PTQ는 학습없이 한번의 알고리즘을 돌리면 사용가능해서 빠름(성능은 떨어질 수 있음)
• PSGD
  • 처음부터 정밀도가 낮은 모양으로 학습을 시키는것
  • 
  • 
  • W를 양자화시킬때 막대가 노란색 점에 있어야함
  • 위에서 별표가 W가 양자화된 위치라 할때 노란점 근처에 있으면 양자화가 잘 되었기 떄문에 업데이트시 움직이지 않게 하고 노란점에서 멀면 양자화가 잘 안된 것이라 판단해 다음 업데이트시 많이 움직이게 만듬
  • 
  • S(X)가 노란점과의 거리, 밑의 식에서 거리만큼 곱해져서 움직이게 됨
  • 
  • 왼쪽그림은 둘다 FP임 2개를 양자화 시켜 비트수를 줄인것이 오른쪽
    • 처음 학습할떄부터 양자화를 고려하면 에러가 줄어듬
    • 처음부터 몇비트로 양자화할지 알아야 가능한 방법이라는 단점이 있음(노란점의 개수를 정해줘야 하기 떄문)
  • 
  • 양자화 할때 여러 값을 0으로 만든것인데 그럼에도 성능이 나온다면 pruning효과까지 얻은것
  • PSGD는 처음부터 양자화후의 모습과 유사하게 학습하기 때문에 학습 완료 후 바로 양자화가 쉬움(타켓 비트를 가지고 학습하기 떄문에 타겟 비트로 양자화하면 성능이 잘 나옴)
    • 
    • On-the-fly quantization(타겟 비트로 한번에 양자화)해도 성능이 잘 나옴
  • 
  • 처음 학습시 양자화에 친숙하게 학습하기 때문에 PTQ를 섞어써도 성능이 잘 나옴

Pruning

• 중요하지 않은 웨이트를 지우는 것(0으로 만드는 것)
• 
• Unstructed pruning : 필터 안에서 웨이트를 지우는 것
• Structed pruning : 여러개의 필터중 특정 필터를 통채로 날림
• 일반적으로 절대값의 크기가 작은 것을 지움
  • 방법은 여러가지가 있다
• One-shot or Iterative
  • 한번에 원하는 만큼 크기를 줄이거나 점차적으로 하는것에 따라 나누어짐
  • Iterative는 조금씩 줄이면서 중간중간 학습을 다시하기 때문에 결과가 한번에 줄이는것과 달라짐(일반적으로 성능이 좋음)
• 
• 햇을 씌운게 프루닝을 하고난 후의 결과
  • 갱신할때 프루닝을 안한 것을 프루닝을 한걸로 갱신하는게 말이 안되기 때문에 채인룰을 사용한 것
  • 파란 동그라미는 마스크를 의미함(w햇이 wx마스크인데 w햇에 대해 미분했기 때문)
    • 실제 마스크값을 곱하면 마스크가 0이면 업데이트가 전혀 안됨
    • 
    • 그냥 마스크값을 1로 만들자는 방법(Dynamic Prining)
• 
• 위에서 다 1로 만든것이 파란색(dpf)
  • 성능이 요동치게 됨
• 마스크가 1일때 실제로 업데이트 하는것은 트루 업데이트(문제가 안됨)
• 그런데 마스크가 0인데 실제로 업데이트 한 경우는?
  • 
  • 뒤의 식에서 M은 마스크의 값 0이거나 1, 마스크가 1이면 마스크를 씌운 후 값인 w햇을 업데이트하고 마스크가 0이면 그냥 w를 업데이트함
  • dpf를 개선한것(dpf 위의 파란색은 뒤의 식 부분에서 마스크가 0이어도 w햇을 업데이트 한거임)
  • 

• undirected(방형성이 없음)
  • 보통 일반적인 그래프
  • 
  • V 2개에 E 1개
  • 각각을 집합으로 표현 {}
• directed(방향성이 있음)
  • 
  • 엣지를 집합으로 표현하지 않았음 ()

특성

• complte 그래프
  • 모든 V쌍에 대해 엣지가 다 연결됨
    • V가 n개면 E는 n(n-1)/2개
• 인접
  • v,w를 잇는 엣지가 있으면 v,w는 인접하다고 할 수 있고 vAw로 표시한다(adjacency)
• 경로 Path
  • 중간 경로가 distinct(중복이 없는)한 엣지의 집합
• connected
  • 그래프 내에서 어떤 두 V를 잡더라도 경로가 존재해야 connected하다고 함
• cycle
  • 시작과 끝 V가 같은 경로
  • acyclic -> 사이클이 없는 것
  • tree구조는 acyclic하면서 connected함
    • 
• 분할
  • 그래프가 connected하지 않으면 여러개의 서브 그래프로 분할 할 수 있음
  • 분할할때는 서브그래프가 최대로 connected하게 해야함
    • 
    • 이건 3개로 분할가능
  • weight
    • 엣지에 가중치를 부여 가능

그래프의 저장

• 그래프의 관계를 저장하는 방법
• undirected 그래프는 대칭적인 매트릭스로 표현됨
  • 
• linked list로도 가능
  • 
  • 계속 연결시키는건 아니고
  • 연결된 노드를 다 연결시킨 것
• Weighted Diagram
  • 
  • linked list에 필드 1개를 추가
    • 

DFS, BFS

• 
• bfs는 큐를 사용(iterative)
• dfs는 스택(iterative), 재귀 둘다 가능
  • ABFEIGCH는 스택사용의 결과
• DFS로 tree를 만들 수 있음
  • 
  • 만약 undirected그래프면 cross, descendant엣지가 없음

Biconnected component

• articulation point : 제거하면 connected하지 않게 되는 지점
• 바이커넥티드는 articulation point가 없는 그래프
• 
• a에서 articulation point는 f,e,b임

K Nearest Neighbors

• kNN : 가장 가까운 k개의 점
  • 
• 가까운 점의 특성을 알고있을때 이를 활용해 새로운 점의 특성을 파악하는 방법임
  • 

• 특징
  • 데이터 기반 분석
  • 데이터 분포를 가정하지 않음
    • 데이터가 가까이 있으면 비슷할 것이다라고만 가정함
  • 회귀문제, 분류문제등에 적용 가능
    • 
    • 
• 1등이 여러개일 경우
  • 
• 데이터가 균일하지 않으면
  • 

• 적절한 k값 찾기
  • 
  • k를 1부터 증가시켜가면서 가장 오류가 적은 k값 선택

• 거리(가까운 점에서 사용할 거리는 어떻게 구하는지)
  • 

• 장,단점
  • 

• 인덱싱
  • 먼저 그룹을 지어놓고 가까운 점을 그룹내에서만 찾는 것
• KD-Tree
  • 
• VP-Tree
  • 
• KNN-Graph
  • 

Union-Find

• 자료구조중 하나

• n개의 set를 가지고있음
  • 각각은공집합이 없음
• 초기에는 set이 모두 원소가 1개인 집합임
• union과 find연산을 제공
• 
• 각 set에서는 parent로가는 방향만 존재함
  • root에서는 자기자신에게 감
  • root가 각 set의 대표이고 각 set은 트리로 표현
• 
• 위 트리를 배열로 표현할떄 각 노드는 자신의 parent인덱스를 가지고 있으면 됨

• 기능
  • 
• find -> 노드의 루트찾기
  • same_set -> 루트가 같아야 같은 set
  • 
• union -> union(1,2)이면 1의 루트를 2의 루트로 바꾸는 것
• 
• 
• n개의 싱글톤 셋 만들기
• 

• union과정에서 트리의 높이가 계속 높아지는 문제가 생길 수 있음(이러면 find에 시간이 오래걸림)
  • 
• 이때 키가 작은 트리가 높은 트리에 붙게 해주면서 해결(개선1)
  • 
  • size를 추가해서 코딩
    • 
• worst
  • 
  • 노드의 개수가 2배 늘어날떄마다 높이가 1증가(logn)
• 연산시간 종합
  • 
• 처음 루트를 찾았을때 parent를 루트로 변경시키는 방법으로 find의 연산시간을 줄일 수 있음(개선2), Path Compression
  • 
  • 
  • 
• Path Compression2
  • parents를 grand parents로 만들어주는 과정의 반복으로 할 수도 있음(한번 할때마다 반씩 줄어듬)
  • 
• log*n : 로그를 몇번 취해야 1보다 작아지는지
  • 
• 최종 정리
  • 
  • m번의 union/find를 할때의 시간

Greedy Approach

• 일반적으로 여러개의 원소 집합에서 부분집합이 해답일때 부분집합을 구할때 사용함
• 해답을 집합 g라할때 처음엔 공집합, 주어진 원소에서 g에 포함될 원소를 차례로 1개씩 선택
  • 원소 선택과정에서 전후 관계를 고려하지 않음

동전교환

• 1,5,10,50,100으로 378원을 교환해주기
• 
• 동전교환에서는 값이 큰 동전부터 선택
• 문제점
  • 
  • 일반적인 경우는 DP로 품

가방 채우기

• 
• 단위 부피당 가격이 높은 치즈부터 채움
• 

• 치즈를 자를 수 없는 경우는?
• 
• 이 경우에는 DP로 풀어야 함

회의실 배정 문제

• 
• 
• 가장 빨리 끝나는 회의부터 선택
• 
• 이때 그 다음 회의를 고를때는 시작시간이 이전 회의의 종료시간보다는 커야함

Minimum Spanning Trees

• 모든 V를 포함하면서 connected인 트리
• 그중 웨이트의 합이 가장 작은것을 구하는 것임
• 
• 1,2는 사이클이 있기 떄문에 트리가 아님
• 3,4둘다 spanning tree인데 웨이트가 더 작은 4가 minimum spanning tree
• Prim, Kruskal 2개의 알고리즘이 있음

Kruskal`s algorithm

MST를 찾는것

• 웨이트가 작은 엣지순서로 정렬
  • 
  • 웨이트가 작은 엣지부터 추가함
  • 엣지를 추가해서 사이클이 생기면 추가 안함
  • v가 5개면 엣지 4개를 구하면 종료임
  • 
  • 엣지를 추가할때마다 사이클이 만들어지는데 검사하는게 중요
    • 이걸 유니온 파인드로 검사함
    • 새로 추가할 엣지에 연결될 P와Q가 유니온 파인드의 같은 트리에 속하면 사이클이 생김, 다를떄만 엣지를 추가하고 UF에서 merge함

Prim`s Algorithm

• 한 버텍스에서 시작(크루스칼)은 엣지를 추가하는 방식
• 전체 버텍스를 y라함
• V를 하나 고르고 V와 y-v를 잇는 엣지 중 가장 웨이트가 작은 엣지를 고르고 이은 버텍스를 V에 추가
• 위 과정을 반복
  • 
• 엣지를 선택할때 최소값만 사용하기 때문에 각각의 V는 자신과 이어준 엣지중 가장 웨이트가 작은 엣지만 관리하면 됨
• V를 추가하면서 V에 연결된 노드도 갱신 연결된 노드는 nearest, 거리를 distance로 관리함
  • 
  • 여기서 거리가 무한대여도 제일 가까운 노드를 1로 초기화 하는게 중요
  • 
  • 

Dijkstra`s Algorithm

• 가장 짧은거 고르고, 추가된 곳을 경유해서 가는게 더 빠르면 그 값으로 갱신, 가장 짧은거 고르기 반복
• 
• 
• 

CNN(Convlutional Neural Networks)

• 이전까지는 이미지를 1차원으로 펴서 연산을 했었음
  • 
  • 이미지가 32x32x3이면 1차원으로 펴면 3072x1이 됨
  • 이때 w도 3072에 맞게 3072xn의 크기로 커짐
    • 
  • 연산횟수도 많고 인풋 아웃풋의 모양도 바뀌게 됨
  • 연산횟수 감소와 모양 유지를 위해 컨볼루션을 도입
  • 
  • 뎁스에 맞게 필터도 뎁스를 가짐
    • 컨볼루션 연산 과정은 동일함(3x5x5면 총 75개를 더함)
    • bias도 도입해서 원점을 안 지나게
  • 결국 필터 하나를 씌우면 아웃풋의 뎁스는 1임
    • 
  • 아웃풋의 뎁스(채널)의 수와 필터의 수가 동일해지는 것이고 인풋의 뎁스는 필터의 뎁스와만 동일하며 인풋과 아웃풋의 뎁스는 연관이 없음
    • 
    • 필터쪽에서 사용하는 4차원은 필터의 개수, 인풋과 필터의 뎁스, 필터의 크기가 됨
    • bias도 필터 개수만큼 필요
    • 아웃풋은 인풋에서 필터의 크기를 뺀 크기로 필터의 개수만큼 나옴 -> 6x28x28
  • Batch : 이미지의 개수
    • 
    • 위의 숫자들을 일반화하면
      • 
      • 최종적으로는 4차원이 필요

• 위의 과정이 CNN의 1간계의 레이어이고 일반적으로 여기서도 여러 레이어를 거치게 됨
  • 
  • N은 유지되고 중간중간 필터의 개수가 바뀜에 따라 아웃풋의 개수도 바뀜
• 추가로 컨볼루션도 리니어 연산이기 때문에 컨볼루션 연산 후 non리니어 연산훌 추가해 선형성을 제거해줌
  • 
• 실제로 딥러닝을 거쳐 나온 필터 예시
  • 
• 필터를 거치고나면 가로세로의 크기가 줄어듬
  • 패딩으로 사이즈를 유지
  • 
  • 위를 제로패딩이라 부르고 패딩의 종류는 여러개가 있을 수 있음
  • 인풋, 필터, 패딩의 사이즈에 따른 아웃풋의 크기
    • 
• Receptive Fields
  • 어느 크기의 픽셀에 의존하여 아웃풋이 나왔는지
    • 
    • 아웃풋 한 픽셀의 Receptive Field는 9(3x3)
  • 레이어가 여러개일때 (previous, input)에 대한 receptive field의 크기가 달라 질 수 있음
    • 
    • input에대한 RF는?
      • 
  • Receptive Field의 의미는 이전에 있는 이미지를 커버해주는 범위(높으면 좋은것)
    • 레이어를 많이 쌓거나
    • 이미지의 크기를 줄이면 높일 수 있음
      • 필터를 한번에 1픽셀이 아닌 더 큰 숫자만큼 이동시키면 가능(Strided convolution)
• 최종적인 아웃풋의 이미지 사이즈
  • 
• 아웃풋의 이미지 예제
  • 
  • 
  • 학습 가능한 parameter의 개수
    • (필터의 크기 + bias) * 필터의 개수
    • 
  • 총 연산의 개수
    • 총 필터를 사용한 횟수 x 필터의 크기(한번 할때 필터의 크기만큼 곱하기를함)
    • 
    • 필터를 사용한 횟수와 아웃풋의 사이즈는 동일함

Pooling and batch normalization

• 1x1 convolution : feature를 뎁스1로 합치는 역할
• 필터의 개수에 맞게 학습시키면서 크기를 줄여줌
  • 

Pooling(이미지의 크기를 줄이는 것)

• 
• Max Pooling(max값을 사용해 pooling)
  • 
  • pooling은 학습은 아님, max에서는 가장 큰 값이 살아나게 되는데 이미지의 모양이 유지되는 효과
  • stride가 2인 필터를 돌려도 이미지 크기는 똑같지만 이는 이미지의 모양은 변함(안좋은건 아니고 상황에 맞게 쓰기)

CNN의 과정

• 
• Convolution을 여러번 거치고 1x1의 형태로 펼쳐줘야함(Flatten)
• 
• 마지막은 softmax로 클래스에대한 확률값으로 반환해줌(최종 output size가 10인이유 : 클래스의 개수)
• 추가로 위의 과정에서 convolution을 거칠때마다 값의 범위가 늘어나게됨
  • 정규화가 필요

정규화

• Batch Normalization

  • 정규화에 학습의 여지를 추가해준 것

  • 

  • NxD에서(D는 데이터의 크기,차원 N은 데이터의 개수)

    • 

  • 데이터의 내부에서가 아니라 같은 차원에서의 mean을 구함

    • 
    • 각 feature의 의미를 구하는 것이 결과를 도출하는데 도움이 되기 때문에 같은 차원에서의 평균을 구하는 것

  • 이미지에서의 Batch Normalization

    • 한면을 평균내서 위와 동일하게함
    • 

• Layer Normalization

  • 
  • 자연어처리등 데이터의 양이 매우커 batch정규화를 사용하기 어렵고 차원마다 의미하는게 다르지 않을때 사용
  • 데이터마다의 평균을 구함

• Instance Normalization

  • 가로세로로만 평균을 냄(평균내면 크기가 1)
  • 

• Norm 정리

  • 

Clustering

비지도 학습중 하나

• 기계 학습(비지도 학습)중 하나임
  • 데이터가 어떻게 구성되었는지 알아내는 문제
  • 

다차원 공간에서 여러개의 점들 중 서로 가까이 있는 점들을 서로 연관시키는 문제

• 
• 인물 사진 분류(사진 중 닮은 사진 모으기)
  • 
• 활용 예시
  • 비슷한 뉴스 모으기
  • 스팸메일 분류
  • 비슷한 성향의 사용자/영화 모으기
  • 사진 압축
    • 원본 이미지의 색 가지수를 줄일떄 비슷한 색끼리 묶는 것

K-Means Clustering

• 반복적인 연산을 통해 데이터를 k개의 클러스터로 분할하는 알고리즘
  • 클러스터 분석 알고리즘
  • 분할법(어떤 노드가 클러스터에 중복되게 포함하지 않도록 하는 것)
  • 클러스터 개수 k는 사용자가 지정해야함
  • 반복연산 사용

• 임의로 k개의 중심점을 생성
  • 
• 각각의 점을 가장 가까운 중심점의 클러스터에 포함 시킴
  • 
• 각 클러스터에 포함된 점들을 평균내어 새로운 중심점을 계산
  • 
• 그 후 다시 2번,3번을 반복
  • 
  • 
• 클러스터 변화가 없으면 종료
  • 

Local Optimum

• 초기화된 중심점에 의존하는 것
  • 
  • 좋지 않은 결과가 나옴

중심점 초기화(Local Optimum을 피하기 위해)

• 중심점을 랜덤으로 여러번 시행
  • 비어있는 클러스터가 생길 수 있음
• 데이터 점 들 중 임의로 중심섬을 선택
  • 비어있는 클러스터가 생기지 않음
• 직접 중심점을 지정할 수도 있음
  • 데이터를 얼추 알고 있을 때 사용 가능
• K-Means++
  • 서로 가장 멀리 떨어진 점들을 중심점으로 사용
    • 임의의 점 1개 지정
    • 점에서 가장 멀리 떨어진 점을 중심점 1번으로 사용
    • 중심점 1에서 가장 멀리 떨어진 점이 중심점 2
    • 중심점 1,2둘에서 가장 멀리 떨어진 점이 중심점 3

K 값 선택

• 클러스터의 분산의 합이 낮으면 좋은 것
  • 
• k의 값을 1부터 증가시켜가면서 비용(분산)을 분석
  • 비용의 감소가 급격히 줄어드는 지점을 선택
  • 
  • 저 지점에서 k를 더 늘리면 비슷한 데이터에서 클러스트가 여러개 생길 수 있음

다른 클러스터링 방법

Computational Complexity

• 문제 자체를 분석하는 분야
  • 문제가 컴퓨터로 해결 가능한가?
  • 문제의 lower bound가 몇인지
• lower bound : 문제 해결의 최고 효율(더 좋아질 수 없음)

Heapsort

• Priority Queue사용
  • 
• Binary Tree를 사용함
  • Complete Binary Tree
    • 제일 밑 레벨을 제외한 레벨에서는 모든 노드가 차있고(리프 2개) 제일 밑 레벨은 맨 뒤에서부터만 연속적으로 없어도 되는 구조
    • 
• BST는 1차원 배열로 표현 가능
  • 
  • 왼쪽 리프인덱스는 x2, 오른쪽은 x2+1(루트 인덱스가 1일떄)
  • 리프에서 부모노드의 인덱스는 2로 나누고 버리면 됨
  • 
• 특성
  • 
  • 한 레벨의 노드의 개수는 2^L개
  • Height는 max level
  • full binary tree에서 노드의 개수는 2^h + 1
  • complete binary tree에서는
    • 
  • n개의 노드가 있는 complete binary tree의 H는
    • 

• parent가 크면 Max Heap 작으면 Min Heap(이 둘중 하나를 만족해야 Heap임)
  • 
• 
• 왼쪽만 Heap(둘다 complete tree이긴함)

• Insert
  • 일단 트리의 특성을 유지하기 위해 제일 밑에 추가함
  • 그 후에 추가한 노드를 Heap의 특성을 유지하기 위한 알맞은 위치로 옮겨줌
  • 
• Delete
  • 먼저 삭제하고 싶은 노드를 삭제함(min, max인 루트 노드만 삭제 가능)
  • 제일 밑의 오른쪽을 삭제한 위치(루트)로 옮김(complete binary 트리의 성질을 유지하기 위해 제일 밑의 오른쪽이 비워질 수 밖에 없음)
  • 그 후 루트부터 Heap의 특성을 유지하기 위한 위치로 이동함
  • 
  • 

• Heap Construction
• 삭제후 루트에서 제 위치로 이동하는 과정에서 비교연산이 몇번 일어나는지
• 한번 이동할때 2번비교함(리프 중 더 큰/작은 리프를 찾는데 1번, 루트와 비교하는데 1번)
  • 
• 위의 기능으로 Heap을 divide and conquer로 만들 수 있음
  • 

반복문으로 힙 construction하기

• 리프의 바로 위부터 시작
  • 
• 

Heap Sorting

• 가장 간단한 방법
  • n개의 데이터를 힙에 넣고
  • delete min/max를 n번하면 정렬
  • 

• delete하면서 정렬할때 배열이 1개 더 필요할거 같지만 1개만 있어도 가능함
  • 
  • max를 지우고 36을 root로 올린다음 fix할때 max(97)을 36자리에 주면 됨
  • 
  • 한번할때마다 마지막 자리가 비게 되고 그 자리에 정렬된 원소를 채우는 방식
  • max힙일때 최대값이 제일 뒤로감, min힙은 최소값

Radix Sort

• 비교없이 정렬하는 방법
• 일정 범위를 설정하고 데이터들을 해당하는 범위로 지정하는 과정을 반복
• 
• 위는 100단위, 10단위 1단위 순서로 정렬한것
• 작은 단위부터 정렬하는 방법도 있음
• 
• 1단위로 정렬한 후 10단위로갈때 순서대로 옮기는것이 중요함
• O(n)만에 정렬가능, 비교를 하지 않고 정렬하기 때문에 LowerBound를 적용받지는 않음(적용받을 경우 nlogn이 제일 빠른 경우임)

vector_backprop

• 스칼라끼리의 관계가 있고 백터와 스칼라의 관계는 Gradient, 벡터와 벡터간의 관계를 jacobian이라 함

Jacobian

• 벡터와 벡터간의 관계를 정의
• 위쪽의 1x2의 벡터에서 2개의 행에 각각 x,y가 관여하는 점을 정리
  • 

• 
• f에서 z는 결국 x와 y의 연산의 결과, Backpropagation은 x,y가 그 단계에서 z에 각각 얼마나 영향을 주었는지 구하는 것
• upstream에서 주어진 그레디언트를 가지고 자코비안으로 local 그레디언트를 구해서
• downstream으로 체인룰을 거쳐 흘려보내줌
• 이때 차원도 x,y,z에 맞게 나옴

• 
• upstream의 미분값은 주어지고
  • local 자코비안은 upstream에대한 인풋에 미분
    • 1보다 크면 1 작으면 0
    • 
• 자코비안 행렬에 업스트림에서 주어진 그레디언트를 곱해서 다운스트림으로 흘려주는 것
  • 

행렬의 연산

• 
• 데이터가 N개 들어왔을떄의 경우
  • 결국 행렬의 크기에서 다운스트림과 인풋의 크기가 같아야하고 업스트림과 아웃풋의 크기가 같아야함
  • 
  • 하지만 위의 경우는 연산횟수가 너무 많음(저장공간도 많이 사용)
    • 그래서 중간에 자코비안을 거치지 않고 바로 다운스트림을 구하는 룰을 찾을것
• 그래서 다운 스트림(dL/dx)의 [1][1]을 구하려면?
  • 
  • 인풋(dx)의 [1][1]만 사용
  • 먼저 dy/dx[1][1]을 구함
    • 
    • dy/dx[1][1]은 결국 dx[1][1]과 연관된(dx[1][1]을 사용하는) 부분만 들어가게 됨
      • 
      • dw에서 dx[1][1]을 사용하는 부분만 그대로 들어가는 결과
    • 그 후 dl/dx[1][1]을 위해 위에서 구한 dy/dx[1][1]에 업스트림 dl/dy를 곱함
      • 
      • 행렬 곱셈 아니고 같은 자리끼리 곱하는거
      • 

        일반화

  • dx[1][1]에서 인덱스가 바뀌어도 똑같이 dx[1][1]이 관여하는 값만 살아나고 나머지는 0이됨(일반화 가능)
  • 
  • 
  • 행렬곱하기 위해 w와x를 트렌스포즈하고 각각 앞,뒤에 곱함

Backprogation

• 중간에 모델 구조가 바뀌거나 하는 일 때문에 중간 값을 알기위해선 처음부터 다시 계산해야하는 문제가 있음
• 모듈화를 통해 중간값을 알고 싶음 -> Backprogation

example

• 
• 위의 식에서 x,y,z가 웨이트 w일경우 결국 우리가 원하는건 x,y,z의 편미분값
• chain Rule
  • f에 대한 y의 미분값을 구할때 f와 y가 연결되어 있지 않아 q에대해 미분하고 q와 y를 연관지어 미분
  • 
  • 이 방법도 레이어가 많아지거나 방법이 바뀌면 계싼 횟수가 굉장히 많아지거나 다시 계산해야함 -> 모듈화필요
• Local Gradient : 현재 나의 상태에서 바로 미분이 가능한 것
• Upstream Gradient : 이전에 먼저 계산한(위의 레이어)에서 보이는 변수를 사용해 나에게 흘려준 값
• Downstream Gradient : 내가 Local, Upstream을 체인룰을 활용해 계산 후 밑의 레이어로 흘려주는 값
• 결국 흘러들어온 값에 내가 계산한 값을 곱해 밑으로 흘려주면 됨(모듈화)
  • 
• 

Gradient Flow

• 덧셈 게이트는 위에서 흘러 들어온 값이 그대로 들어오고 곱셈은 반대의 값에 곱함
• 초록색이 현재 값 빨간색이 실제 흘러가는 값
  • 
• 
• 위 과정을 모듈화 가능
• 모듈화를 해야 계산이 바뀌거나 처음 값이 바뀌는 등이 변동이 일어날때 즉시 수정이 가능
  • 

별점 예측(2)

• Latent Factor Model

Factor Model

• 사용자와 아이템을 요소(factor)들로 나타낼 수 있다고 생각
  • 
  • 아이템, 유저의 구분 없이 정해진 주제로 하나의 좌표(벡터)로 표현하는 것

Laent Factor Model

• 아이템이나 유저를 표현할때 주제가 정해지지 않았음
• 

Matrix Factorization

• 사용자와 아이템을 같은 차원의 공간에 매핑(같은 차원의 벡터로 표현)
  • 
  • 
• 벡터들을 내적해서 주어진 평가 정보가 나오도록 벡터들을 학습시킴
  • 
• 
• 여러개의 linear 리그레이션을 동시에 여러개 하는 것과 동일하다고 생각할 수 있음
• 이미 가지고 있는(별점이 평가되어있는)값만 사용해서 벡터를 학습하고 학습이 완료된 벡터를 사용해서 빈칸을 예측해야함

• Training, Test
  • 벡터가 잘 학습되었는지 검증하기위해
  • 학습전에 Trin, Test데이터로 분류하고 train데이터로 먼저 학습한 뒤 test데이터로 검증해봄
  • 

• Overfitting
  • train데이터에 과도하게 맞추어 train을 못 맞추는 현상
  • 
• Regularization으로 해결
  • 
  • 벡터가 너무 큰 값을 가지지 않게 줄이는 것
  • L2 norm = 각 벡터의 제곱의 합을 구한 후 1/2제곱(루트)
  • Ln norm - n제곱의 합의 1/n제곱
• 결과적으로 차원에서 원점에 멀리 떨어져있는 아이템이나 유저를 끌어오는 역할
  • 

Global baseline Estimate + Latent Factor Model

Collaborative Filtering(별점 예측)

방법

• Collaborative Filtering
  • Item-Item
  • User-User
• Latent Factor Model

Item-Item Collaborative Filtering

• 비슷한 아이템(드라마)에 별점을 몇점을 주었는지가 핵심 아이디어
  • 
• 방법 1 : 비슷한 아이템의 평균을 사용
  • 
• 방법 2 : 비슷한 아이템을 유사도를 사용해서 찾음 -> 더 유사한 아이템에 가중치를 줘서 평균내기
  • 
  • 0.7x0.45 + 0.4x5.0/ 0.7+0.4
• N이 2일때 평점 예측하기
• 
• 순서
  • N이 2이기 떄문에 터널(a)와 비슷한 드라마 2개를 구함 -> 시그널, 보이스
  • 0.41 x 2 + 0.59 x 3 / 0.41 + 0.59 = 2.6
  • 
• 유사도는 이전의 코사인, 자카드 유사도등의 방법을 사용

User-User Collaborative Filtering

• 한 유저마다 한 백터로 생각
• 
• a의 평점을 메겼던 B,D,G,J,L과 H와의 유사도를 검사
• 가장 유사한 사람 2명(N)을 구하고 그 사람이 a(터널)에 준 별점을 사용
  • 
• 이론상 Item-Item, User-User는 동일한 정확도를 가짐
• 하지만 실제로는 item, item이 더 좋은 성능을 보임
  • user는 일관적인 평가를 안할 가능성이 높음

Collaborative Fitering 장,단점

Hybrid Method

• 내용 기반 추천 방법(Content-based method)와 Collaborative Filtering을 함께사용
  • 새로운 아이템을 추천할땐
    • 줄거리, 출연진, 키워드등 item profile을 사용
  • 새로운 사용자
    • 전반적으로 인기가 좋은 item을 추천
• 둘 이상의 추천시스템을 구현하고 그것들을 통합
  • ex) global baseline + collaborative filtering

Global Baseline Estimate

• 이미 높은 평점을 받은 드라마에는 나도 높은 평점을 줄것이다, 내가 깐깐한편이면 평균보다 조금 낮게 평점을 줄것이다라는 아이디어를 사용
• ex) 원준이가 드라마 이두나를 보고 매길 평점을 예측
  • 원준이가 이두나와 비슷한 드라마를 본적이 없어 collaborative필터링을 사용 불가능
• global baseline estimate사용
  • 전체 드라마의 평점 평균 : 3.7(이거만 있으면 원준이도 이두나에 3.7을 줄것이다라고 예측)
  • 이두나의 평점 평균 : 4.2(전체 평균보다 0.5점 높음)
  • 원준이가 매긴 전체 드라마의 평점 평균 : 3.5(전체 평균보다 0.2낮음)
  • 기본 점수(global baseline) : 3.7+0.5+0.2 -> 4.0

global baseline + collaborative

• 위에서 구한 기본 평점 4.0을 CF(collaborative Filltering)에 사용
• 
• 

딥러닝 _intro

학습

• 
• W의 값들을 잘 조정해서 원하는 결과가 나오게 하는 것
  • 많은 데이터를통해 w를 갱신해가는 과정이 학습임
  • b가 없으면 직선이 원점을 반드시 지나야 하기 때문에 한계가 있음
• 
• 원점을 지나지 않는 직선은 linear하지 않다
  • b를 더하는 대신 w에 차원을 추가하는 방식으로 linear성질을 유지할 수 있음

템플릿 매칭

• 주어진 데이터(이미지)와 기존의 템플릿을 활용해 결과는 내는 방식
  • 
  • 템플릿과 기존의 이미지의 모양이 비슷해야 아웃풋 값이 커짐
  • 위의 선형 학습은 템플릿 매칭중 하나라고 생각할 수 있음
• 데이터의 개수가 매우 많아지면 그 모든 데이터에 매칭되는 템플릿을 찾는 과정에서 템플릿이 계속 뿌옇게 변해가기 때문에 한계가 명확함, 그래서 딥러닝을 사용
  • 
  • 말(horse)템플릿의 경우 말이 양쪽을 보고 있는 것처럼 보이는데 많은 데이터를 모두 만족시키기 위해서 나온 현상임

학습의 과정

• w를 찾아야 함
  • 
  • loss function을 정의하고
  • optimization으로 이를 최적화함
• loss function
  • 현재의 모델이 얼마나 좋은지를 평가하는 지표
  • loss가 낮으면 좋은것(loss는 정답값과 떨어져있는 정도임)
  • loss를 최소화하게 만드는 w를 찾는것이 학습
• 정답값은 미리 주어져야함
  • 모든 x에대한 결과값 y에대한 데이터 셋이 필요
    • ex) 이미지 x 1번의 y y1은 1(정수로 표현)
    • 
  • 우리 모델의 아웃풋과 정답값의 차이를 정의
    • 위에서 주어진 x에 대한 우리가 정의한 함수를 적용시켜서 나온 결과값과 위에서 주어진 같은 x에대한 정답값 y과의 차이를 구함
    • 차이값은 x의 개수만큼 나오게되고 최종 loss값은 일반적으로 평균값으로 선택
    • 
• 소프트맥스함수로 확률로 변환(기존값을 e의 지수로 올려서 다 더해서 분모로 보내고 각각의 값은 각각의 값을 e의지수로 올려서 분자로 보냄)
  • 
  • 0.13이 정답 클래스에 대한 확률값임 0.13이 1이 될때 -log함수는 0이되기때문에 loss값이 최소가 됨
  • 확률값을 1로 만드는(loss가 최소가 되게 만드는 w를 찾아야함)

DNN

• 데이터의 모양이 non-linear일때 사용
• 
• DNN이 아니여도 Feature transform으로 non-linear데이터셋을 linear로 해결이 가능하긴함
  • 
  • 
  • 이는 feature가 만족하는 형태로 만들어질때까지 여러가지로 변환해봐야하는 단점이 있음
  • 추가로 결국에는 원래의 모양(x,y좌표)은 non-linear라는 단점도 있다.

• Neural Networks(non-linear문제 해결)
• 
• max를 취하는 이유 -> linear의 특성을 피하기 위해
  • max로 0보다 작은 값을 제거하면서 순서성을 부여하고 이는 결합법칙을 깨기때문에 linear의 특성을 깨버림
  • 
• w의 개수에 따라 n-layer Neural Network라고 표현
  • 
• Fully-connected(모든 데이터가 행렬곱셈에서 참여하는 것)

• 레이어마다 계산된 값을 그다음 레이어에서 사용하고 중간중간 max함수로 0으로 만들어버리기 때문에 해석과 추적이 불가능함
  • 
  • 레이어가 많을수록 분별력이 높아짐

    레이어를 찾아가면서 output을 내는것이 딥러닝(Deep Neural Networks)

• 

Regularization

• 위에서 레이어의 개수와 분별력은 비례한다고 하였음
  • 레이어가 많을떄의 단점도 있다(over-fitting)
  • 
  • over-fiting은 train데이터(실험용)과 test데이터(실제 사용시의 데이터)간의 차이에서 문제가 발생함
    • train데이터에 너무 맞춰두면 실제 데이터에는 못 맞추는 경우가 늘어날 수 있음
  • 결국 train데이터는 많아질수록 에러가 적어지지만 test데이터의 양은 많아지면 에러가 많아질수 있음
• over-fitting을 피하기위해 사용하는 것이 정규화(Regularization)
• loss값에 더해져서 loss펑션 자체를 바꾸는 것이 정규화
  • 
  • loss펑션에 붙어서 피팅을 방해해 오버피팅을 완화

• w에서 각각의 값이 너무 크거나 작으면 x각각에 대한 의존도가 높아짐(w의 range를 줄일 필요가 있다 -> regularizer사용)
• Regularizations
  • 
• 
• loss를 데이터, 정규화 loss 2가지로 나눠서 컨트롤
  • 오버피팅을 피하는게 목표라면 람다값을 높이면 됨
  • 

• 
• 레귤라이저 부분이 j에 해당하는 wj에 대해 미분이 되어서 람다wj만 남게 됨
• 
• 앞에 있는 -가 데이터로스, 레귤라이저로스에 붙음
  • n은 러닝레이트

    결론

• 
• L2 norm
• 업데이트과정에서 미분을 사용
• 레귤라이저가 음수면 더하는 값은 양수가 되고 레귤라이저가 양수면 더하는 값은 음수가 됨
  • 결과값의 절대값의 크기가 작아짐

• 
• L1 norm
• 1보다 크면 1, 작으면 -1인 절대값 함수의 미분을 위해 sign함수를 사용
  • 미분하면 양수면 1, 음수면 -1이 나옴
  • 결국에 앞에 -를 붙이기 때문에 갱신시 절대값의 크기가 작아지는것은 동일

L1, L2 norm의 차이

• L1은 1,-1만큼만 이동하고 L2는 본인의 값을 곱해서 이동
• L2는 본인의 값을 곱하면서 본인의 값을 줄이기 떄문에 이동하는 거리가 점점 작아짐(non sparse)
  • 0에 매우 가까워지긴 하지만 0이되지는 않음
• L1은 Spaese한 특성이 있음
  • 실제로 0을 만들 수 있음, L2에 비해서 학습을 거듭하면 0을 만드는 횟수가 많아짐

연결선의 행렬 변환

• 
• 왼쪽의 연결선을 오른쪽의 행렬의 곱으로 옮길 수 있음
• 

Dropout

• 정규화의 방법중 하나
• 딥러닝의 각 계층(레이어)에서 연결선이 너무 많으면 계산이 정확해서 결국 오버피팅 효과가 발생함
• 연결선의 일부분을 지워버려 과도하게 미세한 계산을 피하는 방법이 Dropout
  • 지우는 행렬의 값을 0으로 만들어 반영이 안되게 함
• 
• 앙상블 효과가 있다
  • 랜덤하게 연결선을 지우기 때문에 다양한 모양이 나와 성능이 향상된다
  • 

Early-stop

• 오버피팅 되기전 학습을 중지하는 것
• validation : test데이터를 활용하기 어렵기 때문에 train데이터의 일부를 학습전에 분리해 test데이터처럼 활용 하는 것
• 

Activation Functions

• 종류가 여러개가 있다, 상황에 맞게 종류를 결정해야함
• 중요한 것은 non-linear성질을 다루기위해 사용한다는 것
• 

생물학적 뉴런과 유사