[ML] XGBoostAScalableTreeBoostingSystem 논문 요약

XGBoost는 확장 가능한 트리 부스팅 시스템으로, 많은 머신러닝 문제에서 뛰어난 성능을 보여주는 알고리즘입니다. 이 논문에서는 희소 데이터와 효율적인 캐시 접근 방식을 포함한 XGBoost의 독창적인 알고리즘을 제안합니다. XGBoost는 대규모 데이터 처리에서 빠른 성능을 자랑하며, 엔드 투 엔드 시스템으로의 가능성을 보여줍니다. 또한, 이를 통해 데이터 과학자들은 더욱 강력한 모델을 구축할 수 있는 여건을 마련할 수 있습니다. XGBoost는 실제 세계의 여러 문제에서 가장 효과적인 기계 학습 방법 중 하나로 자리잡고 있습니다.

핵심 용어

• XGBoost: XGBoost는 확장 가능한 트리 부스팅 시스템으로, 데이터를 분석하고 예측하는 데 매우 효율적이에요. 마치 여러 나무를 한꺼번에 사용해 숲을 만드는 것처럼, XGBoost...

1. 🚀 XGBoost: 확장 가능한 트리 부스팅 시스템

• XGBoost는 스케일이 크고 효율적인 트리 부스팅 시스템으로, 여러 머신러닝 도전 과제에서 최첨단 결과를 달성하는 데 널리 사용된다.

• 이 시스템은 희소 데이터 및 가중 집합의 작업을 가능하게 하며, 캐시 접근 패턴 및 데이터 압축, 분산 처리 최적화를 통해 수십억 개의 예제를 처리할 수 있다.

• 다양한 머신러닝 대회에서 승리팀들이 XGBoost를 채택함으로써 이 시스템의 우수성을 입증했으며, 이로 인해 XGBoost는 많은 데이터 과학자들 사이에서 표준 선택 도구가 되었다.

1.1. XGBoost의 기본 개요

• XGBoost는 확장 가능한 트리 부스팅 시스템이다.

• XGBoost는 문제 해결을 위한 독립적인 도구로 활용된다.

1.2. XGBoost: 스케일러블한 트리 부스팅 시스템

• XGBoost는 데이터 과학자들이 최첨단 결과를 달성하기 위해 사용하는 스케일러블한 기계 학습 시스템이다. 이 시스템은 여러 기계 학습 도전 과제에서 널리 사용된다.

• Kaggle의 2015년 29개 챌린지 우승 솔루션 중 17개가 XGBoost를 사용하였으며, 특히 8개 솔루션은 전적으로 XGBoost만으로 모델을 학습하였다.

• XGBoost는 KDD Cup 2015에서도 모든 우승 팀의 솔루션에서 사용되었으며, 그들은 XGBoost의 성능이 잘 구성된 다른 방법보다 단지 조금 더 우수하다고 보고하였다.

• 이 시스템은 복잡한 데이터 의존성을 캡처하는 효과적인 모델과 대규모 데이터셋에서 모델을 학습할 수 있는 스케일러블 학습 시스템을 통해 성공적으로 사용된다.

• XGBoost의 가장 큰 강점은 모든 시나리오에서의 확장성이다. 이 시스템은 단일 머신에서 기존 솔루션보다 10배 더 빠르게 실행되며, 분산 또는 메모리 제한 환경에서도 수십억 개의 예를 처리할 수 있다.

1.3. XGBoost의 확장 가능성

• XGBoost의 확장 가능성은 여러 중요한 시스템 및 알고리즘 최적화 덕분에 가능하다.

• 새로운 트리 학습 알고리즘은 파싱된 데이터를 효과적으로 처리할 수 있다.

• 병렬 및 분산 컴퓨팅을 활용하여 학습 속도를 증가시키고, 이를 통해 더 빠른 모델 탐색이 가능하다.

• XGBoost는 오프-core 계산을 활용하여 데이터 과학자들이 데스크탑에서 수억 개의 사례를 처리할 수 있도록 지원한다.

• 이 논문은 효율적인 제안 계산을 위한 이론적으로 정당화된 가중치 분위수 스케치를 제안한다.

1.4. 트리 부스팅 알고리즘의 개선 사항

• 캐시 인식 및 희소성 인식 학습 방법이 아직 탐색되지 않았으며, 이러한 측면을 결합한 종단 간 시스템이 현실 세계의 사용 사례에 대한 새로운 해결책을 제공한다.

