"gzip beats BERT" 논문의 숫자는 왜 어긋났나?

 (kenschutte.com)
1P by GN⁺ | ★ favorite | 댓글 1개
  • Jiang et al.의 “Low-Resource” Text Classification 논문에서 주목받은 gzip 기반 kNN 분류기 성능이 일반적인 kNN 정확도가 아니라, k=2에서 top-2에 가까운 방식으로 계산됐을 가능성이 있음
  • 공식 저장소의 experiments.py 안 calc_acc는 동률 후보 중 정답 라벨이 하나라도 있으면 정답으로 처리해, 가까운 두 학습 샘플 중 하나만 맞아도 성공으로 계산됨
  • 첫 4개 데이터셋의 “Full” 컬럼을 다시 계산하면 여러 수치가 바뀌며, KirundiNews에서는 gzip 방법이 최고 성능에서 최저 성능으로 내려감
  • 별도 재구현 결과 공식 코드 출력은 top2와 항상 같았고, k=2 동률을 가까운 샘플 우선으로 풀면 사실상 k=1과 같은 결과가 됨
  • rand==True 옵션은 random.choice로 동률을 깨지만 논문 결과에는 쓰이지 않은 것으로 보이며, SogouNews는 데이터 크기 때문에 아직 실행되지 않음

논문 결과 재현 중 드러난 정확도 계산 문제

  • 대상은 Jiang et al.의 “Low-Resource” Text Classification: A Parameter-Free Classification Method with Compressors로, gzip 기반 방법이 여러 신경망 기반 방법보다 높은 성능을 보인 표가 Twitter에서 주목받음
  • 공식 소스 코드를 재현하는 과정에서 kNN 분류기의 정확도 계산 방식이 일반적인 방식과 다르게 동작하는 지점이 확인됨
  • 특히 k=2에서는 정상적인 kNN(k=2) 정확도라기보다 top-2 정확도에 가까워, 논문 방법의 성능이 더 높게 잡힐 수 있음

k=2 kNN에서 동률이 문제가 되는 이유

  • 논문 방법은 kNN classifier를 사용하며, Appendix C에 따르면 모든 실험에서 k=2를 사용함
  • k=2 분류는 테스트 샘플마다 가장 가까운 학습 샘플 2개를 찾기 때문에 라벨 상태가 단순함
    • 두 라벨이 같으면 해당 라벨을 예측하며, 결과적으로 k=1과 같은 답이 됨
    • 두 라벨이 다르면 1:1 동률이 생기므로, 가까운 샘플 우선 같은 별도 동률 해소 규칙이 필요함
  • 동률을 무작위로 깨면 1:1 동률의 절반에서는 더 먼 샘플을 고르게 되어, k=1보다 나아지기 어려움

calc_acc가 동률을 처리하는 방식

  • 문제 지점은 experiments.py의 calc_acc 메서드임
  • 코드 흐름은 sorted_pred_lab에 top-k 샘플의 라벨과 카운트를 모으고, 라벨별로 묶은 뒤 카운트 기준으로 정렬함
  • 가장 높은 카운트와 동률인 라벨들을 순회하다가, 그중 하나라도 테스트 라벨과 같으면 if_right = 1로 설정되어 정답 처리됨
  • k=2에서 서로 다른 두 라벨이 각각 1표를 받으면, 두 후보 중 하나가 정답인지만 확인하는 셈이 됨
  • 이 결과는 ImageNet에서 말하는 top-k 정확도와 비슷하지만, 여기서는 선택된 k개 라벨이 아니라 k개 학습 샘플을 기준으로 한다는 차이가 있음
  • 이 메서드는 임의의 k를 받지만 모든 k에서 top-k를 계산하지는 않으며, k=2일 때 모든 후보가 최대 카운트 1로 묶이는 특수한 상황이 생김
  • calc_acc에는 rand 플래그가 있고 rand==True에서는 random.choice로 동률을 깨지만, 논문 결과에는 사용되지 않은 것으로 보임

