0. 들어가기 앞서

• 본문은 ML2에서의 인턴십 후반기에 진행한 survey와 약간의 사견을 요약한 자료입니다.
• 제한된 기간 동안 조사를 진행하였기에 정보가 정확하지 않을 수 있습니다.

1. Introduction

What’s Symbolic Expression

이 글에서 Symbolic Expression(Sexp)은 수식을 기호로 표현한 것을 말합니다. 수식은 다양한 방식으로 표현될 수 있습니다. 라는 수식을 예시로 생각해 봅시다. 수식을 만족하는 점들을 샘플링해서 얻은 등의 입출력 쌍으로 수식을 표현할 수도, 또는 아래의 그림과 같이 수식을 그래프로 바꾸거나 단순한 문자열로 표현할 수도 있습니다. 이 중에서 그래프나 문자열로 기호를 유지해서 표현한 것을 Symbolic Expression이라 부르고자 합니다.

Figure 1. Symbolic Expression을 Tree로 나타낸 모습

Symbolic Simplifier

Symbolic Simplifier는 수식의 절대적인 길이를 줄이는 함수입니다. 간단한 예로는 의 상수부를 계산해 로 줄이는 경우가 있고 조금 더 복잡한 예로는 를 로 정리하는 것까지 들 수 있습니다. 필요에 따라서는 수식의 절대적인 길이가 아닌, [Figure. 1]과 같이 표현한 2진 트리의 depth를 낮추는 것을 목표로 하는 simplifier도 있을 수 있습니다.

Symbolic Expression in DL

Symbolic Expression은 딥러닝의 다양한 응용분야에서 사용되고 있습니다. 수학을 딥러닝을 통해 해결하고자 하는 분야나 regression을 연구하는 분야에서도 쓰이고, AutoML에서도 자주 쓰이곤 합니다. 아래에는 Loss Design과 간단한 Mathematical problem에서 사용되는 경우를 소개하였습니다.

Symbolic Expression in Loss Design

Loss design은 신경망을 학습시키기 위한 Loss 함수를 설계하는 분야로, AutoML의 한 연구분야입니다. 예를 들어 Object detection이나 Pose Estimation 같은 분야에서는 좋은 성능을 위해 다양한 형태의 Loss를 사용합니다. 이렇게 기존에 있는 다양한 Loss 중 어떤 것을 사용할지 고르거나, 새롭게 더 좋은 Loss를 만드는 과정은 굉장히 heurisitic하고 시간을 많이 소모합니다. 이 과정을 자동화하여 최적의 Loss를 찾아주는 방법을 얻는 것이 Loss design의 연구 방향입니다. 초기에는 [Figure. 2]의 AM-LFS와 같이 Cross Entropy Loss를 변형해서 조절이 가능한 hyper-parameter를 만들고, 이를 최적화하는 연구가 있었습니다.

Figure 2. The mechanism of AM-LFS [C. Li et al.]

이런 방식은 간단하게 학습시킬 수 있지만 표현 가능한 함수의 형태가 적은 단점이 있습니다. 예를 들어 AM-LFS의 경우, Cross Entropy Loss 바탕에 hyper-parameter를 추가하고 최적화 한 것이라 Cross Entropy Loss의 틀을 벗어날 수 없습니다. 이는 탐색되는 함수의 형태가 제한됨을 의미하고, 충분히 좋은 Loss를 찾지 못하는 결과로 이어질 수 있습니다. 이를 피하기 위해 바탕이 될 함수와 조절할 parameter를 잘 정의한다면 문제가 적겠지만, 정의하는 과정에서 우리의 지식이 섞이게 되고 학습 방향이 편향될 여지도 있습니다.

Symbolic Expression은 임의 길이의 수식을 자유롭게 표현할 수 있어서 형태의 제약이 없고 자유도가 높다는 장점이 있습니다. 하지만 Symbolic Expression의 고정되지 않은 입력 크기를 다룰 수 있는 신경망만 사용할 수 있다는 단점도 있습니다. 이런 종류의 신경만 중에서 주로 쓰이는 방식은 자연어 처리에 쓰이는 seq2seq 모델이나 tree2tree 모델이 있습니다. 약간 분야는 다르지만 이와 관련된 예시를 소개하자면, 더 좋은 activation function을 찾기 위해 RNN을 사용해서 symbolic expression을 처리한 연구가 있습니다. [Figure. 3]

Figure 3. RNN to generate a new activation function, SWISH [P. Ramachandran et al.]

Genetic Programming을 사용하는 것처럼 신경망을 사용하지 않는 방법도 존재합니다. ICLR2021에 발표된 [Peidong Liu et al.]에선 [Figure. 4]에서처럼 evolutionary search를 통해서 object detection의 loss design을 연구하였고, 유사한 방법으로 기계 학습 프로그램[E. Real et al.]을 만든 연구와, 강화학습 알고리즘을 향상시키는 연구[JD Co-Reyes et al.]도 있습니다.

Figure 4. CSE-AutoLoss Example. It uses symbolic expression and evolutionary algorithms

Symbolic Expression in Mathematical Problem

수학적 문제를 딥러닝을 통해서 풀려는 시도를 할 때도 Symbolic Expression은 쓰입니다. Symbolic Expression을 그대로 인코딩하여 배열로 만드는 경우도 있고, parse tree를 통해서 인코딩 후 N-ary tree나 binary tree의 형태로 만들기도 합니다.

Symbolic regression

