To investigate depth efficiency, one intuitive idea is to compare the representation efficiency between deep networks and shallow ones.
Bengio and Delalleau [1]}, [2]} investigate the depth efficiency problem on deep sum-product networks (SPN for short). An SPN consists of neurons computing either products or weighted sums of their inputs.
They consider two families of functions built from deep sum-product networks. The first family of functions is
\(F= \cup _{n \ge 4}F_n\) ,
where \(F_n\)  is the family of functions represented by deep SPNs with \(n=2^k\)  inputs and depth \(k\) . The second family of functions is \(G = \cup _{n\ge 2, i\ge 0} G_{i,n}\) ,
where \(G_{i,n}\)  is the family of functions represented by SPNs with \(n\)  inputs and depth \(2i+1\) .
