4 ms·
They (suspiciously but not necessarily intentionally) avoid calling attension to it but: > Let ({fω}ω∈Ω,Ω) be the decomposition that corresponds to N. Label th
by a1369209993 3y ago
They (suspiciously but not necessarily intentionally) avoid calling attension to it but:
> Let ({fω}ω∈Ω,Ω) be the decomposition that corresponds to N. Label the parts 1,...,p.
p is the number of regions the deep network divides R^n into, and is in general exponential in the network depth. (Eg consider R^1 = [-1,+1], L[k](x) = 2*abs(x)-1 ∀k (where abs(x) = x - 2*ReLU(-x), IIRC), which divides R^1 into 2^D equal segments using only D individual ReLUs, assuming I wrote the formulas down correctly.)
So for a arbitrary deep network the shallow network size is definitely exponential in input depth, and while it's not clear whether that's true for typical 'trained' deep networks, I would be surprised if it wasn't.
- uoaei 3y agoI would assume the distinction between trained and untrained networks is a constant factor at best.
- a1369209993 3y agoI meant 'trained' networks in contrast to totally-synthetic intentionally-pathological networks like my 2abs-1 example. (It could be that only pathological cases give bad results - similar to how (Hindley-Milner) type inference is EXPTIME-complete but works fine for ~all real world programs - but that seems unlikely.)