희소 코딩: 축은 많이, 쓰는 축은 몇 개만

혼동하기 쉬운 점과 요약

토론 1. 축 번호도 숫자 하나니까 좌표 하나만큼 드나

평면의 점 하나를 「축 번호, 계수」 두 숫자로 적는 것과 「좌표, 좌표」 두 숫자로 적는 것은 같은 길이인가.

선생님 T01
선생님

별 모양 점 하나를 희소 코드로 적으면 「몇 번 축, 계수 얼마」, 주성분 축으로 적으면 「좌표 얼마, 좌표 얼마」예요. 어느 쪽이 짧을까요?

이서연 S03
이서연

둘 다 숫자 둘이에요. 평면의 점이니까 숫자 둘은 어차피 드는 것 같고요. 그런데 본문에서는 희소 코드가 짧다고 했는데, 숫자 개수로는 그게 안 보여요.

선생님 T01
선생님

좌표 하나는 8비트로 적기로 했죠. 축 번호에도 8비트가 들까요?

이서연 S01
이서연

번호는 1, 2, 3 가운데 하나니까… 2비트면 충분하네요. 계산하면 log₂ 3 = 1.585비트예요. 숫자는 둘인데, 하나는 값이 세 가지뿐이었어요.

김민준 M01
김민준

그럼 축을 많이 둘수록 번호가 비싸지겠다. 축이 몇 개까지면 좌표 둘보다 짧아?

이서연 S01
이서연

좌표 둘은 16비트고, 희소 코드는 축이 m개면 log₂ m + 8비트야. log₂ m < 8이어야 하니까 m < 256.

선생님 T01
선생님

같은 평면 자료에 축을 1,000개 두면요?

김민준 M07
김민준

log₂ 1,000이 10쯤이니까 번호 하나가 좌표 하나보다 비싸져요. 점 하나에 18비트라 좌표 둘보다 길어지네요. 축을 넘치게 둔다고 늘 짧아지는 게 아니었어요.

선생님 T13
선생님

그래요. 번호는 공짜도 아니고, 실수 하나와 같은 값도 아니에요. 몇 가지 가운데 하나인지가 정하고, log₂(가짓수) 비트가 들어요. 희소 코드가 짧아지는 것은 계수를 적는 비트에 비해 그 번호가 쌀 때예요.

이서연 S07
이서연

방사형 도로 도시에서 「번호 + 거리」가 숫자 둘인데도 짧았던 것도 큰길이 셋뿐이어서였네요.

토론 2. L1 페널티를 붙이면 0인 계수가 늘 생기나

L1 페널티를 더해 선택한 답에는 0인 계수가 반드시 있는가.

선생님 T01
선생님

문제 6에서 가중치 (0.8, 0.05, −0.3, 0.02)에 L1 페널티를 주자 둘이 0이 됐어요. L1 페널티를 붙이면 늘 이렇게 될까요?

김민준 M01
김민준

네, 손실에 L1 항을 붙이면 가중치가 희소해진다고 배웠어요. 마름모 꼭짓점에 닿으니까요.

선생님 T01
선생님

같은 가중치에 λ = 0.01로 해 볼까요?

김민준 M04
김민준

가중치마다 소프트 스레숄딩이니까 0.79, 0.04, −0.29, 0.01… 어, 0이 하나도 없네요.

선생님 T01
선생님

λ = 0.1에서 0이 된 가중치는 어떤 것들이었죠?

김민준 M01
김민준

0.05랑 0.02요. 둘 다 크기가 0.1보다 작았어요. λ = 0.01이면 가장 작은 0.02도 문턱을 넘으니까 다 살아남는 거고요.

이서연 S01
이서연

축이 직교하지 않을 때도 그럴까? 본문의 마름모 그림에서 타원 가운데를 (1.2, 0.5)로 옮긴 경우가 있었잖아.

선생님 T01
선생님

그때 타원이 마름모의 어디에 닿았죠?

이서연 S06
이서연

꼭짓점이 아니라 변 위 (0.85, 0.15)에 닿았어요. 두 계수가 다 살아남았고요. 꼭짓점에 닿기 쉬울 뿐이지 꼭 닿는 건 아니네요.

김민준 M01
김민준

그럼 어느 계수가 0이 될지는 뭘로 알아?

선생님 T01
선생님

