✍️ 문제 풀이

딕셔너리를 이용했다. n개의 숫자를 입력받을 때마다 그 숫자가 딕셔너리에 존재한다면 딕셔너리[입력받은숫자] += 1, 만약 존재하지 않는다면 딕셔너리[입력받은숫자] = 1. 숫자를 전부 입력받은 뒤에는 딕셔너리를 우선 value값을 기준으로 내림차순 정렬을 하고, key값을 기준으로 오름차순 정렬을 한번 더 해준다.

💻 코드

import sys
input = sys.stdin.readline

n = int(input())
nums = {}
for _ in range(n):
    num = int(input())
    if num in nums.keys():
        nums[num] += 1
    else:
        nums[num] = 1

nums = sorted(nums.items(), key = lambda x: (-x[1], x[0]))
print(nums[0][0]) 

👀 문제 풀면서

• 딕셔너리 딕셔너리[key] = value , item = key + value

  # 딕셔너리 정렬
  nums = sorted(nums.items(), key = lambda x: (-x[1], x[0]))

✍️ 문제 풀이

우선 금메달 개수를 기준으로 정렬한다. 금메달 개수가 같다면 은메달, 은메달 개수도 같다면 동메달을 기준으로 정렬한다. sort()와 lambda로 구현했다.

💻 코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

scores = [[] for _ in range(n)]

for i in range(n):
    nation, gold, silver, bronze = map(int, input().split())
    scores[nation-1] = [gold, silver, bronze] 

k_score = scores[k-1]
scores.sort(key = lambda x: (-x[0],-x[1],-x[2]))

for i in range(n):
    if k_score[:] == scores[i][:]:
        print(i+1)
        break    

👀 문제 풀면서

• .sort(key = lambda ~) sort()는 key 값을 기준으로 정렬하며 기본값은 오름차순이다.

  # 인덱스 0의 값으로 오름차순 정렬 후, 인덱스 1의 값으로 내림차순 정렬
  리스트.sort(key = lambda x : x[0], -x[1])

• 배열 비교하기

  if k_score[:] == score[i][:]:

✍️ 문제 풀이

💻 코드

from collections import Counter
import sys
input = sys.stdin.readline

n = int(input())
nums = [int(input()) for _ in range(n)]

