DiscoGrad

분기(branchy)가 많은 프로그램에서 자동 미분 (Automatic Differentiation)을 사용하여 경사 하강법 (Gradient Descent)을 수행하려고 하시나요?
또는 엔드 투 엔드 (end-to-end) 학습을 위해 이를 신경망 (Neural Networks)과 결합하려고 하시나요?
그렇다면 이 프로젝트가 흥미로울 것입니다.

자동 미분 (Automatic Differentiation, AD)은 컴퓨터 프로그램의 기울기 (Gradients)를 얻기 위한 대중적인 방법이며, 이는 최적화 (Optimization), 제어 (Control), 추론 (Inference) 문제를 해결하기 위해 경사 하강법 (Gradient Descent)을 사용하여 프로그램 파라미터를 조정하는 데 매우 유용합니다. 불행히도, AD만으로는 if-else 문과 같은 파라미터 의존적 분기 제어 흐름 (Branching Control Flow) 및 다양한 유형의 시뮬레이션을 포함한 무작위성 (Randomness)이 포함된 프로그램에 대해 도움이 되지 않는 (0 값이거나 편향된) 기울기를 생성하는 경우가 많습니다.

DiscoGrad는 C++ 프로그램을 분기 (Branches)를 가로질러 매끄러운 기울기 (Smoothed Gradients)를 효율적으로 계산하는 버전으로 자동 변환합니다. 외부 섭동 (External Perturbations)을 통한 평활화 (Smoothing)가 지원되지만, 대상 프로그램 자체에 무작위성 (Randomness)이 포함되어 있다면 필수 사항은 아닙니다. DiscoGrad는 여러 가지 기울기 추정 (Gradient Estimation) 백엔드를 포함하고 있으며, Torch를 통해 신경망 (Neural Networks)을 통합할 수 있는 가능성도 제공합니다. 이 도구는 기본적인 C++ 구조를 지원하지만, 아직 연구용 프로토타입 (Research Prototype) 단계입니다.

이 저장소에는 교통, 군중 관리, 역학 (Epidemiology)과 같은 도메인의 다양한 샘플 애플리케이션이 포함되어 있습니다.

DiscoGrad Use Cases

Illustration of DiscoGrad

💾 설치 (Installation)

Ubuntu 24.04.1 LTS, Ubuntu 22.04.4 LTS, Arch Linux 및 Fedora 38 Workstation에서 테스트되었습니다.

변환 코드를 컴파일하려면 다음 패키지(또는 Linux 배포판에서 제공하는 유사 패키지)가 필요합니다:

• clang, libclang-dev, libclang-cpp-dev (버전 13 이상)
• llvm, llvm-dev (버전 13 이상)
• cmake

cd transformation
cmake .
make -j

🚀 빠른 시작 (Quickstart)

programs/hello_world/hello_world.cpp에 포함된 코드를 빠른 시작 (Quickstart) 템플릿 및 참조용으로 사용할 수 있습니다. programs 폴더에는 이보다 더 복잡한 여러 프로그램도 포함되어 있습니다.

위 영상에서 보여준 것처럼 Heaviside 계단 함수 (Heaviside step function)를 구현한 hello world 예제를 컴파일하려면 다음과 같이 실행합니다:

discograd$ ./smooth_compile programs/hello_world/hello_world.cpp

smooth_compile은 다양한 백엔드 (backend)를 위해 코드를 변환하고 컴파일하는 명령을 호출하는 셸 스크립트 (shell script)입니다. 여기서는 programs/hello_world 폴더에 각 백엔드별 바이너리 (binary)를 생성합니다.

원본 (crisp) C++ 프로그램에 자동 미분 (AD)을 적용하면 0인 미분값이 나옵니다:

DiscoGrad$ echo 0.0 | ./programs/hello_world/hello_world_crisp_ad --var 0.0 --ns 1
expectation: 1
derivative: 0

우리의 추정기인 DiscoGrad Gradient Oracle (DGO)는 최적화 (optimization)에 유용한 0이 아닌 미분값을 계산합니다:

DiscoGrad$ echo 0.0 | ./programs/hello_world/hello_world_dgo --var 0.25 --ns 1000
expectation: 0.527
derivative: -0.7939109206

CLI 사용법에 대한 정보는 ./programs/hello_world/hello_world_{crisp,dgo,pgo,reinforce} -h를 실행하여 확인할 수 있습니다.

❔ 사용법 (Usage)

DiscoGrad API 사용법

아래에 상세히 설명된 바와 같이, 우리 API를 사용하려면 약간의 상용구 코드 (boilerplate)가 필요합니다. 몇 가지 사용 예시는 programs 폴더를 참조해 주세요.

1. 소스 파일의 최상단에 프로그램의 입력 개수를 정의하고 discograd 헤더를 포함합니다 (이 순서를 지켜주세요).

const int num_inputs = 1;
#include "discograd.hpp"

2. 함수 이름 앞에 _DiscoGrad_를 붙이고, 반환 값으로 미분 가능한 타입인 adouble을 사용하여 엔트리 함수 (entry function)를 구현합니다. aparams 타입의 객체는 프로그램의 입력값을 보유합니다. 전통적인 자동 미분 (AD, Automatic Differentiation) 라이브러리와 마찬가지로, adouble 타입은 배정밀도 부동 소수점 (double precision floating point) 변수를 나타냅니다. DiscoGrad는 adouble을 통한 미분뿐만 아니라, adouble의 (함수) 값에 따른 분기 (branching)를 허용하며, 선택된 분기가 조건에 의존하는 정도를 반영하는 그래디언트 (gradient)를 생성합니다.