데이터 포인트들을 입력받고, 해당 데이터가 따르는 내재된 함수를 추출하는 연구입니다. 기존의 regression이 linear, polynomial regression과 같이 어떤 틀 속에서 최대한 비슷한 함수를 얻는 접근이라면, Symbolic regression은 임의 형태의 함수를 반환할 수 있기에 차이를 보입니다. 최근의 연구를 하나 소개하자면, [BK Petersen et al.]의 연구가 있습니다. [Figure. 5]에서 보여지듯 policy gradient와 autoregressive RNN을 통해서 주어진 데이터가 따르는 관계식을 추출하는 연구로 Symbolic Expression의 형태로 관계식을 반환합니다.

Figure 5. [BK Petersen et al.] the mechanism of sampling expression from data with RNN in DSR.

ODE/PDE solver

미분 방정식의 해를 찾기 위해 딥러닝을 사용하는 시도도 많이 있습니다. 그 중에는 Numerical한 해를 구하려는 접근도 있지만, 뒤에 소개할 [G. Lample et al.]의 연구와 같이 Symbolic Expression과 자연어 처리에 쓰이는 기술을 융합해서 해를 찾으려는 시도도 있습니다.

이와 같이 다양한 분야에서 Symbolic Expression을 사용해서 문제를 해결하려 하고 있습니다. 이제 우리는 이 포스트의 주제인 Symbolic Simplifier로 눈을 돌려 ‘무엇을 할 수 있는지', ‘어떻게 할 수 있는지'등에 대해 생각해보려고 합니다.

Why Symbolic Simplifier?

Computer Vision과 관련된 연구들 중 많은 분야에서 ImageNet으로 학습된 pretrained image classifier를 사용합니다. 이 classifier는 feature extractor로 다양하게 활용되는데, 주로 데이터가 적은 문제 상황에서 학습을 보조하거나 detection과 같은 응용 주제의 backbone으로 쓰이고 있습니다. 많은 비전 연구들이 이런 식으로 feature extractor를 활용해 단기간에 좋은 성능을 보이는 결과를 도출합니다. 비슷하게, Symbolic Expression을 쓰는 연구에도 수식들의 보편적인 특징을 추출할 수 있는 feature extractor가 있다면 큰 도움이 될 것입니다.

Feature extractor를 만들기 위해서 가장 먼저 떠오르는 것은 AutoEncoder입니다. 임의의 제한된 차원안에 수식들을 인코딩 할 수 있고 정답 레이블 없이도 학습이 가능하니 매력적인 선택지입니다. 하지만 단순한 AutoEncoder의 학습은 수식이 아닌 문자열을 인코딩 하는 것과 동일한 결과를 만드는 문제가 있습니다. 우리는 수식의 원리를 이해하는 feature extractor를 원하기에, 이 방식은 기대와 거리가 있습니다.

신경망이 (문자가 아닌) 수식을 학습하려면 어떤 특징을 강조해야 할까요? 저는 연산자의 원리를 학습시켜야 한다고 생각합니다. 덧셈의 원리나 뺄셈의 원리와 같은 연산자의 작동 원리를 이해할 수 있으면, 보다 고차원적인 작업을 위한 feature extractor로 사용할 수 있을 것입니다. 연산자의 원리를 학습시키는 좋은 방법 중 하나는 simplify하는 법을 학습시키는 것입니다. 수식의 길이를 합리적으로 줄이는 과정에서 신경망은 연산자와 숫자, 변수들의 관계를 학습하게 됩니다. 따라서 Symbolic Simplifier로 학습된 신경망은 좋은 feature extractor로 활용될 가능성이 있습니다. Symbolic Simplifier는 수식을 축약하는 기능 그 자체만으로도 의미가 있지만, 이렇듯 feature extractor로 쓰일 가능성도 있기에 중요한 연구 주제라고 생각합니다.

2. About Dataset

모든 딥러닝 모델은 학습시킬 데이터가 필요합니다. 물론 Symbolic Simplifier도 예외는 아닙니다. 다행히도 수식의 경우 우리가 직접 만들 수 있기 때문에 다른 분야에 비해 데이터에 대한 고민은 비교적 적다는 장점이 있습니다. 하지만 어떤 방법으로 수식을 만들어야 할까요?

여기선 데이터 생성과 관련된 3가지 방법을 살펴보고, 데이터셋과 관련한 중요한 이슈 중 하나인 data leakage에 대해 언급해보려고 합니다.

a. Dataset with Ground Truth

Ground Truth가 있는 수식 쌍을 만드는 쉬운 방법은, 임의의 수식들에 이미 알려진 simplify 규칙을 반대로 적용하는 것입니다. 예를 들어서 가 있다면 로 늘린 다음 데이터에 추가하는 방식입니다. 반대로 임의의 수식을 만들고 Mathematica나 SymPy의 함수를 이용해서 수식을 simplify하고서 그 결과를 GT로 만들 수도 있습니다.

위와 같이 만든 데이터로 모델을 학습시키면, 성능의 기대 상한이 데이터 생성에 쓰인 알고리즘의 성능으로 제한되는 단점이 있습니다. 즉, 모델이 데이터를 만들 때 사용한 규칙과 알고리즘을 학습해서, 기존 알고리즘 이상의 성능을 내기 어려울 수 있습니다.

