IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0201126.html
   My bibliography  Save this article

Fast and exact search for the partition with minimal information loss

Author

Listed:
  • Shohei Hidaka
  • Masafumi Oizumi

Abstract

In analysis of multi-component complex systems, such as neural systems, identifying groups of units that share similar functionality will aid understanding of the underlying structures of the system. To find such a grouping, it is useful to evaluate to what extent the units of the system are separable. Separability or inseparability can be evaluated by quantifying how much information would be lost if the system were partitioned into subsystems, and the interactions between the subsystems were hypothetically removed. A system of two independent subsystems are completely separable without any loss of information while a system of strongly interacted subsystems cannot be separated without a large loss of information. Among all the possible partitions of a system, the partition that minimizes the loss of information, called the Minimum Information Partition (MIP), can be considered as the optimal partition for characterizing the underlying structures of the system. Although the MIP would reveal novel characteristics of the neural system, an exhaustive search for the MIP is numerically intractable due to the combinatorial explosion of possible partitions. Here, we propose a computationally efficient search to precisely identify the MIP among all possible partitions by exploiting the submodularity of the measure of information loss, when the measure of information loss is submodular. Submodularity is a mathematical property of set functions which is analogous to convexity in continuous functions. Mutual information is one such submodular information loss function, and is a natural choice for measuring the degree of statistical dependence between paired sets of random variables. By using mutual information as a loss function, we show that the search for MIP can be performed in a practical order of computational time for a reasonably large system (N = 100 ∼ 1000). We also demonstrate that MIP search allows for the detection of underlying global structures in a network of nonlinear oscillators.

