<p>Gopalan, Kalai, Klivans gave an algorithm 
<a href="https://dl.acm.org/citation.cfm?id=1374376.1374451" rel="nofollow noreferrer">https://dl.acm.org/citation.cfm?id=1374376.1374451</a>
for agnostically learning decision trees <span class="math-container">$h:\{0,1\}^n\to\{0,1\}$</span> under the uniform distribution given black-box query access to a target function. They use discrete Fourier analysis. Question: How might one extend this to learning decision trees over <span class="math-container">$\mathbb{R}^n$</span>? Obviously there is no "uniform distribution", unless we limit the domain to a (say) ball, which I'm perfectly happy to do.</p>

CC BY-SA 4.0
2019-06-04T17:25:29.643Z
A hazy idea: their proof doesn't extend to the Gaussian measure, using Hermite instead of Fourier (and mimicking the argument)?
Clement C.
CC BY-SA 4.0
2019-06-04T21:41:28.290Z
Hmm, interesting idea, I'll give it some thought.
Aryeh
<machine-learning><lg.learning><fourier-analysis><pac-learning>
Agnostic query learning of decision trees
Aryeh
# Agnostic query learning of decision trees

(Asked by: username_0 on 2019-06-04)

Gopalan, Kalai, Klivans gave an algorithm
<https://dl.acm.org/citation.cfm?id=1374376.1374451>
for agnostically learning decision trees $h:\{0,1\}^n\to\{0,1\}$ under the uniform distribution given black-box query access to a target function. They use discrete Fourier analysis. Question: How might one extend this to learning decision trees over $\mathbb{R}^n$? Obviously there is no "uniform distribution", unless we limit the domain to a (say) ball, which I'm perfectly happy to do.

**Tags:** machine-learning, lg.learning, fourier-analysis, pac-learning
> **Comments:**
> **username_1**: A hazy idea: their proof doesn't extend to the Gaussian measure, using Hermite instead of Fourier (and mimicking the argument)?  
> **username_0**: Hmm, interesting idea, I'll give it some thought.  

---

## 0 answers