• 제안된 미분 가능한 볼록 손실 함수는 예측값과 목표값 간의 차이를 측정한다.

• 추가된 정규화 학습 목표는 모델의 복잡성을 처벌하고, 최종 학습된 가중치를 매끄럽게 하여 과적합을 피하는 데 도움을 준다.

• 이후 논문에서는 트리 부스팅 및 정규화 목표를 소개하고, 분할 찾기 방법 및 시스템 설계를 제시하며, 관련된 정량적 지원을 제공한다.

• 정규화 매개변수가 0으로 설정되면, 목표는 기존의 회귀 트리 함수로 돌아간다.

1.5. 그래디언트 트리 부스팅의 주요 개념

• 그래디언트 트리 부스팅 알고리즘은 전통적인 최적화 방법으로는 다룰 수 없는 매개변수를 포함한 모델을 개선하는 데 중점을 둔다.

• 이 모델은 가법적 방식으로 학습되며, 각 반복에서 기존의 예측을 보완하는 트리 함수를 추가하여 목표를 최소화한다.

• 각 트리는 독립적인 회귀 트리로 구성되며, 예시는 해당 트리의 구조에 의해 분류된다.

• 자연스러운 합성 및 점수 계산 방식을 통해 각 나뭇잎의 점수를 평가하고, 이 점수는 노드 분할을 위한 기준으로 활용된다.

• 최적화 점수는 열(column) 서브 샘플링 기법을 통해 계산 속도를 높이고 오버 피팅을 방지하며, 이는 전통적인 행(row) 서브 샘플링보다 더 효과적이다.

2. 📈 XGBoost의 알고리즘 효율성 및 최적화 방법

• 정확한 탐색 알고리즘은 가능한 모든 분할 지점을 탐색하며, 이를 통해 최적의 성능을 달성한다. 그러나 이 과정은 계산적으로 비효율적이어서 데이터가 메모리에 맞지 않을 경우 어려움이 발생한다.

• 규제 목표 외에도, 데이터 과적합을 방지하기 위한 두 가지 추가 기술인 축소(shrinkage)와 열 서브샘플링(column subsampling)이 사용되며, 이는 각각 기존 트리의 영향력을 줄이고 데이터를 더 효율적으로 사용할 수 있도록 돕는다.

• 근사 알고리즘은 대규모 데이터 셋에서도 적용할 수 있도록 후보 분할 지점을 제안하는 방향으로 개선되었으며, 효율적인 트리 부스팅을 위해 예상된 분할 점을 기반으로 최적화를 수행한다.

• 희소성 인식(split finding)은 데이터 입력의 결측값이나 자주 발생하는 제로 입력에 대한 효율적인 처리를 지원하며, 추가적으로 결측값에 대해 기본 방향(default direction)을 제공하여 모든 트리를 고려할 수 있도록 설계되었다.

• 컬럼 블록(column block) 구조는 병렬 학습을 지원하여 데이터 정렬 비용을 줄이고, 데이터의 각 블록을 크기별로 나누어 기계학습 속도를 높이는 방법이다. 이는 여러 기계에 걸쳐 분산 가능하며, 모든 스레드에서의 통계 수집을 병렬 처리할 수 있도록 돕는다.

2.1. 정확한 탐욕 알고리즘과 손실 감소

• 정확한 탐욕 알고리즘은 최적의 분할을 찾기 위해 모든 가능한 분할을 열거하는 방법이다.

• 손실 감소는 분할 후의 결과로 주어진 식에 따라 계산된다.

• 대부분의 단일 머신 트리 부스팅 구현체는 정확한 탐욕 알고리즘을 지원하며, scikit-learn과 R의 gbm이 그 예시이다.

• 이 알고리즘은 연속적인 특성에 대한 모든 가능한 분할 후보를 열거하는 과정이기 때문에 계산 비용이 크다.

• 효율적인 성능을 위해서는 알고리즘의 개선이 필요할 것으로 추정된다.

2.2. XGBoost에서의 과적합 방지를 위한 기법들

• 데이터를 정렬 후 누적하여 gradient statistics를 계산하고, 새로운 가중치를 조정하여 과적합을 방지하는 두 가지 기술이 사용된다.