Suggested Citation

  • Shohei Hidaka & Masafumi Oizumi, 2018. "Fast and exact search for the partition with minimal information loss," PLOS ONE, Public Library of Science, vol. 13(9), pages 1-14, September.
  • Handle: RePEc:plo:pone00:0201126
    DOI: 10.1371/journal.pone.0201126
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0201126
    Download Restriction: no

    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0201126&type=printable
    Download Restriction: no

    File URL: https://libkey.io/10.1371/journal.pone.0201126?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Kenneth D. Harris & Jozsef Csicsvari & Hajime Hirase & George Dragoi & György Buzsáki, 2003. "Organization of cell assemblies in the hippocampus," Nature, Nature, vol. 424(6948), pages 552-556, July.
    2. Elad Schneidman & Michael J. Berry & Ronen Segev & William Bialek, 2006. "Weak pairwise correlations imply strongly correlated network states in a neural population," Nature, Nature, vol. 440(7087), pages 1007-1012, April.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Einat Granot-Atedgi & Gašper Tkačik & Ronen Segev & Elad Schneidman, 2013. "Stimulus-dependent Maximum Entropy Models of Neural Population Codes," PLOS Computational Biology, Public Library of Science, vol. 9(3), pages 1-14, March.
    2. Seif Eldawlatly & Karim G Oweiss, 2011. "Millisecond-Timescale Local Network Coding in the Rat Primary Somatosensory Cortex," PLOS ONE, Public Library of Science, vol. 6(6), pages 1-14, June.
    3. Guillaume Viejo & Thomas Cortier & Adrien Peyrache, 2018. "Brain-state invariant thalamo-cortical coordination revealed by non-linear encoders," PLOS Computational Biology, Public Library of Science, vol. 14(3), pages 1-25, March.
    4. Lipovetsky, Stan, 2018. "Quantum paradigm of probability amplitude and complex utility in entangled discrete choice modeling," Journal of choice modelling, Elsevier, vol. 27(C), pages 62-73.
    5. Mark L Ioffe & Michael J Berry II, 2017. "The structured ‘low temperature’ phase of the retinal population code," PLOS Computational Biology, Public Library of Science, vol. 13(10), pages 1-31, October.
    6. Katarína Bod’ová & Enikő Szép & Nicholas H Barton, 2021. "Dynamic maximum entropy provides accurate approximation of structured population dynamics," PLOS Computational Biology, Public Library of Science, vol. 17(12), pages 1-22, December.
    7. MohammadReza Zahedian & Mahsa Bagherikalhor & Andrey Trufanov & G. Reza Jafari, 2022. "Financial Crisis in the Framework of Non-zero Temperature Balance Theory," Papers 2202.03198, arXiv.org.
    8. Gaëlle Desbordes & Jianzhong Jin & Chong Weng & Nicholas A Lesica & Garrett B Stanley & Jose-Manuel Alonso, 2008. "Timing Precision in Population Coding of Natural Scenes in the Early Visual System," PLOS Biology, Public Library of Science, vol. 6(12), pages 1-11, December.
    9. Yasser Roudi & Sheila Nirenberg & Peter E Latham, 2009. "Pairwise Maximum Entropy Models for Studying Large Biological Systems: When They Can Work and When They Can't," PLOS Computational Biology, Public Library of Science, vol. 5(5), pages 1-18, May.
    10. Maulana, Ardian & Situngkir, Hokky, 2015. "Korelasi Bebas-skala dalam Studi Geo-politik Pemilihan [Scale-free correlation within Geopolitics of Election Studies]," MPRA Paper 66351, University Library of Munich, Germany.
    11. Remus Oşan & Liping Zhu & Shy Shoham & Joe Z Tsien, 2007. "Subspace Projection Approaches to Classification and Visualization of Neural Network-Level Encoding Patterns," PLOS ONE, Public Library of Science, vol. 2(5), pages 1-14, May.
    12. Hideaki Shimazaki & Shun-ichi Amari & Emery N Brown & Sonja Grün, 2012. "State-Space Analysis of Time-Varying Higher-Order Spike Correlation for Multiple Neural Spike Train Data," PLOS Computational Biology, Public Library of Science, vol. 8(3), pages 1-27, March.
    13. Timothy R Lezon & Ivet Bahar, 2010. "Using Entropy Maximization to Understand the Determinants of Structural Dynamics beyond Native Contact Topology," PLOS Computational Biology, Public Library of Science, vol. 6(6), pages 1-12, June.
    14. Xiaoyuan Liu & Hayato Ushijima-Mwesigwa & Avradip Mandal & Sarvagya Upadhyay & Ilya Safro & Arnab Roy, 2022. "Leveraging special-purpose hardware for local search heuristics," Computational Optimization and Applications, Springer, vol. 82(1), pages 1-29, May.
    15. Sacha Jennifer van Albada & Moritz Helias & Markus Diesmann, 2015. "Scalability of Asynchronous Networks Is Limited by One-to-One Mapping between Effective Connectivity and Correlations," PLOS Computational Biology, Public Library of Science, vol. 11(9), pages 1-37, September.
    16. Dhanya Parameshwaran & Upinder S Bhalla, 2013. "Theta Frequency Background Tunes Transmission but Not Summation of Spiking Responses," PLOS ONE, Public Library of Science, vol. 8(1), pages 1-12, January.
    17. Sahar Gelfman & Quanli Wang & Yi-Fan Lu & Diana Hall & Christopher D Bostick & Ryan Dhindsa & Matt Halvorsen & K Melodi McSweeney & Ellese Cotterill & Tom Edinburgh & Michael A Beaumont & Wayne N Fran, 2018. "meaRtools: An R package for the analysis of neuronal networks recorded on microelectrode arrays," PLOS Computational Biology, Public Library of Science, vol. 14(10), pages 1-20, October.
    18. Jason S Prentice & Olivier Marre & Mark L Ioffe & Adrianna R Loback & Gašper Tkačik & Michael J Berry II, 2016. "Error-Robust Modes of the Retinal Population Code," PLOS Computational Biology, Public Library of Science, vol. 12(11), pages 1-32, November.
    19. Asako Noguchi & Roman Huszár & Shota Morikawa & György Buzsáki & Yuji Ikegaya, 2022. "Inhibition allocates spikes during hippocampal ripples," Nature Communications, Nature, vol. 13(1), pages 1-14, December.
    20. Simona Cocco & Remi Monasson & Martin Weigt, 2013. "From Principal Component to Direct Coupling Analysis of Coevolution in Proteins: Low-Eigenvalue Modes are Needed for Structure Prediction," PLOS Computational Biology, Public Library of Science, vol. 9(8), pages 1-17, August.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:plo:pone00:0201126. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.