재계산된 정확도 변화

  • 첫 4개 데이터셋의 “Full” 컬럼에서 논문 수치와 수정된 knn2d 수치는 다음과 같음
구분 KinyarwandaNews KirundiNews DengueFilipino SwahiliNews
논문 0.891 0.905 0.998 0.927
수정 knn2d 0.835 0.858 0.999 0.850
  • 다섯 번째 데이터셋인 SogouNews는 크기가 커서 아직 실행되지 않음
  • 이 차이로 실험 해석이 크게 바뀌며, KirundiNews에서는 gzip 방법이 최고 성능에서 최저 성능으로 내려감

별도 구현으로 확인한 결과

  • 별도 구현은 두 가지 동률 해소 전략을 사용함
    • r: 무작위 선택
    • d: 동률이 없어질 때까지 k를 줄임
  • 재구현 결과는 다음과 같음
방식 kinnews kirnews filipino swahili 설명
table5 0.891 0.905 0.998 0.927 논문 표 수치
code 0.891 0.906 1.000 0.927 npc_gzip 저장소 사용
top2 0.891 0.906 1.000 0.927 top-2
knn1r 0.835 0.858 0.999 0.850 kNN, k=1, 동률 무작위
knn1d 0.835 0.858 0.999 0.850 kNN, k=1, 동률 시 k 감소
knn2r 0.828 0.807 0.851 0.842 kNN, k=2, 동률 무작위
knn3r 0.838 0.791 0.851 0.881 kNN, k=3, 동률 무작위
knn2d 0.835 0.858 0.999 0.850 kNN, k=2, 동률 시 k 감소
knn3d 0.843 0.794 0.904 0.883 kNN, k=3, 동률 시 k 감소
  • 검산 결과는 공식 코드가 무엇을 계산했는지 보여줌
    • table5는 code와 0.001 또는 0.002 이내로 가까워 논문 수치를 재현할 수 있음
    • code는 항상 top2와 같아, 공식 코드 결과가 별도 구현한 top-2 결과와 일치함
    • knn1r == knn1d이며, k=1에서는 동률이 발생하지 않음
    • knn2d == knn1d이며, k=2에서 동률을 첫 번째 샘플로 풀면 k=1과 같아짐
    • knn2r < knn2d이며, k=2의 1:1 동률에서 무작위 선택은 절반의 경우 더 먼 샘플을 택하게 됨