그럼에도 전반적으로 보면 지도 학습은 보다 빠르고 간단하게 학습시킬 수 있다는 점에서 이점을 가집니다. 이미 알려진 알고리즘의 interpolation만 할 수 있더라도, 수식의 원리를 이해한 feature extractor란 목적에는 충분히 부합하기에 유용한 접근입니다. 아래에 두가지 대표적인 simplify() 함수들을 소개하였습니다. 이들을 통해 우리는 학습용 데이터의 Ground Truth를 만들 수도 있고, 학습시킨 모델의 성능 비교에도 사용할 수 있습니다.

SymPy

SymPy는 simplify()라는 함수를 지원합니다. 예시와 같이 일부 경우에 대해 수식을 보다 간단한 형태로 정리를 해줍니다. 아래처럼 감마함수에 대해서도 작동을 하지만, 종종 간단한 simplification을 지원하지 않는 경우도 있습니다. 예를 들어, 을 넣어주면 로 줄어들기를 기대할 수 있지만, 이를 처리해주지 못합니다.

>>> simplify(sin(x)**2 + cos(x)**2)
1
>>> simplify((x**3 + x**2 - x - 1)/(x**2 + 2*x + 1))
x - 1
>>> simplify(gamma(x)/gamma(x - 2))
(x - 2)⋅(x - 1)

따라서 SymPy에서는 simplify()를 사용해보고, 잘 안되는 경우 상황에 맞춰서 아래의 함수들을 시도해보라고 이야기합니다. 다항식 입력의 경우 expand(), factor()나 collect()가 있고, 삼각함수의 경우 trigsimp()를 사용하면 보다 확실한 simplification이 가능합니다. 앞서 simplify()가 실패한 의 경우 factor()에 넣어주면 으로 줄여줍니다.

Mathematica

Mathematica도 simplify를 지원합니다. 기본적인 변환을 적용해서 수식을 단순화 하는 Simplify[expr,assum]와 더 넓은 범위의 연산(규칙)을 적용한 FullSimplify[expr,assum]를 통해서 수식을 간소화 해줍니다. 전자의 Simplify[]의 경우 줄여주는 대상이 다항식, 분수, 삼각함수와 지수 등으로 제약된 반면, FullSimplify[]의 경우 hyperbolic 함수나 감마 함수와 같은 특별한 함수를 사용해서 줄여주는 등 더 넓은 범위에서 적용할 수 있습니다.

b. Generating well-organized equations

“어떤 방향으로 수식을 줄여야 성공적인 simplifier인가?”는 명확한 정답이 없는 문제입니다. 우선 이 글에서는 수식의 길이를 많이 줄일수록 성공한 simplifier라고 보겠습니다. 그렇다면, 수식의 줄어든 길이를 reward로 설정한 강화학습 모델은 Ground Truth 없이도 성공적인 simplifier를 학습할 수 있을 것입니다. 이런 방식은 Ground Truth가 필요 없어 데이터 생성 과정이 더욱 간단하기에, 방대한 양의 데이터를 만들기 쉽다는 장점이 있습니다. 또한 사람이 미리 정해둔 simplify 규칙이 아닌 새로운 규칙을 학습할 가능성이 있다는 장점도 있습니다.

그렇다고 해서 임의의 수식을 넣어주면 합리적인 걸까요? 우리는 데이터셋을 구축할 때 균형을 항상 고려해야 합니다. 예를 들어 데이터셋의 대부분이 덧셈만을 가지고 있다면 우리의 simplifier는 덧셈만을 학습하게 되며, 뺄셈이나 곱셈 등과 같은 다른 연산에 대해선 학습할 수 없을 것입니다. 이처럼 균형잡힌 수식을 만드는 것은 중요하며 아래에 소개한 연구가 관련해 도움이 될 내용을 담고 있습니다.

Deep Learning for Symbolic Mathematics (G Lample et al.)

이 연구는 자연어 처리에 쓰이는 Transformer를 이용해서 ODE solver를 지도학습을 통해서 만드는 방법을 소개합니다. 해가 되는 수식을 만들고 대응되는 ODE를 만드는 방식으로 대량의 데이터셋을 구축했는데, 아래와 같은 조건 하에서 40M개의 데이터셋을 학습용으로 만들었습니다.

Figure 6. Search space of Lample et al.’s research.

저는 이 연구에서 random symbolic tree를 만드는 부분이 유용하다고 생각합니다. 위와 같이 다양한 연산자를 사용해 보편화된 수식을 만드는 법을 제시하였기에, 데이터 생성의 시작점으로 삼기 좋아 보입니다. 생성 과정 중에 동일한 의미를 가지는 수식의 중복을 제거하는 법과 균형있는 수식의 생성에 대한 고민도 담겨있어서 도움이 될 듯합니다.

c. Mathematics from Wikipedia

Distilling Wikipedia Mathematical Knowledge into Neural Networks Model [JT Kim et al.]

수식을 생성하는 지금까지의 내용과는 다르게 기존 수식을 이용해서 학습을 시킬 수도 있습니다. [JT Kim et al.]은 Symbolic regression 모델의 성능을 개선하기 위해 위키피디아에 쓰인 수식을 prior로 사용하는 연구를 하였습니다. 그 결과 특정 상황에서 성능 향상을 얻었는데, 이처럼 현실에 있는 수식을 데이터로 쓰기 위해 Wikipedia나 Arxiv를 크롤링 하는 것도 하나의 좋은 선택지로 보입니다.

d. About Data leakage

Can Neural Networks Learn Symbolic Rewriting? [B. Piotrowski et al.]