adouble _DiscoGrad_my_function(DiscoGrad<num_inputs>& _discograd, aparams& p) {
  adouble inputs[num_inputs];
  for (int i = 0; i < num_inputs; i++)
...

3. main 함수에서 DiscoGrad 클래스의 인스턴스와 매끄러운 함수 (smooth function)를 위한 래퍼 (wrapper)를 생성하여 DiscoGrad API와 인터페이스합니다. DiscoGrad 인스턴스에서 .estimate(func)를 호출하여 백엔드 전용 그래디언트 추정기 (gradient estimator)를 실행합니다.

int main(int argc, char** argv) {
  // 백엔드와 인터페이스하고 분산 (variance)과 같은 CLI 인자를 제공합니다
  DiscoGrad<num_inputs> dg(argc, argv);
...

매끄러운 함수에 추가 변수 포함하기

입력값(aparams) 이외의 추가 변수를 포함하고, 매끄러운 함수들 사이에서 DiscoGrad 인스턴스를 전달해야 하는 번거로움을 피하려면, DiscoGradProgram 인터페이스를 구현하는 클래스로 함수를 감싸야 합니다. 이 클래스의 유일한 요구 사항은 adouble run(DiscoGrad&, aparams&) 메서드를 구현하는 것입니다. 간단한 예시는 programs/ac를, 더 정교한 예시는 programs/epidemics를 참조하세요. 다음은 위의 2단계와 3단계를 대체하는 예시입니다:

class MyProgram : public DiscoGradProgram<num_inputs> {
public:
  // 미분하기를 원하지 않는 매개변수 (parameter)
...

컴파일

programs/my_program/my_program.cpp 폴더에 있는 프로그램을 모든 백엔드(backend)로 컴파일하려면 다음과 같이 입력합니다:

discograd$ ./smooth_compile programs/my_program/my_program.cpp

사용자 정의 컴파일러(compiler) 또는 링커(linker) 플래그는 smooth_compile 스크립트에서 설정할 수 있습니다.

백엔드 목록은 아래에서 확인할 수 있습니다. 기본적으로 모든 백엔드에 대한 실행 파일이 생성됩니다. 컴파일을 특정 백엔드 집합으로 제한하려면 -Cbackend1,backend2,... 플래그를 추가하세요.

컴파일 시점에 전처리기 상수(preprocessor constants)를 정의하려면 -D 플래그를 사용할 수 있습니다. 예를 들어, -DNUM_REPS=10은 NUM_REPS라는 이름의 상수를 10으로 설정합니다.

Smoothed Program 실행하기

Smoothed program을 실행하고 그 기울기(gradient)를 계산하려면, 원하는 CLI 인자와 함께 바이너리를 호출하기만 하면 됩니다. 예를 들어,

discograd$ ./programs/my_program/my_program_dgo --var 0.25 --ns 100

만약 DGO 백엔드를 사용하고 싶다면 위와 같이 입력합니다. 매개변수는 stdin을 통해 입력되며, 예를 들어 퀵스타트 가이드에 나와 있는 것처럼 echo의 출력을 파이프(piping)로 전달할 수 있습니다. expectation 및 derivative 이후의 stdout 출력은 smoothed output과 편미분(partial derivatives) 값을 제공합니다.

백엔드 (Backends)

현재 사용 가능한 모든 백엔드에 대한 개요입니다. 더 자세한 설명은 다음 섹션에서 확인할 수 있습니다.

실행 파일 접미사 (ExecutableSuffix)	설명
crisp	선택적 입력 섭동(input perturbations) 및 자동 미분(AD)이 적용된 원본 프로그램
dgo	DiscoGrad Gradient Oracle. 자동 미분(automatic differentiation)과 몬테카를로 샘플링(Monte Carlo sampling)에 기반한 DiscoGrad 자체의 기울기 추정기(gradient estimator).
pgo	Polyak이 제시하고 Nesterov 등이 추가로 분석한 Polyak의 Gradient-Free Oracle.
reinforce	인위적으로 도입된 가우시안 무작위성(Gaussian randomness)을 가진 프로그램에 REINFORCE를 적용한 방식.
rloo	Kool 등이 설명한 REINFORCE Leave-One-Out 추정기.

또한, Chaudhuri와 Solar-Lezama의 매끄러운 해석 (Smooth Interpretation) 방법을 통한 경사 추정 (gradient estimation) 구현은 'discograd_ieee_access' 브랜치에서 확인할 수 있습니다.

참고: 모든 브랜치가 알려진 형태의 분포에서 추출된 이산 확률 변수 (discrete random variables) 상에서 직접 발생하는 경우, StochasticAD가 위 추정기들의 적절한 대안이 될 수 있습니다.

참고 문헌 (References):

• Chaudhuri, Swarat, and Armando Solar-Lezama. "Smooth interpretation." ACM Sigplan Notices 45.6 (2010): 279-291.
• Boris T Polyak. "Introduction to optimization." 1987. (Chapter 3.4.2)
• Nesterov, Yurii, and Vladimir Spokoiny. "Random gradient-free minimization of convex functions." Foundations of Computational Mathematics 17 (2017): 527-566.
• Wouter Kool, Herke van Hoof, and Max Welling. Buy 4 reinforce samples, get a baseline for free! DeepRLStructPred@ICLR, 2019.

⚖️ 라이선스 (License)

이 프로젝트는 MIT 라이선스 (MIT License) 하에 라이선스가 부여됩니다.
DiscoGrad 도구는 다음과 같이 라이선스가 부여된 제3자의 일부를 포함하고 있습니다:

• backend/ankerl/unordered_dense.h, MIT 라이선스
• backend/genann.hpp, zlib 라이선스
• backend/discograd_gradient_oracle/kdepp.hpp, MIT 라이선스
• backend/args.{h,cpp}, MIT 라이선스
• Doxygen Awesome theme, MIT 라이선스

📄 인용 (Cite)

@article{kreikemeyer2023smoothing,
     title={Smoothing Methods for Automatic Differentiation Across Conditional Branches},
     author={Kreikemeyer, Justin N. and Andelfinger, Philipp},
...

DGO 추정기의 대안적인 유도 방식은 다음에서 확인할 수 있습니다:

@inproceedings{andelfinger2024automatic,
  booktitle = {24th International Conference on Computational Science (ICCS 2024)},
  title = {{Automatic Gradient Estimation for Calibrating Crowd Models with Discrete Decision Making}},
...

감사의 글 (Acknowledgement)

이 연구는 Deutsche Forschungsgemeinschaft (DFG), 독일 연구 재단(German Research Foundation)의 지원(Grant 497901036)을 받아 수행되었습니다.