Fast Unbalanced Optimal Transport on a Tree
Authors: Ryoma Sato, Makoto Yamada, Hisashi Kashima
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We confirm the effectiveness of the proposed method through numerical experiments. We run the experiments on a Linux server with an Intel Xeon CPU E7-4830 @ 2.00 GHz and 1 TB RAM. We aim to answer the following questions. (Q1) How fast is the proposed method? (Q2) How accurately can tree GKR approximate Euclidean GKR? (Q3) Is the proposed method applicable to large-scale datasets? We also investigate the noise robustness of GKR, but we defer this to the appendices |
| Researcher Affiliation | Academia | Ryoma Sato1,2 Makoto Yamada1,2 Hisashi Kashima1,2 1Kyoto University 2RIKEN AIP {r.sato@ml.ist.i, myamada@i, kashima@i}.kyoto-u.ac.jp |
| Pseudocode | Yes | Algorithm 1 describes the pseudo code of the algorithm. |
| Open Source Code | Yes | Our code including a C++ implementation and Python wrapper for our algorithm is available at https://github.com/joisino/treegkr. |
| Open Datasets | Yes | We use Chicago Crime dataset2, where each measure corresponds to a day and contains Dirac mass in the place where a crime occurred in that day. [...] We use New York taxi dataset3 from November 1, 2015 to January 31, 2016. |
| Dataset Splits | Yes | The scale is determined by 10 training data so that the relative error is minimized (see Appendix E). |
| Hardware Specification | Yes | We run the experiments on a Linux server with an Intel Xeon CPU E7-4830 @ 2.00 GHz and 1 TB RAM. We also conduct the same experiments with a laptop computer with an Intel Core i5-7200U @ 2.50 GHz and 4 GB RAM. |
| Software Dependencies | No | The paper mentions using the Lemon graph library and a C++ implementation of the Sinkhorn algorithm, but does not provide specific version numbers for these software components. |
| Experiment Setup | Yes | For each n = 27, 28, . . . , 220, we generate 10 random trees with n nodes. The amount of mass in each node is an integer drawn from an i.i.d. uniform distribution from 0 to 106. The weight of each edge is also drawn from the same distribution. [...] We compute the GKR distance GKReuc of these measures in the Euclidean space exactly with λd = λc = λ [10 4, 10.0]. We then compute the GKR distance GKRtree of these measures using the quadtree of depth 15 without random translation. |