Symbolic Expression을 사용하는 연구는 대부분 데이터를 합성해서 사용하는데, 그만큼 의도하지 않은 data contamination이 발생하기 쉽습니다. 대표적인 예시가 test set과 train set에 변수 이름만 다르고 형태가 동일한 수식이 동시에 포함된 경우입니다. [B. Piotrowski et al.]는 symbolic expression에 관한 연구에서 있을 수 있는 data leak을 소개하며 이를 주의해야 한다고 말합니다.

[B. Piotrowski et al.]에서 논의 대상으로 가져온 연구는 앞서 소개한 Deep Learning for Symbolic Mathematics [G. Lample et al.]입니다. [G. Lample et al.]은 많은 수의 수식을 합성, 학습시켜 99% 가량의 높은 정확도를 가진 ODE solver를 학습시킨 연구입니다. 여기서 [B. Piotrowski et al.]은 99~97%와 같은 높은 성능의 결과에 대해, 의도치 않은 data leak에 의해 얻어진게 아닌가? 라고 의문을 제기합니다.

실제로 [G. Lample et al.]의 연구에 쓰인 수식의 상수들을 모두 CONST 토큰으로 대체를 할 경우, test set과 train set에 많은 데이터가 겹침을 아래 Table을 통해 확인할 수 있습니다. 학습에 쓰인 IBP, BWD, FWD 3가지 데이터셋 중 IBP의 경우 겨우 30%의 test 데이터만 새로운 형태임을 이야기 합니다.

Table 1. Number of unique (not overlapping with the training set) testing examples. It shows the possible data leak of the [G Lample et al.]'s data

Train과 test에 동일한 형태의 수식이 쓰였다는 것은, 결국 의도치 않은 데이터 유출이라고 주장하며, 이를 연구에서 고려해야 한다고 저자는 이야기합니다. Symbolic Expression을 활용하는 연구는 데이터를 직접 생성해서 연구를 하는 경우가 많기 때문에, evaluation 과정에서 이런 부분을 항상 경계하자는 주장은 좋아 보입니다.

3. Symbolic Expression Simplification with Deep Learning

이 문단은 기존의 Deep Learning(DL) 기반 Symbolic simplifier와 유사한 주제를 연구한 논문 세가지를 소개하고 있습니다.

a. Can Neural Networks Learn Symbolic Rewriting?

• ICML 2019 Workshop, AITP19 [B. Piotrowski et al.]

Background

본 연구는 제목에서 볼 수 있듯이, 수식을 동일한 의미를 갖게 재구성하도록*(꼭 simplify일 필요는 없음)* 신경망을 학습시킬 수 있느냐에 대한 연구입니다. 이 이전에 자연어 번역에 쓰이는 seq2seq 모델을 이용해서 LaTeX으로 쓰인 수식을 프로그램으로 변환하는 연구가 있었는데, 이를 확장한 시도입니다. 저자들은 seq2seq 모델을 Sexp → Sexp에 적용해서 학습이 가능한지 확인하고자 하였습니다.

Model

모델의 경우 앞서 언급한 ‘LaTeX에서 프로그램으로 변환하는 연구’에서 쓰인 설정을 조금 고쳐 만들었습니다. 모델의 크기를 약간 줄여 128개의 cell로 구성된 두 층의 LSTM을 사용하였고 attention mechanism을 더했습니다. 연구 방향 자체가 "잘 연구된 자연어 번역 모델을 가져와서 수식을 이해시킬 수 있는가?" 이기에, 모델 선정과 튜닝에 대한 이야기는 짧고 데이터와 결과에 초점이 맞춰져 있습니다.

Dataset & Result

실험에는 2가지 데이터가 사용되었는데, 하나는 AIM 데이터셋이고, 다른 하나는 Polynomial 데이터셋입니다.

• AIM 데이터셋

  AIM(Abelian Inner Mapping) loop에 대한 증명 데이터로 학습 결과는 아래의 표에서 확인할 수 있습니다. 우선 학습 데이터가 1000개 이상으로 충분한 경우, 각 규칙에 대해서는 90% 이상의 정확도로 잘 학습합니다. 이는 LSTM 모델이 수식에서 규칙을 추출하는 능력이 있음을 나타냅니다.

Table 2. result of rewriting

추가적으로 모든 규칙을 섞어서 학습시키고 테스트를 했을 때, 83%의 정확도가 나옵니다. 약간의 성능 저하가 있지만, 모델이 여러 규칙을 동시에 학습하고 어떤 규칙을 적용할지 고르는 과정도 학습할 수 있음을 보여주는 결과입니다.

• Polynomial 데이터셋

  간단하게 임의의 형태로 수식을 만들고, 해당 수식의 괄호를 전부 전개해서 대응되는 쌍을 만드는 형식으로 데이터를 만듭니다. 30만개의 수식을 만들었고, 최대 길이가 50을 넘지 않도록 제한하였습니다. 사용한 상수와 변수의 개수에 따라 서로 다른 데이터셋을 만들었는데, 아래의 표에서 그 결과를 볼 수 있습니다.

Table 3. Result of the polynomial normalization case.

• 여기서 symbolic expression을 어떻게 RNN에 넣어줬을까요?

간단합니다. 그냥 수식이 적힌 순서대로 괄호와 콤마까지 모두 인코딩해서 넣어줍니다. 예를 들어 [G Lample et al]에서 사용한 [A + B] 를 [+ A B]의 순서로 바꿔주는 방식이나 후술할 연구에서 사용하는 tree 구조를 사용하지 않고, 괄호를 하나의 연산자로 인코딩하여 사용합니다. 개인적으로 이 요소가 낮은 성능의 원인이 되지 않았나 생각해 봅니다.