문제 5에서 계수가 모두 0인 답을 알아본 조건을 계수 하나에 써 보면요?

이서연 S11
이서연

그 계수가 0일 때 맞추기 항의 그래디언트 성분이 [−λ, λ] 안에 들면 0에 머물러요. 폭을 넘으면 0을 벗어나고요.

선생님 T13
선생님

그래요. L1 페널티는 계수가 0에 머물 수 있는 폭을 만들어 줄 뿐이에요. 0이 되는 것은 0에서의 그래디언트가 그 폭 안에 드는 계수뿐이고, λ가 작거나 등고선이 마름모의 변에 닿으면 모든 계수가 살아남아요.

혼동하기 쉬운 점

혼동하기 쉬운 생각 나온 문제 바로잡는 법
「번호 + 거리」와 「동쪽 + 북쪽」을 같은 숫자 둘로 봄 1, 토론 1 번호는 몇 가지 가운데 하나라 log₂(가짓수) 비트면 된다. 실수 하나에 번호가 붙은 것과 실수 둘은 다르다
축이 차원보다 많은데 답이 하나라고 봄 2 미지수가 식보다 많으면 답이 끝없이 많다. 어느 답을 선택할지는 기준이 정한다
제곱합이 가장 작은 답(유사역행렬)이 희소하다고 봄 2 제곱합을 가장 작게 하면 값이 여러 축에 조금씩 나뉜 답이 나온다. 0이 많은 답을 얻으려면 L1 페널티처럼 다른 기준을 써야 한다
차원보다 많은 특징을 담으면 늘 서로 망가뜨린다고 봄 3 특징이 드물게 켜지면 거의 늘 하나만 켜진다. 켜질 확률 0.05면 켜진 경우의 5.1%만 겹친다
L1 페널티를 붙이면 0인 계수가 늘 생긴다고 봄 토론 2 0이 되는 것은 0에서의 그래디언트가 폭 [−λ, λ] 안에 드는 계수뿐이다. λ가 작거나 등고선이 마름모의 변에 닿으면 모든 계수가 살아남는다
소프트 스레숄딩과 하드 스레숄딩을 같게 봄 4 소프트 스레숄딩은 문턱을 넘은 만큼만 남겨 값이 뛰지 않는다. L1 페널티의 답은 소프트 스레숄딩이다
계수가 모두 0이 되는 λ를 신호의 크기(절댓값 합)로 추정함 5 0에서의 그래디언트가 꺾인 폭 안에 들어야 한다. λ ≥ max |aⱼ·x|
처음 내적이 큰 축이 먼저 살아난다고 봄 5 앞서 살아난 축이 신호를 가져간 뒤의 내적이 정한다
작은 가중치는 학습 뒤 반올림하면 된다고 봄 6 반올림 문턱은 목적 밖의 임의 선택이다. L1 페널티는 목적 안에서 0을 선택한다
스텝 크기를 「차이 × 1」로 둠 7 차이가 (1 − 곡률 × 스텝 크기)배가 된다. 곡률이 클수록 스텝을 줄인다
보장 범위를 넘은 스텝 크기가 한 번 통하면 늘 통한다고 봄 8 η ≤ 1/σ₁² 가 모든 문제의 보장이다. 넘으면 쓰이는 축에 따라 수렴, 진동, 발산이 결정된다
음수를 막은 ISTA 와 부호 있는 ISTA 가 같은 답을 낸다고 봄 9 답에 음수 계수가 필요한 신호에서는 다른 답이 나온다
축의 길이를 묶지 않고 L1 페널티를 줌 11 축을 늘리고 계수를 줄이면 페널티가 0으로 간다. 축을 길이 1로 묶는다
축 수를 늘리면 일하는 축도 그만큼 는다고 봄 12 죽은 축이 생기거나 한 특징을 여럿이 쪼개 맡는다

요약

면 하나에 모이지 않는 자료는 축을 차원보다 많이 두고 점마다 몇 개만 쓰면 더 짧게 적힌다. 다만 축 번호에도 log₂(축 수) 비트가 들어서, 번호가 계수를 적는 비트보다 쌀 때만 그렇다. 장 머리에서는 쓰이는 방향이 차원보다 많은 자료를 무엇으로 짧게 적고 그 방향들을 어떻게 찾느냐고 물었다. 희소 코드로 적고, 축은 딕셔너리 러닝으로 자료에서 찾는다. 중첩 가설대로라면 작은 언어 모델의 뉴런 하나가 학술 인용, 영어 대화, HTTP 요청, 한국어 글에 함께 켜진 것은, 그 뉴런을 조금씩 나눠 쓰는 뜻의 방향이 여럿이기 때문이다.

