{ "info": { "author": "Andrew Wrigley", "author_email": "andrew@wrigley.io", "bugtrack_url": null, "classifiers": [ "Development Status :: 3 - Alpha", "Environment :: Console", "Intended Audience :: Science/Research", "License :: OSI Approved :: MIT License", "Operating System :: MacOS :: MacOS X", "Operating System :: POSIX :: Linux", "Operating System :: Unix", "Programming Language :: C++", "Programming Language :: Python :: 3 :: Only", "Topic :: Scientific/Engineering :: Artificial Intelligence" ], "description": "Tensor Belief Propagation\n=========================\n\n|Build Status|\n\n`Tensor Belief\nPropagation `__\n(TBP) is an experimental algorithm for approximate inference in discrete\ngraphical models [1]. At a high level, it takes a factor graph in\n`.uai <#other-file-formats>`__ or `.fg <#other-file-formats>`__ format\nand outputs approximate marginals for each variable.\n\n[1] [Wrigley, Andrew, Wee Sun Lee, and Nan Ye. \"Tensor Belief\nPropagation.\" International Conference on Machine Learning.\n2017.](http://proceedings.mlr.press/v70/wrigley17a/wrigley17a.pdf)\n\nRequirements\n------------\n\n- Linux or OSX\n- Python 3 (tested with 3.6)\n\nInstallation\n------------\n\nInstall with the Python package manager ``pip``:\n\n.. code:: bash\n\n $ pip install tbp\n ...\n Successfully installed tbp-X.X.X\n\nThis will likely take several minutes as libDAI must be compiled.\n\nUsage\n-----\n\nTBP takes a factor graph in either `.fg <#other-file-formats>`__ or\n`.uai <#other-file-formats>`__ format as input, and outputs the\napproximate marginal distribution of each variable in `.MAR\nformat <#other-file-formats>`__. This involves two steps \u2014 first, all\npotential functions in the graph must be decomposed into sums of rank-1\ntensors rather than multidimensional tables, yielding a decomposed\nfactor graph (.dfg). Then, the message passing procedure must be run on\nthe decomposed graph to give approximate marginals.\n\nCommand line\n~~~~~~~~~~~~\n\nAfter installation, the command line utility ``tbp`` is available to do\neither or both of these steps. For full usage instructions, run\n``tbp --help``.\n\nExamples\n^^^^^^^^\n\nDecompose the factor graph ``ising_8x8.fg`` and find marginals:\n\n.. code:: bash\n\n $ tbp tests/ising_8x8.fg\n 64 2 0.594961 0.405039 2 ... 0.608573 0.391427\n\nDecompose input potentials into 3 rank-1 components and save the\nresulting decomposed graph (but don't find marginals):\n\n.. code:: bash\n\n $ tbp tests/ising_8x8.fg -r 3 -o tests/ising_8x8.dfg --verbosity 2\n Reading graph tests/ising_8x8.fg (libDAI format)...\n Decomposing input graph (r=3 terms per factor)...\n Successfully saved decomposed graph to tests/ising_8x8.dfg.\n\nDecompose the factor graph ``Promedus_11.uai`` after applying some\nevidence, find marginals using TBP with sample size of 1000, and save\nthe output to ``out.MAR``:\n\n.. code:: bash\n\n $ tbp tests/uai/MAR_prob/Promedus_11.uai -e tests/uai/MAR_prob/Promedus_11.uai.evid -k 1000 -o out.MAR --verbosity 2\n Reading graph tests/uai/MAR_prob/Promedus_11.uai (UAI format)...\n Applying evidence file tests/uai/MAR_prob/Promedus_11.uai.evid...\n Decomposing input graph (r=4 terms per factor)...\n Running TBP with sample size K=1000...\n Successfully saved marginals to out.MAR.\n\nPython library\n~~~~~~~~~~~~~~\n\nThe ``tbp`` package can also be used directly from Python, for example:\n\n.. code:: python\n\n import tbp\n\n # Load a factor graph in .uai format\n g = tbp.load_uai_graph('tests/uai/MAR_prob/linkage_11.uai')\n\n # Apply evidence (fixed variable assignments)\n g.apply_evidence('tests/uai/MAR_prob/linkage_11.uai.evid')\n\n # Decompose each factor into a weighted sum of 4 rank-1 tensors\n dg = g.decompose(r=4)\n\n # Run TBP to find marginals with sample size of 10000\n mar = dg.tbp_marg(K=10000)\n\nTroubleshooting\n~~~~~~~~~~~~~~~\n\nInstalling into a virtual environment\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nIf you find ``pip install`` has issues with dependencies or version\nconflicts, try installing all the necessary packages into a virtual\nenvironment (i.e. a project-specific folder rather than globally on your\nsystem):\n\n.. code:: bash\n\n $ sudo pip3 install virtualenv # pip or pip3, depending on your system\n $ virtualenv -p python3 venv # create venv folder to store packages\n $ source venv/bin/activate # activate virtual environment\n $ pip install tbp # install tbp into venv folder\n\nNow, anything you ``pip install`` will be stored in the ``venv`` folder,\nand when you invoke ``python`` or ``tbp``, the local versions will be\nused.\n\nBuilding from GitHub clone\n^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nTo use the ``tbp`` Python package from source without installation via\n``pip install``, libDAI must first be compiled. To do this:\n\n.. code:: bash\n\n $ git clone git@github.com:akxlr/tbp.git\n $ cd tbp/libdai\n $ cp Makefile. Makefile.conf # Choose according to your platform\n $ make\n ...\n libDAI built successfully!\n\nThis produces a utility ``libdai/utils/dfgmarg``, which is symlinked\nfrom ``tbp/dfgmarg`` and used during inference.\n\nUsing MATLAB for the decomposition\n----------------------------------\n\nThe decomposition of potential functions uses the non-negative CP\ndecomposition algorithm in the Tensorly tensor library. As an\nalternative to TensorLy, the `MATLAB Tensor\nToolbox `__ can be used\n(this was what we used in [1]). To use this instead of Tensorly:\n\n- Install MATLAB normally\n- Install the `MATLAB Python\n API `__\n- Install the `MATLAB Tensor\n Toolbox `__\n\nYou can now replace ``method='tensorly'`` with ``method='matlab'`` when\ncalling decomposition functions in `core.py `__.\n\nICML experiments\n----------------\n\nThe results from Figure 1 and Figure 3 in [1] can be reproduced with:\n\n::\n\n $ python tbp/icml17.py\n\nNote that these tests take considerable time to finish.\n\nFile formats\n------------\n\n.dfg (decomposed factor graph)\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n\nWe created the ``.dfg`` file format based on `libDAI's .fg file\nformat `__\nto represent decomposed factor graphs. A decomposed factor graph is a\nfactor graph with all factors represented as sums of rank-1 tensors\nrather than multidimensional tables.\n\nThe first line of a ``.dfg`` file contains the number of factors in the\ngraph, followed by a blank line. Then, factors are described in turn by\nblocks separated by a single blank line. Each factor block is structured\nas follows:\n\n::\n\n 1. n_terms\n 2. \n 3. n_variables\n 4. \n 5. \n 6. n_nonzero_1\n 7. 1 0.5\n 8. 3 0.1\n 9. 4 0.1\n 10. ...\n 11. n_nonzero_2\n 12. 1 0.5\n 13. 3 0.1\n 14. 4 0.3\n 15. ...\n\nIn the header section of the factor block (lines 1-5), ``n_terms`` is\nthe number of terms in the decomposition and ````,\n```` and ```` are\nself-explanatory space-separated lists of length ``n_terms``,\n``n_variables`` and ``n_variables`` respectively.\n\nThe remainder of the factor block (line 6 onwards) describes a series of\n``n_variables`` 2D matrices that together describe the ``n_terms``\nrank-1 tensors. Each matrix corresponds to a single variable and has\nshape ``(cardinality, n_terms)``, where ``cardinality`` is the\ncardinality of the variable and ``n_terms`` is the number of rank-1\nterms in the decomposition (constant for all variables). Each matrix\nbegins with the number of nonzero values in the matrix, followed by a\nseries of ``index value`` pairs describing the nonzero entries of the\nmatrix in column-major order. See `libDAI's\ndocumentation `__\nfor examples of how to reshape these lists back into matrices.\n\nThe *i*\\ th rank-1 tensor is constructed by taking the outer product of\nthe *i*\\ th columns of all matrices. The complete factor is then\nreconstructed by adding up these rank-1 tensors and weighting according\nto ````.\n\nOther file formats\n~~~~~~~~~~~~~~~~~~\n\nOther file formats used in this project are:\n\n- ``.fg`` (libDAI factor graph):\n https://staff.fnwi.uva.nl/j.m.mooij/libDAI/doc/fileformats.html\n- ``.uai`` (UAI factor graph):\n http://www.hlt.utdallas.edu/~vgogate/uai14-competition/modelformat.html\n- ``.MAR`` (marginals):\n http://www.hlt.utdallas.edu/~vgogate/uai14-competition/resformat.html\n- ``.evid`` (evidence):\n http://www.hlt.utdallas.edu/~vgogate/uai14-competition/evidformat.html\n\nTo do\n-----\n\n- Add experiments from Figure 2 (random pairwise MRFs)\n- Rewrite code that loads .uai files to handle all problems (currently\n breaks on some)\n- Deal with Z <= 0 warning from C++ code\n- Add more tests\n\nFeedback\n--------\n\nBug reports, suggestions and comments are welcome. Please email\nandrew@wrigley.io or use the issue tracker.\n\nLicense\n-------\n\nSee `LICENSE.txt `__ (MIT).\n\nAcknowledgments\n---------------\n\n- `libDAI `__ (included in\n `libdai `__ folder with modifications; libDAI's junction tree\n implementation is used for the message passing step)\n- `Eigen `__ (version 3.3.4 included in\n `libdai/vendor/include `__ folder)\n- `TensorLy `__ (used to perform\n initial non-negative CP decomposition of potential functions)\n- `MATLAB Tensor\n Toolbox `__\n\n.. |Build Status| image:: https://travis-ci.org/akxlr/tbp.svg?branch=master\n :target: https://travis-ci.org/akxlr/tbp\n", "description_content_type": null, "docs_url": null, "download_url": "https://github.com/akxlr/tbp/archive/0.1.0.tar.gz", "downloads": { "last_day": -1, "last_month": -1, "last_week": -1 }, "home_page": "https://github.com/akxlr/tbp", "keywords": "tensor", "license": "MIT", "maintainer": "", "maintainer_email": "", "name": "tbp", "package_url": "https://pypi.org/project/tbp/", "platform": "", "project_url": "https://pypi.org/project/tbp/", "project_urls": { "Download": "https://github.com/akxlr/tbp/archive/0.1.0.tar.gz", "Homepage": "https://github.com/akxlr/tbp" }, "release_url": "https://pypi.org/project/tbp/0.1.0/", "requires_dist": null, "requires_python": "", "summary": "Tensor Belief Propagation - algorithm for approximate inference in discrete graphical models", "version": "0.1.0" }, "last_serial": 3493087, "releases": { "0.0.38": [ { "comment_text": "", "digests": { "md5": "91d44565d037e63bc2c5c802be5d9979", "sha256": "dd3046aa8c5b2fa505456699bbc5980151b656707a5bb85d4e92d561997f8091" }, "downloads": -1, "filename": "tbp-0.0.38.tar.gz", "has_sig": false, "md5_digest": "91d44565d037e63bc2c5c802be5d9979", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 11209237, "upload_time": "2018-01-04T08:45:32", "url": "https://files.pythonhosted.org/packages/ff/b4/99b46da11ca951f5ab863323834ac966a047adcc0547d4dc66f36a3bd86f/tbp-0.0.38.tar.gz" } ], "0.1.0": [ { "comment_text": "", "digests": { "md5": "2be8372dea901da15d3423bb50771e3a", "sha256": "b4f55da176401bebdb9cc152f2d8ae9c8baee8fd14d8bf080254fd815b6833bb" }, "downloads": -1, "filename": "tbp-0.1.0.tar.gz", "has_sig": false, "md5_digest": "2be8372dea901da15d3423bb50771e3a", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 11204930, "upload_time": "2018-01-16T07:23:49", "url": "https://files.pythonhosted.org/packages/52/3d/1d6537f0def3084ca7dcd5d4758d752d16651267ac80a0dbb00538311772/tbp-0.1.0.tar.gz" } ] }, "urls": [ { "comment_text": "", "digests": { "md5": "2be8372dea901da15d3423bb50771e3a", "sha256": "b4f55da176401bebdb9cc152f2d8ae9c8baee8fd14d8bf080254fd815b6833bb" }, "downloads": -1, "filename": "tbp-0.1.0.tar.gz", "has_sig": false, "md5_digest": "2be8372dea901da15d3423bb50771e3a", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 11204930, "upload_time": "2018-01-16T07:23:49", "url": "https://files.pythonhosted.org/packages/52/3d/1d6537f0def3084ca7dcd5d4758d752d16651267ac80a0dbb00538311772/tbp-0.1.0.tar.gz" } ] }