• 첫 번째 기술은 Shrinkage로, 새로 추가된 가중치가 각 트리 부스팅 단계 후에 일정 비율(η)로 축소된다. 이는 각 개인 트리의 영향력을 줄여주며 미래의 트리에 대한 여지를 남겨준다.

• 두 번째 기술은 특성 서브샘플링으로, 이는 Random Forest에서 사용되는 기법이다. 이 기법은 트리의 분할을 최적화하는 데 중요한 역할을 한다.

• Exact Greedy Algorithm은 모든 가능한 분할 지점을 탐색하며 실시간으로 최적의 트리 구조를 찾지만, 메모리 제약으로 인해 대용량 데이터에 대한 효율적 처리가 어렵다.

• AUC 성능 비교 결과, Higgs 10M 데이터셋에 대한 실험을 통해 정확도를 향상시키기 위한 eps 파라미터의 중요성이 강조된다.

2.3. 분산 환경에서의 근사 스플릿 찾기 알고리즘

• 근사 프레임워크는 과거 문헌의 아이디어를 바탕으로 후보 스플릿 포인트를 찾기 위한 방법을 요약한다. 이 알고리즘은 초기 단계에서 모든 후보 스플릿을 제안하고, 각 레벨에서 동일한 제안을 사용할 수 있다.

• 후보 스플릿 포인트는 특징 분포의 백분위수에 따라 결정되며, 이 경우 각 데이터 포인트는 가중치로 표현된다.

• 알고리즘의 두 가지 변형이 존재하는데, 글로벌 변형은 많은 제안 단계가 필요 없으나 후보 포인트 수가 줄어들 수 있는 반면, 로컬 변형은 각 스플릿 후 후보를 재제안하여 덜 필요한 후보 포인트를 요구할 수 있다.

• 새로운 분산 가중치 양자 스케치 알고리즘을 도입하여 가중화된 데이터 세트를 처리할 수 있는 이론적 보장을 제공한다.

• 이 알고리즘은 분포 가능한 히스토그램을 직접 구성하고, 특정 정확도 수준을 유지하며 데이터 통합 및 가지치기 작업을 지원하도록 설계되었다.

2.4. 희소성 인식 알고리즘의 효과

• 희소성의 원인은 데이터 내 결측치, 빈번한 제로 항목, 머신 설정, 그리고 특징 공학으로 추정된다. 따라서, 알고리즘이 이러한 희소성 패턴을 인식해야 한다.

• 알고리즘은 데이터의 결측치가 있을 경우, 이를 기본 방향으로 분류하여 처리한다. 이 과정에서 사용자는 필요한 방법을 자유롭게 선택할 수 있다.

• 제안된 근사 알고리즘은 결측값을 처리하기 위해 비어 있지 않은 항목에서만 통계를 수집한다. 또한, 이 알고리즘은 나쁜 성능 기준으로 삼고, 희소성을 고려하지 않는 단순 버전보다 50배 이상 빠르다.

• 블록 구조를 통해 병렬 학습을 수행하며, 각 블록은 해당 특징 값으로 정렬되며, 이는 효율적인 분할 포인트 열거에 기여한다.

• 제안된 알고리즘은 각 노드의 대용량 데이터 처리에 있어 경량화된 역할을 할 수 있다.

2.5. XGBoost의 병렬 학습을 위한 블록 구조

• XGBoost에서는 데이터를 메모리 내 유닛인 블록에 저장하여 정렬 비용을 줄인다. 이는 훈련 전 한 번만 계산되고 이후 반복에서 재사용 가능하다.

• 기본 방향은 데이터에서 학습되며, 이를 통해 분할 검색 알고리즘을 실행하여 각 블록의 정보를 통합적으로 처리한다.

• 누락된 값은 최적 방향을 학습하는 데 있어 결측값으로 처리되며, 블록 구조를 통해 효율적으로 최적 분할을 찾는다.

• XGBoost는 다양한 희소성 패턴을 지원하며, 적은 메모리로 큰 데이터 세트를 처리하는 데 효율적이다.

• 통계 수집 과정은 병렬화가 가능하여, 희소성 인식 알고리즘은 단순 구현보다 50배 더 빠른 성능을 보인다.

3. 📊 XGBoost의 성능 향상을 위한 캐시 인지 알고리즘

• 캐시 인지 프리패칭을 활용한 결과, 큰 데이터셋에서 성능이 두 배로 향상된다.