남아 있는 확인 사항

  • 더 많은 k 값을 포함한 새 재구현은 gzip-knn에 있음
  • DengueFilipino가 일부 경우 1.0처럼 매우 높은 이유는 후속 글 Part 2에서 다룸
  • table5와 code가 두 경우에서 약간 다른 이유는 아직 확인 과제로 남아 있음

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 저자들에게는 실망스럽겠지만, 훌륭한 반박이라고 봄
    머신러닝에서는 이런 실수를 하기가 정말 쉽고, 더 안 좋은 점은 미묘한 방법론 오류가 다른 공학·과학 분야처럼 대개 치명적 실패로 드러나는 게 아니라 미묘한 성능 변화로 나타난다는 것임
    나쁜 데이터가 학습 세트에 섞이거나 목표값 정보가 새어 들어가도 시스템은 그럭저럭 돌아가며, 결과만 살짝 오염됨
    기존 압축 알고리즘을 머신러닝에 적용하는 건 바라던 것과 달리 너무 공짜 점심처럼 느껴짐. 압축 알고리즘에 특별한 마법이 있었다면, 트랜스포머를 압축기로 쓰기보다 압축 알고리즘을 인코더로 썼을 것임

    • 이 점을 꼭 기억해야 함. 실수는 하기 쉬우니까 흔하고, 과학은 잡음이 많은 과정이지만 그 안에 신호도 있으며, 지금 보이는 것이 바로 동료 검토의 본질임
      그래서 학회·저널보다 공개 출판이 더 나은 동료 검토 형태라고 자주 주장함. 동료 검토는 동료가 내 작업을 검토하는 것이지, 학회나 저널이 내세우는 임의적이고 잡음 많은 기준이 핵심은 아님
      역사 대부분의 기간 동안은 이렇게 돌아갔고, 현대적 의미의 동료 검토는 1970년대 중반의 꽤 최근 개념임. 예전 저널은 오늘날 arxiv가 하는 것처럼 연구를 배포하는 임무에 더 가까웠음
      https://mitcommlab.mit.edu/broad/commkit/peer-review-a-histo...
      학회·저널을 없애자고 주장하는 또 다른 이유는, 그렇게 해야 재현 논문, 실패 논문 같은 중요한 작업을 적극적으로 장려할 수 있기 때문임. “새로움” 기준에 묶이지 않아도 되고, 사실 거의 모든 연구는 점진적임
      “출판”은 동료에게 내 작업을 전달하고, 그들이 결과를 검증하거나 반증하게 하는 일임
      다만 학회가 사람들을 모으고 협업을 촉진한다는 점은 좋음. 여기서 말하는 건 학회·저널을 연구의 타당성을 판단하는 수단으로 쓰는 것에 대한 비판임
      학회 시스템이 단지 연구와 커뮤니티를 초대하는 장이라면 전혀 문제없음. 저널도 이론적으로는 저자와 리뷰어 간 대화가 있다는 점에서 좋지만, 이것도 arxiv + github나 OpenReview로 쉽게 가능하다고 봄
    • 이미 그런 방식은 쓰이고 있음. 최소 기술 길이 원리와 엔트로피 기반 분류기를 찾아보면 됨
      성능은 나쁘지만 분명 존재하고 배포도 아주 쉬움. 비슷한 텍스트는 더 잘 압축되는 경향이 있어서 gzip을 표절 탐지에 쓰는 걸 본 적이 있음
      압축률을 스프링 모델의 가중치로 써서 시각화할 수도 있고, 네트워크 통신 메타데이터에도 적용 가능함
    • 많은 실험에서 맞는 말임. 원하는 결과를 얻고 싶은 욕구가, 실제로 얻은 것을 검증해야 한다는 필요를 쉽게 압도함
      특히 결과가 기존 생각을 확인해줄 때 더 그렇다
    • 최근 머신러닝을 많이 공부하고 있는데 이런 양상을 자주 봄. 소프트웨어 엔지니어로서 해온 거의 모든 것과 정반대처럼 느껴지는 또 하나의 지점임
      세미콜론 하나 빠뜨리면 즉시 오류가 남
      그런데 세 층 중 한 층의 기울기 계산을 잘못해도 가끔은 돌아갈 수 있음. 다만 결과가 이상해짐
    • 학술 연구 코드는 대체로 아마추어가 최대한 빨리 짠 엉망인 코드이고, 테스트도 거의 없으며, 그런 코드의 주된 산출물은 논문 인용을 쌓는 것임
      과학 논문이 절반으로 줄고 주의가 두 배가 되는 세상이 훨씬 더 많은 가치를 만들겠지만, 전체 시스템이 절망적으로 게임화되어 있음

  • 이 블로그 글을 쓴 사람임. 여기 쓴 내용에는 꽤 확신이 있지만, 놓친 게 있다면 저자들이 직접 설명해줘야 할 수도 있음
    방금 GitHub에 이슈를 올렸음: https://github.com/bazingagin/npc_gzip/issues/3

    • 글 맨 위에 주석을 추가하는 걸 고려해볼 만함. 많은 사람이 제목만 대충 훑고 “gzip 논문은 엉터리이고 gzip 접근은 별로다”로 받아들이는 듯한데, 실제로는 “gzip 접근이 심층신경망 모델보다 낫지는 않지만 대체로 경쟁 가능하고 실행 비용이 훨씬 싸다”에 가까워 보임
      논문 자체는 여전히 탄탄함
    • 논문의 제1저자이고 블로그 글을 읽었음. k=2를 고른 이유는 n^{1/2} 사용이 권장되었고, 5-shot 설정과 맞는 k를 고르고 싶었기 때문임
      하지만 이 선택이 좀 이상하다는 말은 맞음. 논문과 Twitter에서 말했듯 k 값이 달라지면 결과가 달라지고, 보고한 것은 얻을 수 있는 최대 결과였으므로 예측이 항상 맞는 이상적 상황을 뜻함
      W2V와 SentBERT에도 같은 전략을 썼음. 다만 이것이 top-2 정확도라는 뜻은 아님. 내가 아는 한 top-2 정확도는 예측된 상위 2개 클래스 중 하나가 맞으면 점수를 주는 것임
      그런데 지적했듯 kNN에서 k=2일 때 가장 가까운 이웃 2개가 같은 클래스를 가리키는 상황이 있고, 이 경우 top-2 정확도를 보고한다면 다른 클래스 후보 하나를 놓치게 됨
      시간이 나서 arxiv에 새 버전을 올릴 때, 다른 전략과 다른 k 값에 대한 결과를 추가하고 싶음. 블로그에서 말한 decrement 전략은 정말 좋고, 원한다면 저장소에 추가하고 싶음
      짧고 늦은 답변은 미안함. 아직 저장소를 확인하지 못했음. 내일 논문 심사 준비 중이라 끝나면 이슈에 답하고 해결하겠음
    • 재현해줘서 고맙고, 중요한 작업임
      다른 결과 표인 Table 3도 재현해봤는지 궁금함
      내가 이해한 게 맞다면 클래스가 2개뿐일 때 top-2 정확도는 1이 되지만, 클래스 수가 많아질수록 평균적으로 “일반” 정확도와의 차이가 점점 줄어듦. 그래서 데이터셋에 클래스가 많다면 Table 3 결과는 그렇게까지 크게 바뀌지 않을 것임
      어쨌든 20-newsgroups 데이터셋에서 top-2 정확도 0.685는, 문자조차 문자로 보지 않는 방법치고는 꽤 인상적임[1]. 토큰, n-그램, 임베딩 같은 자연어 처리 연구자들이 몇 년씩 쏟아온 좋은 도구들은 말할 것도 없음
      [1] 내가 이해한 gzip은 비트열만 다루며, 이는 단어, 즉 바이트 경계와 반드시 정렬되지 않음
    • 공개하기 전에 저자들에게 먼저 연락해봤는지 궁금함

  • Shopify에서 검색 관련성 실험을 할 때도 실수를 많이 했고, 저자들에게 공감함. 나도 공개적으로 망신당한 실수가 꽤 있음
    Shopify에서의 마지막 무렵에 좋은 과학에는 좋은 소프트웨어 엔지니어링이 필요하다는 걸 배웠음. 스택의 너무 많은 지점에서 실수하기 쉽기 때문임
    그래서 숫자를 신뢰하고 서로의 실험을 재현할 수 있도록, 엄격하고 테스트가 많고 품질 높은 실험용 소프트웨어를 만드는 데 시간을 많이 썼음
    일회성 평가 방법은 지양하려 했고, 새 방법을 만들면 평가 도구 모음에 추가한 뒤 그 지표가 무엇을 의미하는지 이해하기 위해 테스트했음
    당연해 보이지만, 이런 실험을 해본 내 경험상 안타깝게도 바라는 만큼 흔하지 않음. 회사는 속도를 원하고, 통계적으로 깊게 생각하거나 내부 도구를 만드는 일은 대부분 윗선의 이해관계와 잘 맞지 않음

    • “좋은 과학에는 좋은 소프트웨어 엔지니어링이 필요하다”는 말은 산업 연구의 긍정적인 면임
      첫째, 더 많은 소프트웨어 엔지니어링 전문성을 쓸 수 있고, 둘째, 주장 과장을 덜 하게 되는 유인이 있음. 작동한다고 말하면 실제 운영 환경에 넣으라는 기대를 받기 때문임

  • 이 블로그 글이 공개되어서 좋음
    나도 이런 작은 프로젝트를 정말 많이 하는데, 심지어 논문의 문제를 보여주는 이런 작업도 빛을 보지 못할 때가 많음. 보통 잠깐 소리만 내고, 하드디스크에 묻힌 채 끝남
    그래서 이렇게 내놓아줘서 고마움

    • 요즘은 Twitter를 저비용 블로그처럼 쓰기 시작했음
      이런 작업에 하루를 쓰고 나면 보통 블로그 글을 실제로 쓸 힘이 없어서 아깝게 느껴짐. 그래도 짧은 Twitter 스레드를 쓰는 정도는 대체로 가능함

  • 이 결과를 보게 되어 정말 반가움. kNN + 분류 작업 + 순수 텍스트 유사도 기반 분류는 결과가 유리하게 쌓이기 쉬운 조합임
    이 논문을 두고 고소해하는 반응은 자연어 요소가 임베딩에서 핵심적으로 중요하다는 점을 오해함. 단어를 공유하는 문구는 분류도 잘 되고 GZIP도 잘 되므로, GZIP을 대체 분류기로 쓸 수는 있음
    BERT나 임베딩의 기적은 단어를 공유하지 않아도 된다는 데 있음. 예를 들어 “what is my safe passcode?”는 “my lockbox pin is 1234”와 강하게 맞지만, “my jewelry is stored safely in the safe”와는 그렇지 않음
    LLM에서도 이 점이 중요함. 많은 사람이 텍스트 유사도용 임베딩을 쓰는데, 실제로는 질문과 그 답을 담은 문서가 상관되도록 학습된 SBERT 모델을 써야 함
    전체 토끼굴은 https://www.sbert.net/에서 볼 수 있음
    이전 글: Should you use OpenAI's embeddings? Probably not, and here's why. https://iamnotarobot.substack.com/p/should-you-use-openais-e...
    HN 논의: https://news.ycombinator.com/item?id=35377935

    • 공정하게 말하면, 원래 과제는 kNN+압축 같은 방식이 잘될 가능성이 있는 곳, 즉 도메인 밖 + 저자원 환경으로 의도적으로 선택된 것임
      이런 조건에서는 학습 입력이 너무 희소해서 매개변수가 많은 모델이 좋은 임베딩을 학습하기 어려울 수 있음
      전통적인 도메인 내 대규모 데이터 분류 설정에서는 압축 같은 비매개변수 방법이 학습된 표현을 이길 가능성이 없음

  • 저자들이 왜 분류기로 kNN을 골랐는지는 명확하지 않았음. 거리 행렬을 만들었다면 다차원 척도법으로 행렬을 요인으로 바꾼 뒤, xgboost 같은 트리 알고리즘을 쓸 수 있었고, 그러면 kNN보다 더 많은 정보를 활용해 훨씬 나은 결과를 냈을 가능성이 큼
    LZ 계열 압축기보다 훨씬 좋은 PAQ 압축 알고리즘도 쓸 수 있었음. 이런 선택들이 결과를 크게 개선해 원래 결론에 도달하게 했을 수도 있음
    이 논문에서 좋았던 점은 압축 알고리즘을 추상화했다는 점이고, 덕분에 p(x) ~ K^(-|x|) 관계에서 압축으로 또 무엇을 할 수 있을지 생각하게 됨. 여기서 K는 알파벳 크기, |x|는 문자열 x의 길이이며, 최적 부호화를 가정함
    예를 들어 각 응답의 요인을 별도 문서로 묶고, 논문과 같은 방식으로 다음 샘플을 가장 잘 압축하는 문서를 찾아 클래스를 정하는 전통적 분류도 가능하겠다고 떠올랐음. 일종의 압축 알고리즘을 이용한 지도 분류임
    압축기가 해당 데이터셋의 최적 부호에 가까울수록 더 잘 작동할 것임
    순서열 예측 방식도 구현은 마찬가지로 간단함
    기분 좋은 놀라움이었음

  • 압축 알고리즘이 어떻게 LLM을 이길 수 있는지 설명해줄 수 있나? 말이 더 낫다는 걸 그래피티와 비교하는 것처럼 들림
    답이 어딘가에 있을 것 같지만 AI에 익숙하지 않아서 도무지 이해가 안 됨

    • 일반적으로 압축 = 모델 + 엔트로피 부호화임
      모델의 역할은 다음에 올 것을 예측하는 것이고, 엔트로피 부호화기의 역할은 예측과 실제 다음 값의 차이를 인코딩하되, 가능성이 높은 결과가 가능한 한 적은 비트를 쓰게 만드는 것임
      모델이 정확할수록 현실과 예측의 차이가 작아지고, 엔트로피 부호화기가 필요한 비트 수도 줄어서 압축이 좋아짐
      단순한 압축 알고리즘은 “같은 바이트를 10번 봤다면 11번째도 같을 가능성이 높다” 같은 단순 모델을 가짐. 하지만 LLM도 모델로 쓸 수 있음. 가장 그럴듯한 단어로 텍스트를 완성하는 것이 LLM이 하는 일이기 때문임
      여기서는 반대로 했음. 압축에 모델을 쓰는 대신 몇 가지 요령으로 압축 알고리즘을 모델처럼 쓴 것임. 압축 알고리즘이 결과를 더 적은 비트로 인코딩할 때 가장 가능성이 높은 결과로 보는 방식임
      원 논문 저자들은 일부 작업에서 gzip에서 뽑아낼 수 있는 단순 모델이 훨씬 복잡한 LLM을 이긴다고 보였음
    • 언어 모델은 단어열의 확률 P(w_1, ..., w_n), 또는 동등하게 P(word | context)를 추정함
      압축에서는 확률이 높은 단어열에 더 짧은 코드를 배정해야 하므로 직접적인 관계가 있음. 확률을 바탕으로 이런 코드를 만드는 잘 알려진 방법이 허프만 부호화임
      단어 빈도를 쓰는 통계적 언어 모델이든, 확률 추정에 LLM을 쓰든 성립함. 언어 모델이 좋을수록, 즉 퍼플렉서티가 낮을수록 압축 결과가 짧아짐
      반대로 압축 알고리즘은 코드 길이를 통해 암묵적으로 언어 모델을 정의한다고도 말할 수 있음. 예컨대 중복 문자열이 무작위 잡음보다 더 가능성이 높다고 가정하는 셈임
    • gzip 방식의 직관은 이렇음
      ABC를 압축하면 X바이트가 됨. 이어서 ABCABC를 압축하면 2X바이트가 되지 않음. 이어 붙인 두 문자열이 비슷할수록 필요한 바이트 수가 줄어듦
      ABCABD는 ABCABC보다 더 크지만 ABCXYZ보다는 작을 것임
      BERT는 오늘날 기준으로는 매우 작은 LLM이고, 우리가 요즘 많이 접하는 수십억 매개변수 규모 모델보다 성능이 약하다는 것도 알고 있음
    • 압축은 지능과 동등함
      https://mattmahoney.net/dc/rationale.html
    • 매우 제한된 작업임. 문서 하나를 받아 예컨대 10개쯤 되는 범주 중 하나로 분류하는 것임
      특정 단어를 감지하는 식의 방법도 경우에 따라 꽤 잘할 수 있음. 잘 압축되는 대상에는 공통 부분 문자열이 자주 나타남

  • 이게 사실이라면, 그 논문에 대해 거창한 말을 했던 사람들이 이제 어떻게 조용히 흔적을 지우는지 보고 싶음
    특히 LinkedIn과 Twitter 인플루언서들을 보고 있음
    사실이 아니라면 내가 멍청해 보이겠지만, 기사를 대충 훑기만 했음

  • 분류기로서의 Gzip은 놀라울 정도로 좋고, 신경망의 기준선으로 써야 함

  • 참고로 블로그가 2022년에 멈춰 있는 것 같음
    글 날짜가 2022년 7월 17일로 되어 있음

    • 고마움. 곧 고쳐질 것임. 날짜를 손으로 쓰면 이렇게 됨...
답변달기