Conclusion

이 연구는 자연어 번역에 쓰이는 모델이 수식을 재구성하는 규칙을 학습할 수 있고, 모델이 내재적으로 규칙을 고르는 것도 가능함을 보입니다. 조금 확장해서 말하면, 딥러닝을 통해서 simplifier를 만드는 것이 가능한 일임을 보인 연구라고 생각할 수 있습니다.

동시에 이 연구는 여러 부분에서 개선의 여지를 보입니다. 간단한 모델의 구조와 데이터셋의 단순성, 그리고 괄호와 콤마까지 인코딩하는 입력 방식 등이 눈에 들어오는 개선 가능한 부분이라 생각합니다. 실험 결과 일부 상황에서 90%에 못미치는 정확도를 보이는데, 언급된 부분들에 개선이 있다면 더 좋은 결과를 보이지 않을까 생각합니다. 성능에서 아쉬움이 있고 목표한 방향성도 약간 다르지만, Symbolic Simplifier가 활발한 연구분야가 아닌 만큼, 이 논문은 여전히 연구의 시작점으로 의미가 있다고 생각합니다.

• more informations about dataset
  ref1 : Loops with Abelian Inner Mapping Groups: An Application of Automated Deduction
  doi: 10.1007/978-3-642-36675-8\ 8. URL https://doi.org/10.1007/978-3-642-36675-8_8.
  AIM data
  https://github.com/BartoszPiotrowski/rewriting-with-NNs/tree/master/data/AIM
  polynomial data
  https://github.com/BartoszPiotrowski/rewriting-with-NNs/tree/master/data/polynomial

b. Learning to Perform Local Rewriting for Combinatorial Optimization

• NeurIPS 2019 [X.Chen et al.]

Background

이 연구는 조합최적화를 Local rewriting을 통해서 풀어보자는 방향을 제시하고 있습니다. NeuRewriter라는 모델을 강화학습을 통해 학습시켜, expression simplification, job scheduling과 vehicle routing 문제에서 좋은 성과를 보였다고 이야기합니다. 이 글에서는 expression simplification에 대한 부분만 떼어내서 다루고자 합니다.

Method

수식은 우선 아래의 그림과 같이 Tree의 형태로 표현이 됩니다. 앞선 연구에서 수식을 sequence로 다뤘던 것과 차별화된 부분입니다. 이렇게 Tree로 표현된 수식을 N-ary Tree-LSTM에 넣어서 각 노드들의 embedding을 얻습니다. 그 후 region-picker가 simplify하기에 가장 합리적인 sub-tree의 root-node를 선택합니다. 마지막으로 미리 정의된 rule-set에서 해당 sub-tree에 가장 합리적인 규칙을 선정하고, 이를 통해서 수식의 길이를 줄입니다. 이 과정을 계속 반복함으로 Sexp simplify를 진행할 수 있습니다.

Figure 7. The mechanism of simplification with NeuRewriter

Region-picker와 rule-picker의 경우 줄어든 수식의 결과를 보고, 이를 강화학습을 통해서 학습시킵니다. Actor-Critic 기반의 알고리즘을 사용하였다고 하는데, 이는 아래의 그림에서 볼 수 있듯이 크게 두 부분으로 나눌 수 있습니다. 우선 region-picker인 policy함수 는 Q-Actor Critic을 통해 학습시킵니다. rule-picker의 경우 A2C를 사용하며, 두 Loss를 일정 비율로 합한 값을 최종 Loss로 활용합니다.

Figure 8. We can check two policies of NeuRewriter. Region-Picker and Rule-Picker. Also there is a NN that encodes the current-state, so there are totally three different NNs.

Tree형태로 주어진 모델을 region-picker, rule-picker의 policy에 넣어주기 위해서 embedding을 해줘야 하는데, 이를 위해 treeLSTM을 사용합니다. 또한 전체 트리의 정보를 넣기 위해서, 전체 트리의 정보를 모두 담고 있는 root 노드의 임베딩된 값을 policy에 같이 넣어줍니다. Rule-picker와 score-predictor의 경우 간단한 Fully Connected Layer로 구성하였습니다.

Dataset & Rules

데이터의 경우 Halide라는 프로그래밍 언어의 랜덤 생성기를 기반으로 만들어져 있습니다. 아래의 예시에 나오는 연산자를 이용해 random한 수식을 만들었는데, 이는 boolean operator만을 고려하던 기존의 연구들에 비해 확장된 논의라고 이야기하고 있습니다. 그 밖에 상수의 경우 ±1024의 값을, 변수의 경우 최대 12개까지 포함되는 수식을 만들어 사용합니다.

Figure 9. operators included in Halide.

Rule-set의 경우 Halide에서 기본적으로 제공하는 rule-based rewriter에 포함된 규칙을 사용하였습니다. 추가적으로 uphill rule을 도입하였는데, 이는 수식의 길이를 증가시키는 규칙을 말합니다. 아래의 그림과 같이 Min/Max expansion을 통해 수식의 길이를 늘리는데, 일부 상황에서 수식의 길이를 더 줄일 수 있는 기회를 줍니다.

Figure 10. The example of simplification with uphill-rule

Result