• 정확한 탐색 알고리즘의 시간 복잡도는 O(Kd‖x‖₀ log n)으로, 여기서 d는 트리의 최대 깊이, K는 총 트리 수를 나타낸다.

• 블록 구조를 활용한 트리 부스팅은 O(Kd‖x‖₀ + ‖x‖₀ log n)의 시간 복잡도를 갖고, 이는 대규모 데이터에서 추가적인 log n 절감을 가져온다.

• 블록 크기의 선택이 매우 중요하며, 과도하게 작은 블록은 비효율적인 병렬화를 초래하고, 과도하게 큰 블록은 캐시 미스를 발생시킨다.

• 캐시 인지 프리패칭 알고리즘을 통해 그라디언트 통계치를 내부 버퍼로 가져와서 누적하는 방식으로 문제를 해결하며, 이는 성능 향상을 가져온다.

3.1. 캐시 인식 프리패칭의 성능 향상

• 캐시 미스 효과가 대규모 데이터셋(1000만 인스턴스)에서 성능에 영향을 미친다.

• 캐시 인식 프리패칭을 사용하면 대규모 데이터셋에서 성능이 두 배 개선된다.

• 블록 크기가 증가할수록 성능에 미치는 영향은 상이하지만, 시간 소요는 일정하게 발생한다.

• 짧은 범위의 데이터 의존성 패턴이 캐시 미스로 인해 지연을 초래할 수 있다.

3.2. 시간 복잡도 분석

• 최대 깊이를 d, 총 나무의 수를 K로 두었을 때, 원래의 정확한 알고리즘에 대한 시간 복잡도는 O(Kd∥x∥₀logn)이다. 여기서 ∥x∥₀는 훈련 데이터의 결측치가 아닌 항목의 수를 나타낸다.

• 블록 구조를 이용한 트리 부스팅의 경우, 시간 복잡도는 O(Kd∥x∥₀+(∥x∥₀logn))로 계산된다. 여기서 O((∥x∥₀logn))는 사전 처리 비용이다.

• 블록 구조는 n이 클 때 추가적인 logn 요소를 절약할 수 있어, 시간 복잡도를 개선하는 데 도움이 된다.

• 근사 알고리즘의 경우, 원래 알고리즘의 시간 복잡도는 O(Kd∥x∥₀logq)이며, q는 데이터셋에서의 제안 후보자의 수로 보통 32와 100 사이이다.