print(round(sum(nums)/len(nums)))
nums.sort()
print(nums[len(nums)//2])

counts = Counter(nums).most_common()
if len(counts)>1 and (counts[0][1] == counts[1][1]):
    print(counts[1][0])
else:
    print(counts[0][0])

print(max(nums)-min(nums))

👀 문제 풀면서

• 반올림 소수점 n번째 자리까지만 표현하고 반올림하고 싶을 때 round(실수, n)

import math
math.ceil()  # 올림
math.floor()  # 내림
math.trunc()  # 버림

• collections 모듈의 Counter 클래스

  from collections import Counter
  

sample = "hihello"

딕셔너리 형태 + 내림차순 형태로 반환

counter = Counter(sample) print(counter)

Counter({'h': 2, 'l': 2, 'i': 1, 'e': 1, 'o': 1})

[리스트(튜플)] + 내림차순 형태로 반환

counter = Counter(sample).most_common() print(counter)

[('h', 2), ('l', 2), ('i', 1), ('e', 1), ('o', 1)]

지정한 개수만큼 출력

counter = Counter(sample).most_common(2) print(counter)

[('h', 2), ('l', 2)] ```

풀면서

집합 자료형

• 중복 허용x
• 순서 x

리스트, 튜플과 달리 사전 & 집합 자료형은 순서가 없기 때문에 인덱싱으로 값을 얻을 수 없다. '특정 데이터가 이미 등장한 적이 있는지'를 확인할 때 효과적이다.

• 집합 자료형의 연산
  • 합집합 : |
  • 교집합 : &
  • 차집합 : -
• 집합 자료형 관련 함수
  • 집합에 값을 추가 : .add()
  • 여러 개의 값을 추가 : .update()
  • 특정한 값을 제거 : .remove() +안전한 제거 : .discard()

내 코드

import sys
input = sys.stdin.readline

S = set()

for _ in range(int(input())):
    command = list(input().split())

    if command[0] == "all":
        # for문보다 실행시간이 짧다.
        S = set(['1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11', '12', '13', '14', '15', '16', '17', '18', '19', '20'])
    elif command[0] == "empty":
        S = set()
    elif command[0] == "add":
        S.add(command[1])
    elif command[0] == "remove":
        S.discard(command[1])
    elif command[0] == "check":
        print(int(command[1] in S))
    elif command[0] == "toggle":
        if command[1] in S:
            S.remove(command[1])
        else:
            S.add(command[1])

• 집합 개념
• for문을 사용하지 않고 일일이 작성해 주는게 실행 시간이 짧다. (상황에 맞게 잘 선택하기)

문제 풀이

n개 문서의 중요도를 저장할 리스트(files)와 몇 번째로 인쇄되는지 궁금한 문서의 위치를 표시한 리스트(check), 총 2개의 리스트가 필요하다. files과 그때의 리스트의 최댓값(max(files)을 비교해 나간다. 비교 결과에 따라 문서를 출력, 즉 files.pop()을 하여 리스트에서 해당 값을 빼내거나 리스트의 가장 뒤로 값을 옮기게 되는데 files.append(files.pop()) 위와 같은 작업을 check에도 똑같이 수행한다. 이를 통해 files 내에서 문서들의 위치가 계속 변경이 되더라도 내가 표시해둔 문서의 위치 정보를 계속 유지할 수 있다.

코드

import sys
input = sys.stdin.readline

cases = int(input())

for _ in range(cases):
    n, idx = map(int, input().split())
    files = list(map(int, input().split()))
    check = [0 for _ in range(n)]
    check[idx] = 1

    count = 0
    while files:
        if max(files) == files[0]:
            files.pop(0)
            count += 1
            if check.pop(0):
                print(count)
                break
        else:
            files.append(files.pop(0))
            check.append(check.pop(0))

📝 문제 풀면서

문제 제대로 읽기

문제 풀이

k번 숫자를 입력받고 0이라면 정수리스트.pop(), 0이 아니라면 정수리스트.append(정수)를 해준다.

코드

import sys
input = sys.stdin.readline

k = int(input())
nums = []

for _ in range(k):
    num = int(input())
    if num == 0:
        nums.pop()
    else:
        nums.append(num)

print(sum(nums))

📝 문제 풀면서

1. sys.stdin.readline() 한 줄 단위로 입력받으며 개행문자까지 입력받는다.

풀이

내 코드1

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

people = [num+1 for num in range(n)]
idx = 0

print("<", end="")
while people:
    idx += k-1
    if idx > len(people)-1:
        idx %= len(people)
    print(f"{people.pop(idx)}", end="")
    if people:
        print(", ", end="")

print(">")

idx=0 에서 시작해서 k-1을 더해주면서 k번째 차례가 된 원소를 기존리스트.pop(idx)로 기존리스트에서 삭제함과 동시에 바로 출력한다. 기존 리스트의 길이가 0이 될때까지 위의 과정을 반복한다. 이때 idx가 인덱스 범위를 초과했다면 리스트의 길이만큼 나눠준다.(원개념) 출력형태를 맞추는 것도 꽤 신경 써야 했다.

내 코드2

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

# 1.
people = list(range(1, n+1))
ans = []
idx = 0

while people:
    # 2.
    idx = (idx + k - 1) % len(people)
    ans.append(str(people.pop(idx)))

# 3.
print("<" + ", ".join(ans) + ">")

빈 배열 ans[]를 준비한다. people 배열이 빌 때까지 idx = (idx + k - 1) % len(people)를 반복하여 그때의 배열 내의 k번째 원소를 찾아낸다. 이때 그 k번째 원소를 ans 배열에 문자열로 바꿔서 저장한다. 그래야 마지막 결과를 출력할 때 .join()을 사용할 수 있다.

📝 문제 풀면서

1. 리스트 생성 방법 익히기

   list(range(숫자범위))

2. 인덱스가 범위를 초과하지 않는 경우 len(people)로 나눈 나머지값과 같기 때문에 모든 경우에 len(people)로 나눠줘서 코드를 단축한다.

3. 출력 방법 익히기 *ans배열에 저장할때 문자열로 바꾸고 저장

*join함수 익히기

코드1

import sys
input = sys.stdin.readline


n = int(input())
ans = n

for i in range(n):
    vocabs = input().rstrip()
    ch = []
    idx = 0

    while idx < len(vocabs) - 1:
        if vocabs[idx] != vocabs[idx+1]:
            if vocabs[idx] in ch:
                ans -= 1
                break
            else:
                ch.append(vocabs[idx])
        idx += 1
    if idx == len(vocabs) - 1 and vocabs[idx] in ch:
        ans -= 1

print(ans)

while문으로 현재 인덱스의 문자와 인덱스+1의 문자를 비교하고 문자를 따로 리스트에 저장한다. 이때 리스트에 이미 존재하는 문자인지 확인을 하는데 이미 존재한다면 그룹 단어가 아닌 것. 인덱스 와 인덱스+1을 비교하기 때문에 맨 마지막 문자의 경우 인덱스+1을 하면 에러가 발생한다. 그래서 맨 마지막 문자는 while문 밖에서 따로 검사하도록 했다. while문 안에서 깔끔하게 다 넣고 싶었는데 생각해보다가 말았다. 고쳐봐야지. 효율적인 코드로 짜고 싶었는데 방법을 모르겠어서 그냥 일단 100점 맞추는 것만 생각하고 풀었다. 다른 코드들 찾아봐야겠다.

코드2

import sys
input = sys.stdin.readline

ans = 0

for i in range(int(input())):
    vocab = input().rstrip()
    if list(vocab) == sorted(vocab, key=vocab.find):
        ans += 1

print(ans)

• 문자열.find('문자') 문자열 내에서 가장 먼저 발견되는 '문자'의 인덱스를 반환한다. 즉, '문자'가 문자열 내에서 여러 번 반복되더라도 가장 첫 번째 위치를 반환한다.
• sorted(vocab, key = vocab.find) key의 인수로 함수를 전달받고 vocab 내의 모든 문자들에게 해당 함수를 적용한다.

n을 리스트로 입력받아서 숫자 한 자리씩 떼어내서 저장 itertools.permutations로 가능한 모든 숫자 조합을 만들어 리스트로 저장 그 리스트를 내림차순으로 정렬 후 30으로 나눠가며 나누어 떨어지면 해당 값이 정답이 된다. 위와 같이 풀어봤는데 메모리 초과가 떴다. 쓸데없이 복잡하게 생각했다.

풀면서

• 개행문자 빼고 문자열 입력받기

  n = input().rstrip()

• "구분자".join(리스트) 구분자를 기준으로 리스트 내의 문자들을 합쳐준다.

• 형변환, map(함수, 반복 가능한 자료형) 여러 개의 데이터를 한 번에 자료형으로 변환할 때 두 번째 인자로는 주로 리스트나 튜플이 들어간다.

  nums = list(map(int, input().rstrip()))
  nums = map(str, nums)

내 코드1

import sys
input = sys.stdin.readline

# 개행문자빼고 입력받은 문자열을 map(int,~)로 정수형으로 변환 후 리스트화
nums = list(map(int, input().rstrip()))
if 0 not in nums or sum(nums) % 3 != 0:
    print(-1)
else:
    # 최댓값을 찾는 거니까 + 0은 자동으로 가장 끝자리에 위치
    nums.sort(reverse=True)
    # 정수형으로 저장된 nums 리스트내의 모든 값들을 str형으로 변환
    nums = (map(str, nums))
    print("".join(nums))

30의 배수를 찾아내는 조건문을 만들어 주면 된다. 3의 배수는 각 자릿수의 합이 3의 배수다. 즉, 0이 반드시 1개 이상 존재하고 모든 자릿수들의 합이 3의 배수라면 30의 배수가 된다.

내 코드2

import sys
input = sys.stdin.readline

nums = list(input().rstrip())
nums.sort(reverse=True)

if nums[-1] != '0' or sum(map(int, nums)) % 3 != 0:
    print(-1)
else:
    print("".join(nums))

sum을 구할 때만 nums내의 값들이 정수형이면 된다. 실행 시간이 줄었다.

다른 풀이

오름차순으로 정렬할 생각을 못했다. 입력받은 리스트를 정렬을 통해 정리를 하고 문제를 풀어나가는 경우가 꽤 많은 것 같다.

여기저기 참고한 코드

import sys
input = sys.stdin.readline

t = int(input())
rank = []

for _ in range(t):
    n = int(input())
    ans = 1
    rank.clear()
    rank = [list(map(int, input().split())) for i in range(n)]
    rank.sort()

    min = rank[0][1]
    for j in range(1, len(rank)):
        if min > rank[j][1]:
            ans += 1
            min = rank[j][1]

    print(ans)

• 우선 서류심사 성적을 기준으로 정렬한다.
• 이제 면접시험 성적을 비교해 본다.

내 코드

import sys
input = sys.stdin.readline

n = int(input())

ropes = []
for _ in range(n):
    ropes.append(int(input()))

ropes.sort(reverse=True)
ans = 0
for i in range(1, n+1):
    tmp = (i * ropes[i-1])
    ans = max(tmp, ans)

print(ans)

가장 적은 무게를 드는 로프가 기준이 된다.

내 코드

import sys
input = sys.stdin.readline

string = input()

tmp = ""
f = 1
ans = 0

for c in (string):
    # 숫자
    if c != "+" and c != "-":
        tmp += c
    else:
        ans += f * int(tmp)
        if c == "-" and f != -1:
            f *= -1
        tmp = ""

print(ans + (f * int(tmp)))

다른 풀이

import sys
input = sys.stdin.readline

string = input().split("-")

ans = 0
for i in string[0].split("+"):
    ans += int(i)
for i in string[1:]:
    for j in i.split("+"):
        ans -= int(j)

print(ans)

• -를 기준으로 문자열 분리

문제 풀면서

• 배열에서 최댓값의 인덱스 가져오기

  print(list.index(max(list)))

내 코드1

import sys
input = sys.stdin.readline

n = int(input())
list_A = []
list_B = []

list_A = list(map(int, input().split()))
list_B = list(map(int, input().split()))

# B의 큰 수와 A의 작은 수가 곱해지도록

list_A.sort()
ans = 0
for n in (list_A):
    B_max = max(list_B)
    ans += n * B_max
    list_B.pop(list_B.index(B_max))


print(ans)

문제 풀이

'너무 늦게 끝나는 회의를 시작해버리면 다른 회의들을 진행할 수가 없다.'

입력 받은 회의의 시작시간과 끝나는 시간을 저장한 리스트를 두 번 정렬하는 과정이 필요하다. 우선, 회의 시작시간을 기준으로 오름차순 정렬을 한다.

times.sort()

이때 만약 회의의 시작시간(times[][0])이 같다면 그 다음 인덱스 값인 끝나는 시간(times[][1])을 기준으로 정렬이 된다. 이후 이번에는 회의 종료시간을 기준으로 정렬을 한다.

times.sort(key=lambda a: a[1])

앞에서 언급했듯 회의 시작시간이 같다면 종료시간을 기준으로 정렬이 되는데 왜 또 다시 종료시간을 기준으로 정렬을 해줘야 할까 문제에서 원하는 답은 가능한 회의의 최대 개수를 출력하는 것이었다. 예를들어 시작시간, 종료시간이 아래와 같은 회의를 입력받았다고 하자.

(0, 15) (1, 4) (4, 6)

시작시간을 기준으로 정렬을 한 번만 한다면 0시 시작 15시 종료인 회의 1개밖에 진행할 수 없다. 종료시간을 기준으로 다시 정렬을 진행하면

(1, 4) (4, 6) (0, 15)

2개의 회의를 진행할 수 있다.

코드

import sys

input = sys.stdin.readline

n = int(input())
times = []

for _ in range(n):
    time = list(map(int, input().split()))
    times.append(time)

times.sort()
times.sort(key=lambda a: a[1])

end = times[0][1]
ans = 1
for i in range(1, len(times)):
    if times[i][0] >= end:
        ans += 1
        end = times[i][1]

print(ans)

📝 문제 풀면서

1. 리스트에서 특정 인덱스값으로 정렬하기

key를 이용한다.

times = [[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]

# 방법1
times.sort(key = lambda a: a[0])
# 방법2
sorted(times, key = lambda a: a[0])

첫 번째 인덱스값으로 정렬을 원하면 그냥 times.sort()를 해줘도 되는 것 같다. 2차원배열.sort()를 하면 첫 번째 키 값이 동일하면 자동으로 그 다음 키 값에 따라 정렬된다.

2. 리스트에서 특정 값 삭제하기

   • 인덱스로 제거
     • del 리스트[인덱스] 슬라이싱도 가능하다.
     • 리스트.pop(인덱스) 매개 변수가 없을 때는 자동으로 -1값이 들어가서 리스트의 맨 마지막 요소를 제거한다.
   • 값으로 제거
     • 리스트.remove(값) 넘겨준 값을 가지는 원소를 삭제한다. 해당 값이 여러 개라면 가장 앞에 있는 요소 1개를 삭제한다.
   • 모든 원소 제거
     • 리스트.clear()

3. for문에서 zip 두 개의 리스트를 for문에서 동시에 돌리고 싶을 때

   l1 = [1, 2, 3]
   l2 = [4, 5, 6]
   

for n1, n2 in zip(l1, l2): print(n1, n2)

1 4 2 5 3 6

_처음에는 문제를 너무 단순하게 생각했다.
회의의 최대 개수를 출력해야 한다는 것에 대해 깊게 생각하지 않았다. _

Summary

Summary: Main topics

• Supervised Learning

  • Linear regression, logistic regression, neural networks, SVMs

• Unsupervised Learning

  • K-means, PCA, Anomaly detection

• Special applications/special topics

  • Recommender systems, large scale machine learning

• Advice on building a machine learning system

  • Bias/variance, regularization; deciding what to work on next: evaluation of learning algorithms, learning curves, error analysis, ceiling analysis.

Photo OCR

1) Problem Description and Pipeline

The Photo OCR problem

Photo Optical Character Recognition

1. Text detection 주어진 사진에서 텍스트 부분을 감지한다.

sliding window

2. Character segmentation 1D sliding window

3. Character classification 이러한 시스템을 파이프라인 이라고 한다.

2) Sliding Windows

Text detection

1D Sliding window for character segmentation

3) Getting Lots of Data and Artificial Data

Aritificial data synthesis for photo OCR

데이터를 무한으로 만들어낼 수 있다.

Synthesizing data by introducing distortions

16개의 새로운 데이터를 만들어 냈다. amplify

의미없는 노이즈는 별 도움이 되지 않는다.

Discussion on getting more data

1. 위와 같이 데이터를 늘리는 노력을 하기 전에 우선 분류기가 low bias를 가졌는지를 확인해야 한다. 그래야 데이터를 늘리는 것이 의미가 있기 때문이다. plot curve 그래프를 통해 low bias 여부를 확인한다. 만약 low bias 분류기가 아니라면 low bias가 될 때까지 feature의 개수를 늘리거나 neural network의 hidden unit 개수를 늘린다.
2. "How much work would it be to get 10x as much data as we currently have?" 라는 질문에 대해 생각해 본다.
   • Artificial data synthesis
   • Collect / label it yourself
   • "Crowd source"

3) Ceiling Analysis: What Part of the Pipeline to Work on Next

Estimating the errors due to each component (ceiling analysis)

우선 전체 시스템의 accuracy는 72% 다. 1. Text detection이 100%의 정확도를 가진다고 가정한다. 100% 정확도를 갖는 결과를 가지고 이후의 Character segmentation, Character recognition을 진행한다. 그러면 전체 시스템의 정확도는 89%가 된다. 2. Character segmentation이 100%의 정확도를 가진다고 가정하고 나머지 단계들을 실행한다. 전체 시스템의 정확도는 90%가 된다. 3. Character recognition이 100%의 정확도를 가진다고 가정한다. 전체 시스템의 정확도는 당연히 100%가 된다.

정리하면

• Text detection에 시간을 들여 정확도를 최대한 올렸을 때 최대 17(89 - 82)% 만큼의 성능을 높일 수 있다.
• Character segmentation에 시간들 들여 정확도를 최대한 올렸을 때 최대 1(90 - 89)% 만큼의 성능을 높일 수 있다.
• Character recognition에 시간을 들여 정확도를 최대한 올렸을 때 최대 10(100 - 90)% 만큼의 성능을 높일 수 있다.

ceiling , 최대 얼만큼 성능 향상을 할 수 있는지

Advanced Topics

1) Online Learning

온라인 학습 알고리즘은 실시간으로 유입되는 데이터를 모델링하고 학습한다. 고정된 훈련 세트라는 개념이 없다. 지속적으로 새롭게 유입되는 데이터로 학습을 하고, 학습을 했다면 해당 샘플은 폐기한다. 데이터가 지속적으로 계속 유입된다면 충분히 새로운 데이터를 확보할 수 있기 때문에 한 번 사용했던 샘플은 다시 사용하지 않는다. 온라인 학습 알고리즘은 연속적인 데이터 스트림이 발생하는 환경에서 매우 효과적이다.

Can adapt to changing user preference. Can keep track of changes 유입되는 데이터의 변화에 따라 자동으로 파라미터를 조정한다.

• CTR(click-through rate) 실제 예측 클릭률

온라인 학습 알고리즘은 확률적(Stochastic) 경사 하강법 알고리즘과 매우 유사하다. 하지만 이때 온라인 학습의 경우 고정된 데이터가 아닌 새롭게 유입되는 샘플 데이터 1개씩으로 훈련을 하며 한 번 사용한 샘플은 폐기한다.

2) Map Reduce and Data Parallelism

Map-reduce

• 훈련 세트를 쪼갠다.
• 쪼갠 각 훈련 세트들을 서로 다른 컴퓨터로 보낸다. (또는 컴퓨터 한 대 내에서 각각 다른 core로 보낸다. 이 경우에는 네트워크 지연율은 고려하지 않아도 된다.) 각 컴퓨터들은 연산을 수행한다.
• 각 컴퓨터들의 연산 결과를 하나의 중앙 서버로 보낸다.

병렬화

Map-reduce and summation over the training set

Q. Suppose you apply the map-reduce method to train a neural network on ten machines. In each iteration, what will each of the machines do? : Compute forward propagation and back propagation on 1/10 of the data to compute the derivative with respect to that 1/10 of the data.

Gradient Descent with Large Datasets

1) Learning With Large Datasets

학습알고리즘이 이전보다 더 잘 동작하는 이유는 학습알고리즘을 훈련시킬 수 있는 데이터셋이 커졌기 때문이다. 데이터셋이 커지면 왜 성능이 좋아질까?

Machine learning and data

이전에 배웠던 성능이 좋은 학습 알고리즘을 얻는 방법 중 하나는 low bias 알고리즘을 크기가 큰 데이터셋으로 훈련시키는 것이었다.

Learning with large datasets

크기가 큰 데이터셋으로 학습할 때에 연산비용과 관련한 문제점이 발생한다.

훈련 세트의 크기 m이 아래와 같다고 할 때. $$ m = 100,000,000 $$ $$ \theta_j := \theta_j - \alpha\frac{1}{m}\sum_{i=1}^{m}(h_\theta(x^{(i)} - y^{(i)})x_j^{(i)} $$ $\theta_j$ 하나를 계산할 때마다 매번 100,000,000 개의 값을 더하는 과정이 필요하며, 이 계산 비용은 꽤 크다. 이후의 강의에서 이 과정을 좀 더 효율적으로 바꿔줄 방법에 대해 배운다. 100,000,000개의 데이터를 전부 다 활용하지 않고 그 중 랜덤으로 1000개만을 뽑아서 사용하는 방법도 있다. 우선 1000개만으로 학습을 해본 뒤, learning curve를 그려보고 전체 데이터셋을 사용하지 않아도 충분한 학습이 가능한지 확인한다. High bias 라면 데이터를 더 늘리는 것이 의미가 없다.

2) Stochastic Gradient Descent

데이터셋이 클 경우 경사하강법 연산 비용이 커지게 된다.

Linear regression with gradient descent

경사하강법을 사용해서 Linear regression을 훈련하고자 할 때 가설과 비용함수는 아래와 같으며, 비용함수의 그래프는 활 모양을 띈다. $$ h_\theta(x) = \sum_{j=0}^{n}\theta_jx_j $$ $$ J_{train}(\theta) = \frac{1}{2m}\sum_{i=1}^{m}(h_\theta(x^{(i)} - y^{(i)})^2 $$ 경사하강법 수행은 다음과 같다. $$ \text{Repeat} {
\theta_j := \theta_j - \alpha\frac{1}{m}\sum_{i=1}^{m}(h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)}
\text{( for every j=0, ... , n) }} $$ 이때 m의 크기가 크다면 derivative term ($\frac{1}{m}\sum_{i=1}^{m}(h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)}$)의 연산비용이 커지게 된다. derivative term에서 m의 값을 전체 훈련 세트로 설정해두고 계산하는 것을 Batch gradient descent라고 한다. 매 iteration마다 훈련세트 전체를 고려하지 않는 것은 Stochastic gradient descent.

Stochastic gradient descent

Stochastic의 경우 Batch와 달리 전체 훈련세트를 훑고 $\theta_j$를 업데이트 하는 것이 아니기 때문에 최적값에 도달하는 과정에서 아래 그림과 같이 방향 전환이 많이 발생한다. 하지만 이때 속도는 더 빠르다. GD : 전체 데이터셋 , SGD : 샘플 1개

3) Mini-Batch Gradient Descent

• Batch gradient descent : Use all $m$ examples in each iteration
• Stochastic gradient descent : Use 1 example in each iteration
• Mini-batch gradient descent : Use $b$ examples in each iteration 이때 $b$를 mini-batch size 라고 한다.

Mini-Batch Gradient Descent

mini-batch vs stochastic mini-batch는 stochastic 보다 더 많은 샘플들을 살펴봐야 하지만 벡터를 이용한다면 오히려 더 빠른 연산이 가능하다.

4) Stochastic Gradient Descent Convergence

Checking for convergence

각각의 경사하강법들에서 convergence를 확인하는 방법.

Plot $cost(\theta, (x^{(i)}, y^{(i)})),$ averaged over the last 1000(say) examepls

Stochastic gradient descent

학습률의 값을 위와 같이 점점 감소시키면 같은 값을 유지한 것보다 더 좋은 결과를 얻을 수 있다. If we reduce the learning rate α (and run stochastic gradient descent long enough), it’s possible that we may find a set of better parameters than with larger α.

비용 함수를 최적화하는 관점에서 stochastic gradient descent를 모니터링하는 방법에 대해 배웠다. 이 방법은 훈련 세트 전체가 아닌 일부만 이용한다. 이 방법으로 stochastic gradient descent가 제대로 동작하고 있는지, 즉 최적값으로 잘 수렴하고 있는지 확인할 수 있고 또한 학습률 α를 조정할 수 있다.

Recommender Systems

1) Vectorization: Low Rank Matrix Factorization

Collaborative filtering을 matrix로 나타내면 다음과 같다.

Collaborative filtering

Finding related movies

2) Implementation Detail : Mean Normalization

Mean normalization

Recommender Systems

1) Multivariate Gaussian Distribution

' $x^{()}$ 는 영화에 대한, $\theta^{()}$는 사용자들에 대한 데이터 ' ' $\theta^{()}$에서 가장 첫 번째 항은 기본으로 0이 들어감~~ ' 위의 데이터를 보고 Alice와 Bob은 $x^{(1)}$을 좋아한다. Carol과 Dave는 $x^{(1)}$을 안 좋아한다.

위의 사용자별로 주어진 $\theta^{(~)}$에서 Alice와 Bob은 romance를 좋아했다. 반면 Carol과 Dave는 action을 좋아했다. 따라서 이를 바탕으로 아래와 같이 추측할 수 있다.

$x_1$	$x_2$
1.0	1.0
내가 구하려는 것은 $x^{(1)}$의 feature vector
아래의 식들을 만족하는 $x^{(1)}$을 구하면 된다.

Optimization algorithm

Collaborative filtering

2) Collaborative filtering algorithm

Collaborative filtering algorithm

$Q :$ 초기값을 작은 값으로 초기화하는 이유