성능의 비교를 위해 Heuristic-search, Halide-rule과 Z3(증명툴)의 simplify 함수를 통해 테스트를 진행합니다. 여기서 쓰인 Heuristic-search는 step마다 beam-search를 통해 수식을 최대한 줄이는 greedy한 방법입니다. Z3는 Halide rule-set보다 더 많은 rule을 포함하고 있기에, 보다 좋은 성능을 보일 것이라 기대합니다. 실험 결과는 아래 그림에서 확인할 수 있습니다.

Figure 11. Performance of NeuRewriter and other baselines(left). Performance of NeuRewriters(trained on expressions of different lengths) to evaluate generalization performance(right).

실험 결과를 살펴보면 NeuRewriter가 가장 좋은 성능을 보입니다. 그 다음으로 Z3 기반 방법이 뒤를 이었습니다. 특징적인 점은 greedy algorithm인 Heuristic Search가 꽤 우수한 성능을 보였다는 부분입니다.

Conclusion

결과에서 보듯 greedy한 방식을 취한 Heuristic Search가 Halide-rule 보다 좋은 성능을 보이고 있습니다. 그리고 NeuRewriter의 경우 Heuristic Search보다 25% 가량 높은 성능을 보이고 있습니다. 저는 이 성능의 차이가 NeuRewriter를 학습시킬 때 포함한 uphill 규칙에 의한 것이 아닐까 생각합니다. Uphill 규칙은 잠깐의 길이 증가를 허락하는 것이니, greedy search에 patience를 넣어준 것과 비슷한 접근입니다. 따라서 조금 더 깊게 beam search로 탐색을 하면 Heuristic Search가 느릴지언정 NeuRewriter와 비슷하거나 더 높은 성능을 얻을 수 있지 않을까 생각합니다.

NeuRewriter는 기존 프로그램이나 greedy한 방법보다 더 빠른 속도와 더 좋은 성능을 보이지만, 이와 동시에 하나의 한계점을 가집니다. 바로 인간이 정해둔 rule-set을 넘어서지 못한다는 점입니다. NeuRewriter는 규칙은 정해져 있고, 어떤 규칙을 언제 어디서 적용하냐를 기계학습을 적용해 해결하자는 방식의 접근입니다. 사람이 만든 규칙이 고정되어 있어 모델에게 주어진 자유도는 제한되고, 이런 점이 성능을 제약하지 않을까 하는 의문을 들게 합니다.

c. Deep Symbolic Superoptimization without Human Knowledge

• ICLR 2020 [H. Shi et al.]

  Background

  3.b의 연구가 ‘주어진 rule-set 중에 어떤 규칙을 어디에 적용할지 신경망이 골라주는 연구'라면, 이번 연구는 아무런 rule-set 없이 스스로 학습하는 방법을 제시합니다. 사전에 정의된 rule-set이 없기 때문에, 제목 그대로 사람의 지식이 들어가지 않고 신경망이 스스로 학습하는 것에만 의존해 simplify를 수행합니다.
  
  

Dataset

본 논문의 저자 목록을 보면 앞선 연구의 저자가 그대로 있음을 볼 수 있습니다. 실제로 모델에서도 굉장한 유사성을 보이고 있고, 데이터의 경우 앞선 연구의 것을 그대로 사용하고 있습니다. 특기할 부분은 기존의 -1024, 1024의 상수를 symbol로 변경해서 one-hot 인코딩 한다는 점입니다. 아래의 표에서 수식을 만들기 위해 사용한 요소들을 볼 수 있습니다.

Table 4. The vocabulary of the symbols and operators that are used to construct dataset for pretrain

본 연구에서는 rule-set이 없기에 학습에 어려움이 생길 것을 고려해서 학습을 두 단계로 나눠 진행합니다. 1단계는 depth가 4 이하인 짧은 수식들을 이용해서 pretrain을 시키는 과정입니다. 비교적 깊이가 얕아서 random한 시도로도 빠르게 학습될 수 있기 때문에, 초기 sparse한 search space의 문제를 해결해주는 역할을 합니다. 짧은 입력 데이터를 random하게 줄여가며, valid하면 보상을 얻는 방식으로 unsupervised하게 진행됩니다. 이 과정에는 rule-set을 필요로 하지 않기에, 임의의 데이터에 대해 확장하기 편리할 것입니다.

Method

본 연구에서 사용하는 모델을 저자는 HISS (Human Independent Symbolic Superoptimization)라고 부릅니다. 여기서도 모델을 HISS로 부르겠습니다.

Figure 12. HISS architecture, consists of TreeLSTM Encoder, TreeLSTM Decoder and selector .

위의 그림에서 3가지 색으로 모델을 표현했듯이, 모델은 세 부분으로 구성됩니다. Tree Encoder, Tree Decoder와 Selector입니다. 앞의 두 부분은 AutoEncoder와 비슷한 느낌으로, Encoder는 Tree를 한 공간에 embedding하고 Decoder는 이를 다시 Tree로 복원을 합니다. Selector의 경우 어떤 Tree를 decoding할지 선택하는 신경망으로, 주어진 수식 중에 길이가 줄어들 sub-tree를 찾는 역할입니다. Decoder의 경우 앞서 이야기한 것 처럼 embedding을 입력으로 받아, 최종적으로는 더 줄어든 수식을 반환하는 역할을 가집니다.