자료가 평평한 면 하나가 아니라 여러 직선(부분공간)의 합집합에 놓이면, 주성분 축은 그 구조를 보지 못한다. 별 모양 점 300개에서 두 고윳값은 0.184와 0.174로 거의 같았다. 차원보다 많은 축을 모아 두고 점마다 몇 개만 쓰는 희소 코드로 적으면, 점마다 계수 하나와 축 번호(log₂ 3 비트)로 충분해 300점이 4,800비트에서 약 2,900비트로 줄었다. 축이 넘치면 같은 점을 적는 방법이 끝없이 많고, 제곱합이 가장 작은 답은 축을 모두 쓴다.

0이 아닌 계수의 수를 직접 줄이는 대신 절댓값 합을 페널티로 주면(L1 페널티, 라쏘), 계수 하나의 답은 작은 값을 0으로 만드는 소프트 스레숄딩이 되고, 계수가 여럿이면 등고선이 마름모의 꼭짓점에 닿아 계수가 0이 된다. 계수가 서로 겹칠 때는 맞추기 항으로 경사 한 스텝, 페널티로 소프트 스레숄딩 한 번을 반복하는 ISTA로 푼다. 네 칸 신호에서 칸2~칸4의 계수는 넷째 스텝에 0이 되었고, 스텝 크기 η ≤ 1/σ₁²에서 목적은 스텝마다 준다. 축 자체도 코드 고치기와 축 고치기를 번갈아 하는 딕셔너리 러닝으로 자료에서 찾을 수 있다. 별 모양에서는 두 번 만에 세 직선을 찾았지만, 목적이 볼록하지 않아 처음 축에 따라 갇히기도 했다. 언어 모델 안에서 딕셔너리 러닝을 희소 오토인코더로 한 연구들은, 뉴런 수보다 훨씬 많은 축을 배우고 토큰마다 그 가운데 몇백 개만 켜지는 코드를 얻었다.

flowchart LR
  A["자료가 직선 여러 개 위<br/>(부분공간의 합집합)"] --> B["넘치는 딕셔너리<br/>점마다 몇 개만: 희소 코드"]
  B --> C["L1 페널티<br/>소프트 스레숄딩이 0을 만든다"]
  C --> D["ISTA<br/>경사 한 스텝 + 문턱 한 번"]
  D --> E["딕셔너리 러닝<br/>코드와 축을 번갈아"]
  E --> F["희소 오토인코더<br/>언어 모델 속 특징"]

정리 연습문제

물음. 평면의 점을 「축 세 개 가운데 몇 번 축, 계수 얼마」로 적는다. 계수 하나에 8비트를 쓰면 점 하나에 드는 비트는 얼마인가?

  • [ ] 16비트. 숫자가 둘이니 좌표 둘로 적을 때와 같다 〔틀림: 축 번호는 세 가지 가운데 하나라서 좌표 하나만큼 비트가 들지 않는다.〕
  • [x] 10비트보다 적다. 계수 8비트에 축 번호 2비트 이하가 붙는다 〔맞음: 번호는 몇 가지 가운데 하나인지만 알리면 된다. 세 가지면 약 1.6비트다.〕
  • [ ] 8비트. 축 번호는 비트가 들지 않는다 〔틀림: 받는 사람이 어느 축인지 알아야 하니 번호에도 비트가 든다. 축이 많을수록 번호가 비싸진다.〕

물음. 평면에 축 세 개를 두면 같은 점을 적는 계수가 끝없이 많다. 그 가운데 계수의 제곱합이 가장 작은 답을 선택하면 어떤 답이 나오는가?

  • [ ] 축 하나만 쓰고 나머지 계수는 0인 답 〔틀림: 제곱합을 가장 작게 하면 값이 여러 축에 조금씩 나뉜다.〕
  • [x] 세 축을 모두 조금씩 쓰는 답 〔맞음: 0이 많은 답을 얻으려면 L1 페널티처럼 다른 기준을 써야 한다.〕
  • [ ] 답이 하나뿐이라 선택할 것이 없다 〔틀림: 미지수가 식보다 많으면 답이 끝없이 많다. 어느 답을 선택할지는 기준이 정한다.〕

