Venue: ICLR 2018 conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: General comments:

The paper is largely inspired by a recent work of Bianchini et al. (2014) on upper bounds of Betti number sums for decision super-level sets of neural networks in different architectures. It explores empirically the relations between Betti numbers of input data and hidden unit complexity in a single hidden layer neural network, in a purpose of finding closer connections on topological complexity or expressibility of neural networks.  

They report the phenomenon of phase transition or turning points in training error as the number of hidden neurons changes in their experiment. The phenomenon of turning points has been observed in many experiments, where usually researchers investigate it through the critical points of training loss such as local optimality and/or saddle points. For the first time, the paper connects the phenomenon with topological complexity of input data and decision super-level sets, as well as number of hidden units, which is inspiring. 

However, a closer look at the experimental study finds some inconsistencies or incompleteness which deserves further investigations. The following are some examples. 

The paper tries to identify a phase transition in number of hidden units, h_phase(D_2) = 10 from the third panel of Figure 4. However, when h=12 hidden units, the curve is above h=10 rather than below it in expectation. Why does the order of errors disagree with the order of architectures if the number of hidden neurons is larger then h_phase?

The author conjecture that if b0 = m, then m+2 hidden neurons are sufficient to get 0 training error.
But the second panel of fig4 seems to be a counterexample of the conjecture. In fact h_phase(D_0 of b_0=2)=4 and h_phase (D_1 of b_0 = 3) = 6, as pointed out by the paper, has a mismatch on such a numerical conjecture.  

In Figure 5, the paper seems to relate the homological complexities of data to the hidden dimensionality in terms of zero training error. What are the relations between the homological complexities of data and homological complexities of decision super-level sets of neural networks in training? Is there any correspondence between them in terms of topological transitions. 

The study is restricted to 2-dimensional synthetic datasets. Although they applied topological tools to low-dimensional projection of some real data, it's purely topological data analysis. They didn't show any connection with the training or learning of neural networks. So this part is just preliminary but incomplete to the main topic of the paper.

The authors need to provide more details about their method and experiments. For example, The author didn't show from which example fig6 is generated. For other figures appended at the end of the paper, there should also be detailed descriptions of the underlying experiments.


Some Details:

Lines in fig4 are difficult to read, there are too many similar colors. Axis labels are also missing.

In fig5, the (4, 0)-item appears twice, but they are different. They should be the same, but they are not.
Any mistake here?

Fig6(a) has the same problem as fig4. Besides, the use of different x-axis makes it difficult to compare with fig4.
fig6(b) needs a color bar to indicate the values of correlations. 

Some typos, e.g. Page 9 Line 2, 'ofPoole' should be 'of Poole'; Line 8, 'practical connectio nbetween' should be 'practical connection between'; line 3 in the 4th paragraph of page 9, 'the their are' seems to be 'there are'. Spell check is recommended before final version. 

review_title: The paper aims to connect topology of data to that of decision super-level sets and boundaries, as a new characterization of the capacity of neural networks. The empirical study is very inspiring, yet the paper can be improved.

final_score: rating: 4: Ok but not good enough - rejection
review_content: The authors propose to use the homology of the data as a measurement of the expressibility of a deep neural network. The paper is mostly experimental. The theoretical section (3.1) is only reciting existing theory (Bianchini et al.). Theorem 3.1 is not surprising either: it basically says spaces with different topologies differ at some parts. 

As for the experiments, the idea is tested on synthetic and real data. On synthetic data, it is shown that the number of neurons of the network is correlated with the homology it can express. On real data, the tool of persistent homology is applied. It is observed that the data in the final layer do have non-trivial signal in terms of persistent homology.

I do like the general idea of the paper. It has great potentials. However, it is much undercooked. In particular, it could be improved as follows:

* 1) the main message of the paper is unclear to me.  Results observed in the synthetic experiments seem to be a confirmation of the known results by Bianchini et al.: the Betti number a network can express is linear to the number of hidden units, h, when the input dimension n is a constant. 

To be convinced, I would like to see much stronger experimental evidence: Reporting results on a single layer network is unsettling. It is known that the network expressibility is highly related to the depth (Eldan & Shamir 2016). So what about networks with more layers? Is the stratification observation statistically significant? These experiments are possible for synthetic data. 

* 2) The usage of persistent homology is not well justified. A major part of the paper is devoted to persistent homology. It is referred to as a robust computation of the homology and is used in the real data experiments. However, persistent homology itself was not originally invented to recover the homology of a fixed space. It was intended to discover homology groups at all different scales (in terms of the function value). Even with the celebrated stability theorem (Cohen-Steiner et al. 2007) and statistical guarantees (Chazal et al. 2015), the relationship between the Vietoris-Rips filtration persistent homology and the homology of the classifier region/boundary is not well established. To make a solid statement, I suggest authors look into the following papers

Homology and robustness of level and interlevel sets
P Bendich, H Edelsbrunner, D Morozov, A Patel, Homology, Homotopy and Applications 15 (1), 51-72, 2013