• 블록 구조를 사용하면 계산에서 추가적인 logq 요인을 절약할 수 있어, 시간 복잡도가 O(Kd∥x∥₀+(∥x∥₀logB)로 줄어드는 경향이 있다. 여기서 B는 각 블록의 최대 행 수이다.

3.3. 캐시 인식 블록 크기 조정과 효율적 병렬화

• 작은 블록 크기는 비효율적인 병렬화를 초래하고, 과도하게 큰 블록은 훈련 속도를 저하시킨다, 따라서 최적의 블록 크기 설정이 필요하다.

• 새로운 알고리즘은 비순차적 메모리 접근을 통해 기울기 통계를 불러오는 비효율적인 방식이 있으며, 이는 CPU 캐시에서 기울기 통계들이 적재되지 않기 때문에 발생한다.

• 정확한 탐욕 알고리즘의 경우, 캐시 인식 사전 가져오기 알고리즘을 통해 문제를 완화할 수 있으며, 각 스레드에 내부 버퍼를 할당하여 기울기 통계를 가져온다.

• 다양한 블록 크기를 비교한 결과, 행 수가 많을 때 런타임 오버헤드가 줄어드는 것으로 나타났다.

• 선택한 블록 크기가 캐시 속성과 병렬화 사이의 균형을 맞추는 데 중요한 역할을 하며, 이는 기존의 트리 학습을 병렬화하기 위한 여러 연구들과 관련이 있다.

3.4. XGBoost의 큰 규모 문제 해결을 위한 시스템 기술

• XGBoost는 스케일러블 학습을 달성하기 위해 머신의 리소스를 최대한 활용하는 것을 목표로 한다.

• 기존 연구들은 주로 알고리즘적인 측면에 집중하는 반면, XGBoost는 디스크 공간을 활용하여 메모리에 맞지 않는 데이터를 처리할 수 있는 아웃오브코어(computation) 방식으로 향상되었다.

• 블록 압축과 데이터 샤딩 두 가지 기술을 통해 아웃오브코어 계산을 개선하며, 블록은 열(column) 단위로 압축되고 필요 시 독립 스레드에 의해 메모리로 로드된다.

• XGBoost는 데이터베이스 커뮤니티에서 제안된 가중치가 있는 분위기 스케치 방법을 통해 가중치 데이터에 대한 분위기를 계산할 수 있는 최초의 방법을 제시한다.

• XGBoost는 다양한 언어에서 지원되며, Hadoop, MPI, Spark 환경에서도 원활하게 실행되도록 설계되어 많은 생태계에서 사용 가능하다.

3.5. 실험에 사용된 데이터셋 요약

• XGBoost와 여러 데이터셋을 사용하여 실험을 수행했으며, 그 내용은 Table 2에 요약되어 있다.

• 첫 번째 데이터셋인 Allstate 데이터셋은 보험 청구의 가능성과 비용 예측을 위한 것이며, 주로 sparsity-aware 알고리즘의 영향을 평가하기 위해 사용되었다.

• 두 번째 데이터셋인 Higgs 보존 데이터셋은 물리학 이벤트의 분류 작업을 위한 것으로, 몬테카를로 시뮬레이션을 통해 생성되었다.

• 세 번째 데이터셋인 Yahoo! 학습 순위 데이터셋은 웹 검색 쿼리를 기반으로 한 문서 순위 작업에 사용되며, 공식적인 트레인-테스트 분할을 따른다.

• 마지막 데이터셋은 Criteo의 클릭 로그 데이터셋으로, 시스템의 스케일링 성능을 평가하기 위한 목적으로 활용된다.

4. 🚀 XGBoost의 성능 향상 및 확장성

• XGBoost는 out-of-core 설정에서도 더 뛰어난 성능을 발휘하며, 단일 머신 실험에서는 scikit-learn보다 10배 빠른 결과를 보여준다.

• 실험에서 사용된 Dell PowerEdge R420는 Intel Xeon (E5-2470)보다 성능이 약간 떨어지며, 특정 데이터 세트의 중요 특징 선택에서 이익을 볼 수 있다.

• XGBoost의 기본 알고리즘은 200M 이상의 예제를 처리하는 데 어려움이 있으며, 압축 기법을 사용하면 3배의 속도 향상을 이룰 수 있다.

• XGBoost는 데이터 로드 과정이 제외된 경우에도 빠른 성능을 내며, 서브샘플링을 통해 과적합을 방지하고 약간의 성능 향상을 가져오는 것으로 나타났다.

• 분산 환경에서는 XGBoost가 4대의 머신으로 1.7억 데이터 전량을 처리할 수 있으며, 이로 인해 시스템의 확장성이 뛰어난 것으로 평가된다.

 

5. 📊 XGBoost의 개발 경험과 교훈

• XGBoost는 확장 가능한 트리 부스팅 시스템을 구축하면서 학습한 여러 교훈을 바탕으로 데이터 과학자들이 다양한 문제에서 최첨단 결과를 도출하도록 돕는다.

• 데이터 압축, 캐시 접근 패턴 및 샤딩은 확장 가능한 트리 부스팅 시스템 구축에 있어 필수적인 요소로 확인되었다.

• 이러한 경험들은 다른 머신러닝 시스템에도 적용 가능하며, XGBoost는 최소한의 자원으로 실제 문제를 해결할 수 있도록 설계되었다.

• 연구의 진행 과정에서 피드백을 제공한 여러 기여자들에게 감사의 뜻을 전하고, 자금 지원에 대한 언급도 포함되어 있다.

5.1. XGBoost의 주요 발견과 교훈

• 이 논문에서는 XGBoost라는 확장 가능한 트리 부스팅 시스템을 구축하면서 얻은 교훈을 설명하고 있다.

• 희소성을 고려한 알고리즘과 이론적으로 정당화된 가중치 분위수 스케치 기법을 제안하였다.

• 캐시 접근 패턴, 데이터 압축 및 샤딩은 확장 가능한 트리 부스팅 시스템을 구축하는 데 필수적인 요소임을 보여주었다.

• 이러한 교훈은 다른 머신러닝 시스템에도 적용할 수 있음을 시사한다.

• XGBoost는 이러한 통찰을 결합하여 현실 세계의 규모 문제를 해결할 수 있는 능력을 갖추고 있다.

5.2. 감사의 말씀 및 참고 문헌

• 이 연구에는 타일러 B. 존슨, 마르코 툴리오 리베이로, 사미르 싱, 아르빈드 크리슈나무르티의 귀중한 피드백에 대한 감사가 포함되어 있다.

• 또한 XGBoost 커뮤니티의 기여자들인 통허, 빙 쉬, 마이클 베네스티, 위안 탕, 홍량 리우, 권 커우, 난 저에게도 감사를 표한다.

• 본 연구는 ONR(N000141010672), NSF IIS 1258741, MARCO 및 DARPA가 후원한 TerraSwarm 연구 센터의 지원을 받았다.

• 다양한 참고 문헌이 소개되었으며, 여기에는 머신러닝과 관련된 중요한 연구 결과들이 포함되어 있다.

• 최신 연구, 이 연구가 다룬 다양한 머신러닝 접근법과 알고리즘들을 검토하고 있으며, 여러 분야에서의 적용 가능성을 탐구하고 있다.

5.3. 가중치가 적용된 분위기 스케치 알고리즘

• 가중치 분위기 스케치 알고리즘은 여러 실제 응용에 대한 분위기 쿼리의 근사 답변을 제공한다. 이 알고리즘은 GK 알고리즘 및 그 확장에 기반을 둔다.

• 분위기 요약의 주요 구성 요소는 두 가지 연산인 병합(operation)과 가지치기(prune)이다. 병합은 두 요약을 결합하여 새로운 요약을 생성하며, 가지치기는 요약의 요소 수를 줄인다.

• 새로운 알고리즘은 병합 및 가지치기 연산을 통해 GK 요약과 동일한 보장을 제공하여 가중치를 가진 데이터에 대한 분위기 쿼리를 효율적으로 해결할 수 있도록 한다.

• 분위기 요약 Q(D)는 가중 데이터에 대해 정의된 튜플로, 특정 조건을 만족할 때 (ε-근사 요약)로 간주된다.

• Q(D) 요약이 (ε-근사 요약)인지 여부는 특정 두 조건을 만족해야 하며, 이를 통해 쿼리 함수가 호출될 때의 조건을 명시한다.

5.4. 확장 함수의 특성 및 초기 요약 구성

• 확장된 함수 \( \tilde{D} \)와 \( \tilde{\omega}D \)는 \( X \rightarrow [0,+\infty) \)의 관계를 가지며, 이는 원 함수의 제약과 연관된다. 이를 통해 원 함수에 대한 제약이 확장된 함수에 대한 더 일반적인 제약으로 이어질 수 있다.

• Lemma A.1과 A.2는 원 함수에 대한 제약 조건들로부터 확장된 함수에 대한 더 일반적인 제약 조건을 얻을 수 있음을 보여준다.

• 주어진 두 개의 요약 \( Q(D_1) \)과 \( Q(D_2) \)를 병합하여 \( Q(D) \)를 생성할 때, 이는 \(\max((\epsilon_1, \epsilon_2))\)-근사 요약으로 구성된다.

• 초기 요약 \( Q(D) = \{S, \tilde{D}, \tilde{D}, \tilde{\omega}D\} \)는 각 값들에 대해 정확한 정보를 제공하는 0-근사 요약으로 정의된다.

• 두 개의 요약을 병합하기 위해 정의된 쿼리 함수 \( g(Q, d) \)는 주어진 순위와 가까운 값을 반환하는 방식으로 작동한다.

5.5. 양자 요약의 유효성 및 가지치기 작업

• 양자 요약 Q(D)는 모든 제약 조건을 만족하며, 이는 유효한 양자 요약임을 나타낸다.

• 가지치기 작업은 메모리 예산 b를 기반으로 새로운 요약 Q'(D)를 생성하며, 이 요약에는 복사된 요소가 포함된다.

• Q'는 원래 요약에서 복사된 무게와 양자 조건을 만족하며, 따라서 유효한 양자 요약이 된다.

• 새로운 요약 Q'(D)는 ((ε) + b)-근사 요약으로, 이 속성을 증명하기 위한 여러 불평등을 결合할 필요가 있다.

• 양자 요약 Q는 메모리 비용을 절감하기 위해 원래 요약의 입력 도메인을 제한하는 효과적인 방법을 제공한다.