학습 초기, 즉 1단계에는 Encoder와 Decoder만을 짧은 수식에 대해서 학습을 시킵니다. 이 과정에 sub-tree Selector는 사용하지 않습니다. 그 대신 root-node를 Decoder에 넣고서 나온 결과 수식이 의미가 같고 길이가 더 짧은 경우만을 이용해서 학습시킵니다. Depth가 낮은 데이터를 사용하기에 root-node를 넣어도 빠르게 학습시킬 수 있습니다. 이 과정을 통해서 Encoder, Decoder를 조금 학습시킵니다.

초기 pretrain을 통해 짧은 수식에 대해 학습이 끝나면, Halide 데이터셋을 이용해서 본격적인 학습에 들어갑니다. 이 경우 Selector도 같이 학습되며, 이 부분이 학습의 90% 이상을 차지합니다. 학습에는 기초적인 REINFORCE[Williams, 1992]를 사용하였으며 tree의 노드 수를 줄이는 방향으로 학습됩니다. RTX2080 기준 2주일의 학습시간이 걸리지만, 실제로 실험을 해본 결과 몇 가지 제약(배치사이즈, 프로그램 최적화)때문에 긴 시간이 걸린 것으로 보입니다.

Result

• Human Independent
  아래의 그래프는 전체적인 성능을 이야기하고 있습니다. 초록색은 MCMC, 노란색은 MCTS라는 대조군입니다. 두 방법 모두 random한 접근을 통한 simplify로, 여기서의 비교에 쓰인 데이터셋은 pretrain에 사용한 깊이 4 이하의 수식입니다. Random한 변형을 기반으로 한 방법보다는 HISS의 성능이 좋음을 보여줍니다.

Figure 13. Comparison with human-independent methods in terms of hit rate (left), expression length reduction (middle), tree size reduction (right), on Traverse Equivalence dataset( = short-length data). HISS shows better result than other MC-based random approaches.

• Human Dependent
  Human Dependent에서는 비교군으로 (NeuRewriter에서도 사용한) Halide rule-set과 Z3을 사용합니다. 여기서 비교군으로 쓰인 모델들은, 사람이 만든 규칙에 따라서 수식을 줄여나갑니다. HISS는 어떤 규칙도 없이 학습되었지만, 규칙을 사용하는 Halide나 Z3에 비해 우월한 성능을 보입니다.

Figure 14. Performance of Halide. It shows better result than Halide original simplifier. (10% improvement)

Limitations

성능적인 부분을 보면 Human Dependent의 그래프에서 Halide에 비해서 10% 가량의 성능 향상에 불과한 모습을 볼 수 있습니다. 이는 기대에 비해 너무 낮은 성능 향상입니다. 앞서 3.b에 소개된 NeuRewriter의 경우 그 성능이 36.13 → 57.28로 Halide 대비 80% 가량 성능 향상을 보여줍니다. 이는 HISS보다 훨씬 높은 성능입니다.

이 연구에서 대조군은 기존의 rule-set을 heuristic하게 적용한 방법에 한정합니다. 다시 말해, 기존의 rule-set을 greedy하게 적용해보는 beam-search 기반이나 Deep Learning을 통해 학습된 rule-set Selector인 NeuRewriter에 비해서는 성능이 떨어집니다.

Figure 15. average expression length reduction                   Figure 16. average tree size reduction

HISS의 성능이 떨어지는 이유가 ‘Rule을 충분히 추출하지 못해서’인지, 아니면 ‘Rule을 만들 수는 있지만 어떤 Rule을 적용할지는 잘 학습하지 못해서’인지는 궁금한 부분입니다. 또한, 사람이 만든 rule-set을 사용하는 NeuRewriter에서는 AC 기반 알고리즘을 사용한 반면, HISS에서는 REINFORCE를 사용했다는 부분에서 성능 차이가 발생했을지도 확인해보고 싶습니다.

그 밖에 Halide 데이터를 그대로 차용했기에 데이터가 사칙연산과 비트연산으로만 구성되는 한계가 있습니다. 우리가 일반적으로 기대하는 수식에 있는 복잡한 연산을 포함하면, 지금도 sparse한 학습과정이 더욱 sparse해져 학습에 어려움이 있을지도 모릅니다. 또한, 프로그램이 single batch로만 돌도록 작성이 되어있고 속도의 측면에서 개선할 여지가 많습니다. 학습에 오랜 시간(2주)이 걸리는 것이 ablation을 많이 수행하지 못한 이유라고 생각되는데, 이 부분을 개선한다면 더 좋은 성능을 만들 수 있을 것으로 기대합니다.

4. Conclusion

Limitation from structure

이렇게 Symbolic simplifier에 대해 간단하게 살펴보았습니다. 저는 수식의 feature extractor로 사용하기 위해서 Symbolic simplifier를 연구하자고 이야기하였지만, ResNet과 같이 Computer Vision에서 보편적으로 쓰이는 feature extractor와 simplifier는 약간의 차이를 가지고 있습니다. 그 차이는 수식 고유의 특성에서 기인합니다. 결국 수식은 연산자, 변수, 숫자들이 어떤 벡터로 embedding되어서 모델에 들어가야 합니다. 앞서 보인 연구에서는 미리 search space를 정의해서, 쓰이는 연산자와 변수의 종류(symbolic tree의 노드 종류)를 제한하고 이를 embedding해서 모델을 학습시킵니다.