Herbert Edelsbrunner, Michael Kerber: Alexander Duality for Functions: the Persistent Behavior of Land and Water and Shore. Proceedings of the 28th Annual Symposium on Computational Geometry, pp. 249-258 (SoCG 2012)

There are also existing work on how the homology of a manifold or stratified space can be recovered using its samples. They could be useful. But the settings are different: in this problem, we have samples from the positive/negative regions, rather than the classification boundary. 

Finally, the gap in concepts carries to experiments. When persistent homology of different real data are reported. It is unclear how they reflect the actually topology of the classification region/boundary. There are also significant amount of approximation due to the natural computational limitation of persistent homology. In particular, LLE and subsampling are used for the computation. These methods can significantly hurt persistent homology computation. A much more proper way is via the sparsification approach. 

SimBa: An Efficient Tool for Approximating Rips-Filtration Persistence via Simplicial Batch-Collapse
T. K. Dey, D. Shi and Y. Wang. Euro. Symp. Algorithms (ESA) 2016, 35:1--35:16

* 3) Finally, to support the main thesis, it is crucial to show that the topological measure is revealing information existing ones do not. Some baseline methods such as other geometric information (e.g., volume and curvature) are quite necessary.

* 4) Important papers about persistent homology in learning could be cited:

Using persistent homology in deep convolutional neural network:

Deep Learning with Topological Signatures
C. Hofer, R. Kwitt, M. Niethammer and A. Uhl, NIPS 2017

Using persistent homology as kernels:

Sliced Wasserstein Kernel for Persistence Diagrams
Mathieu Carrière, Marco Cuturi, Steve Oudot, ICML 2017.

* 5) Minor comments:

Small typos here and there: y axis label of Fig 5, conclusion section.


review_title: A good idea, but undercooked

final_score: rating: 3: Clear rejection
review_content: Paper Summary:

This paper looks at empirically measuring neural network architecture expressivity by examining performance on a variety of complex datasets, measuring dataset complexity with algebraic topology. The paper first introduces the notion of topological equivalence for datasets -- a desirable measure to use as it is invariant to superficial differences such as rotation, translation and curvature. The definition of homology from algebraic topology can then be used as a robust measure of the "complexity" of a dataset. This notion of difficulty focuses roughly on determining the number of holes of dimension n (for varying n) there are in the dataset, with more holes roughly leading to a more complex connectivity pattern to learn. They provide a demonstration of this on two synthetic toy datasets in Figure 1, training two (very small -- 12 and 26 neuron) single hidden layer networks on these two datasets, where the smaller of the two networks is unable to learn the data distribution of the second dataset. These synthetic datasets have a well defined data distribution, and for an empirical sample of N points, a (standard) method of determining connectivity by growing epsilon balls around each datapoint in section 2.3.

The authors give a theoretical result on the importance of homology: if a binary classifier has support homology not equal to the homology of the underlying dataset, then there is at least one point that is misclassified by the classifier. Experiments are then performed with single hidden layer networks on synthetic datasets, and a phase transition is observed: if h_phase is the number of hidden units where the phase transition happens, and h' < h < h_phase, h' has higher error and takes longer to converge than h. Finally, the authors touch on computing homology of real datasets, albeit with a low dimensional projection (e.g. down to 3 dimensions for CIFAR-10).

Main Comments

The motivation to consider algebraic topology and dataset difficulty is interesting, but I think this method is ultimately ill suited and unable to be adapted to more complex and interesting settings. In particular, the majority of experiments and justification of this method comes from use on a low dimensional manifold with either known data distribution, or with a densely sampled manifold. (The authors look at using CIFAR-10, but project this down to 3 dimensions -- as current methods for persistent homology cannot scale -- which somewhat invalidates the goal of testing this out on real data.) This is an important and serious drawback because it seems unlikely that the method described in Figure 3 of determining the connectivity patterns of a dataset are likely to yield insightful results in a high dimensional space with very few datapoints (in comparison to 2^{dimension}), where distance between datapoints is unlikely to have any nice class related correspondence.

Furthermore, while part of the motivation of this paper is to use dataset complexity measured with topology to help select architectures, experiments demonstrating that this might be useful are very rudimentary. All experiments only look at single hidden layers, and the toy task in Figure 1 and in section 3.2.1 and Figure 5 use extremely small networks (hidden size 12-26). It's hard to be convinced that these results necessarily generalize even to other larger hidden layer models. On real datasets, exploring architectures does not seem to be done at all (Section 4).


Minor Comments
Some kind of typo in Thm 1? (for all f repeated twice)
Small typos (missing spaces) in related work and conclusion
How is h_phase determined? Empirically? (Or is there a construction?)

Review Summary:

This paper is not ready to be accepted.
review_title: Official Review for Characterizing Neural Network Capacity using Algebraic Topology

Meta-review: This paper attempts to connect the expressivity of neural networks with a measure of topological complexity. The authors present some empirical results on simplified datasets.
All reviewers agreed that this is an intriguing line of research, but that the current manuscript is still presenting preliminary results, and that further work is needed before it can be published. 
Decision: Reject