물음. 계수 하나를 값 0.8에 맞추면서 L1 페널티를 세기 0.1로 준다. 값 0.05에 맞추는 계수에도 똑같이 세기 0.1을 준다. 두 계수는 각각 얼마가 되는가?

  • [x] 0.7과 0 〔맞음: L1 페널티의 답은 소프트 스레숄딩이다. 문턱 0.1을 넘은 만큼만 남기고, 문턱보다 작은 값은 0이 된다.〕
  • [ ] 0.8과 0 〔틀림: 문턱을 넘은 값을 그대로 두는 것은 하드 스레숄딩이다. 소프트 스레숄딩은 넘은 만큼만 남겨 값이 뛰지 않는다.〕
  • [ ] 약 0.727과 0.045 〔틀림: 값을 일정한 비율로 줄이는 것은 제곱합 페널티(가중치 감쇠)다. 제곱합 페널티로는 0이 되는 계수가 생기지 않는다.〕

물음. 서로 직교하는 특징 넷의 가중치가 (0.8, 0.05, −0.3, 0.02)이다. 세기 0.01인 L1 페널티를 주면 0이 되는 가중치는 몇 개인가?

  • [ ] 둘. L1 페널티를 붙이면 작은 가중치는 늘 0이 된다 〔틀림: 0이 되는 것은 크기가 문턱보다 작은 가중치뿐이다. 이번 문턱은 0.01이다.〕
  • [ ] 하나. 가장 작은 0.02만 0이 된다 〔틀림: 0.02도 문턱 0.01보다 크니 0.01이 남는다.〕
  • [x] 하나도 없다 〔맞음: 넷 다 문턱을 넘어 0.79, 0.04, −0.29, 0.01로 남는다. L1 페널티는 계수가 0에 머물 수 있는 폭을 만들 뿐이다.〕

물음. ISTA의 스텝 크기를 수렴이 보장되는 범위보다 크게 잡았는데, 어떤 신호 하나에서는 잘 수렴했다. 다른 신호에도 같은 스텝 크기를 써도 되는가?

  • [ ] 된다. 한 번 통했으니 이 딕셔너리에서는 늘 통한다 〔틀림: 보장 범위는 모든 신호에 통하는 범위다. 넘으면 신호가 어느 축을 쓰느냐에 따라 수렴, 진동, 발산이 결정된다.〕
  • [x] 보장되지 않는다. 신호에 따라 진동하거나 발산할 수 있다 〔맞음: 보장 범위 안에서는 목적이 스텝마다 줄어든다. 범위를 넘으면 그 보장이 사라진다.〕
  • [ ] 된다. 스텝 크기가 클수록 늘 빨리 수렴한다 〔틀림: 스텝마다 차이에 곱해지는 배율은 곡률이 큰 축에서 1보다 커질 수 있다. 곡률이 클수록 스텝을 줄여야 한다.〕

물음. 딕셔너리 러닝에서 「축은 길이 1」이라는 묶음을 빼고 L1 페널티를 주면 어떤 일이 생기는가?

  • [ ] 아무 일도 없다. 페널티는 계수에만 붙으니 축 길이와는 상관없다 〔틀림: 축을 네 배로 늘이면 같은 점을 계수 4분의 1로 적는다. 페널티도 4분의 1이 된다.〕
  • [x] 축을 한없이 늘이고 계수를 줄여 페널티를 0에 가깝게 만든다 〔맞음: 그러면 페널티가 희소함을 선택하지 못한다. 그래서 축을 길이 1로 묶는다.〕
  • [ ] 축이 길어질수록 페널티가 커져 축이 저절로 짧아진다 〔틀림: 페널티는 계수의 절댓값 합이라 축이 길어지면 오히려 준다.〕

막힌 곳

이 장의 코드는 모두 자료를 거의 그대로 되살리려 했다. 별 모양은 오차 0으로 적었고, 라쏘에서도 되살린 신호가 (2, 1, 1, 1)에서 (1.5, 0.833, 0.833, 0.833)으로 달라진 것을 계수를 줄인 대가로 받아들였을 뿐, 되살린 것과 원래 신호의 차이를 얼마나 허락할지 처음부터 정하지는 않았다.