그렇다면 search space에 포함되지 않은, 새로운 연산자나 더 많은 변수를 요하는 작업은 어떨까요? 단순히 embedding하는 부분만 다시 학습시키면 될 수도 있지만, 이 과정이 쉽지 않을 수 있습니다. 추가적인 학습의 시간이 굉장히 오래걸리게 되면 pretrained backbone으로써의 장점도 상실될 것입니다. 이처럼 feature extractor로 응용하려면, 동일하거나 더 작은 search space를 가진 문제에서만 쓰일 수 있다는 점이 한가지 단점입니다.

Conclusion

저는 본문에서 simplifier를 feature extractor로 활용하는 것만 이야기 했지만 이 연구분야는 사실 수식의 이해, 수식 풀이, 수식 증명이나 프로그램 최적화와 같이 많은 분야와 접점을 가지고 있습니다. 그만큼 발전 가능성이 무궁무진한 연구 주제라고 생각합니다. 또한, 학습에 쓰일 데이터도 만들어서 사용하기에 데이터 관련 제약이 적고, 비교군으로 삼을 Wolfram과 같은 상용프로그램이 있어 목표도 설정하기 쉽다는 장점도 있습니다.

이 분야는 아직 많은 것이 미비한 상태입니다. 잘 짜여진 dataset이나 baseline이 되어줄 모델에 대한 연구도 없습니다. 본문에서는 Transformer와 TreeLSTM을 이용한 simplifier를 보였지만, GNN이나 NMT의 다양한 기술이 활용되지 않는 것에서 아직 개선의 여지가 많은 분야라고 생각합니다. 앞으로 많은 연구가 Symbolic simplifier 분야에서 이뤄지기를 바라며 글을 맺겠습니다.

저자 후기...

혹자는 Symbolic simplifier가 novelty도 없고 연구의 필요성도 모호한 분야라고 이야기할 수 있습니다. 저도 비슷한 생각이 있었고, 고민 끝에 이 simplifier의 인코더 부분을 보편적인 formula feature extractor로 쓸 수 있지 않을까 하는 생각을 가지게 되었습니다. Computer Vision에서 resnet과 같은 classifier를 backbone으로 사용하듯이, Sexp를 다루는 연구에서 Simplifier가 backbone 역할을 할 수 있지 않을까 생각합니다.

이 포스트를 작성하며 연구를 찾는 과정에 많은 난항을 겪었습니다. 특히 수학 쪽 연구들은 이해에 어려움이 있어 깊이 살펴보지 못했는데, 해당 분야에 관련 내용이 많을 수 있습니다. Simplify가 약간은 보편적인 문제인 만큼, 많은 분야에 파편화된 시도들이 많을 것으로 보이는데, 이를 잘 모아서 살펴본다면 또 다른 재미있는 리뷰가 되지 않을까 생각합니다.

Reference

• C. Li, Y. Xin, C. Lin, M. Guo, W. Wu, W. Ouyang, J. Yan, AM-LFS: AutoML for Loss Function Search, In ICCV, 2019.
• X. Wang, S. Wang, C. Chi, S. Zhang, and T. Mei, Loss Function Search for Face Recognition. In ICML, 2020.
• H. Li, C. Tao, X. Zhu, X. Wang, G. Huang, J. Dai, Auto Seg-Loss: Searching Metric Surrogates for Semantic Segmentation, In ICLR, 2021.
• P. Liu, G. Zhang, B. Wang, H. Xu, X. Liang, Y. Jiang, Z. Li, Loss Function Discovery for Object Detection via Convergence-Simulation Driven Search, In ICLR, 2021.
• J.D. Co-Reyes, Y. Miao, D. Peng, E. Real, S. Levine, Q.V. Le, H. Lee, A. Faust, Evolving Reinforcement Learning Algorithms, In ICLR, 2021.
• E. Real, C. Liang, D.R. So, Q.V. Le, AutoML-Zero: Evolving Machine Learning Algorithms From Scratch, In ICML, 2020.
• P. Ramachandran, B. Zoph, Q.V. Le, Searching for Activation Functions, 2017.
• B.K. Petersen, M.L. Larma, T.N. Mundhenk, C.P. Santiago, S.K. Kim, J.T. Kim, Deep symbolic regression: Recovering mathematical expressions from data via risk-seeking policy gradients, In ICLR, 2021.
• G. Lample, F. Charton, Deep Learning for Symbolic Mathematics, In ICLR, 2020.
• Q. Wang, C. Kaliszyk, J. Urban, First Experiments with Neural Translation of Informal to Formal Mathematics, In CICM, 2018.
• B. Piotrowski, J. Urban, C.E. Brown, C. Kaliszyk, Can Neural Networks Learn Symbolic Rewriting?, In ICML Graph workshop, 2019.
• J.T. Kim, M.L. Larma, B.K. Petersen, Distilling Wikipedia mathematical knowledge into neural network models, In ICLR Mathematical Reasoning Workshop, 2021.
• H. Shi, Y. Zhang, X. Chen, Y. Tian, J. Zhao, Deep Symbolic Superoptimization Without Human Knowledge, in: International Conference on Learning Representations, In ICLR, 2020.
• X. Chen, Y. Tian, Learning to Perform Local Rewriting for Combinatorial Optimization, In NeurIPS, 2019.
• SymPy Simplify() : https://docs.sympy.org/latest/tutorial/simplification.html#example-continued-fractions
• Wolfram FullSimplify : https://reference.wolfram.com/language/ref/FullSimplify.html
• Wolfram Simplify : https://reference.wolfram.com/language/ref/Simplify.html
• Wolfram Simplifying Algebraic Expressions : https://reference.wolfram.com/language/tutorial/AlgebraicCalculations.html#16626