CaltechAUTHORS
  A Caltech Library Service

Entropic Causality and Greedy Minimum Entropy Coupling

Kocaoglu, Murat and Dimakis, Alexandros G. and Vishwanath, Sriram and Hassibi, Babak (2017) Entropic Causality and Greedy Minimum Entropy Coupling. In: 2017 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscatway, NJ, pp. 1465-1469. ISBN 978-1-5090-4096-4. http://resolver.caltech.edu/CaltechAUTHORS:20170816-170538199

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20170816-170538199

Abstract

We study the problem of identifying the causal relationship between two discrete random variables from observational data. We recently proposed a novel framework called entropie causality that works in a very general functional model but makes the assumption that the unobserved exogenous variable has small entropy in the true causal direction. This framework requires the solution of a minimum entropy coupling problem: Given marginal distributions of m discrete random variables, each on n states, find the joint distribution with minimum entropy, that respects the given marginals. This corresponds to minimizing a concave function of n^m variables over a convex polytope defined by nm linear constraints, called a transportation polytope. Unfortunately, it was recently shown that this minimum entropy coupling problem is NP-hard, even for 2 variables with n states. Even representing points (joint distributions) over this space can require exponential complexity (in n, m) if done naively. In our recent work we introduced an efficient greedy algorithm to find an approximate solution for this problem. In this paper we analyze this algorithm and establish two results: that our algorithm always finds a local minimum and also is within an additive approximation error from the unknown global optimum.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/ISIT.2017.8006772DOIArticle
http://ieeexplore.ieee.org/document/8006772/PublisherArticle
Additional Information:© 2017 IEEE. This research has been supported by NSF Grants CCF 1344364, 1407278, 1422549, 1618689, 1564167, ONR N000141512009 and ARO YIP W911NF-14-1-0258. The work of Babak Hassibi has been supported in part by the National Science Foundation under grants CNS-0932428, CCF-1018927, CCF-1423663 and CCF-1409204, by a grant from Qualcomm Inc., by NASA’s Jet Propulsion Laboratory through the President and Director’s Fund, and by King Abdullah University of Science and Technology.
Funders:
Funding AgencyGrant Number
NSFCCF-1344364
NSFCCF-1407278
NSFCCF-1422549
NSFCCF-1618689
NSFCCF-1564167
Office of Naval Research (ONR)N000141512009
Army Research Office (ARO)W911NF-14-1-0258
NSFCNS-0932428
NSFCCF-1018927
NSFCCF-1423663
NSFCCF-1409204
Qualcomm Inc.UNSPECIFIED
JPL President and Director's FundUNSPECIFIED
King Abdullah University of Science and Technology (KAUST)UNSPECIFIED
Record Number:CaltechAUTHORS:20170816-170538199
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20170816-170538199
Official Citation:M. Koeaoglu, A. G. Dimakis, S. Vishwanath and B. Hassibi, "Entropie causality anc greedy minimum entropy coupling," 2017 IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, 2017, pp. 1465-1469. doi: 10.1109/ISIT.2017.8006772
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:80537
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:17 Aug 2017 16:13
Last Modified:17 Aug 2017 18:45

Repository Staff Only: item control page