Repository: pgmpy/pgmpy
Pull request #976 (2018-02-20 08:32:18)

Feature/structure search score cache
### Your checklist for this pull request
🚨Please review the [guidelines for contributing](CONTRIBUTING.md) to this repository.

- [ ] Make sure you are requesting to **pull a topic/feature/bugfix branch** (right side). Don't request your master!
- [ ] Make sure you are making a pull request against the **dev branch** (left side). Also you should start *your branch* off *our dev*.
- [ ] Check the commit's or even all commits' message styles matches our requested structure.
- [ ] Check your code additions will fail neither code linting checks nor unit test.

#### Changes
Please list the proposed changes in this pull request.
- Wrapper class for StructureScore instances with a dynamically sized cache for local scores

💔Thank you!


ankurankan: @julianreichinger Thanks a lot for the PR. But one of the tests is failing on python 2.7: https://travis-ci.org/pgmpy/pgmpy/jobs/343734794#L845. And it's because python 2.7 doesn't have `unittest.mock`, and for dealing with that we use the mock module: https://mock.readthedocs.io/en/latest/. Could you please fix the tests (can either have a try except in imports or just replace with the mock module) ?
codecov[bot]: # [Codecov](https://codecov.io/gh/pgmpy/pgmpy/pull/976?src=pr&el=h1) Report
> Merging [#976](https://codecov.io/gh/pgmpy/pgmpy/pull/976?src=pr&el=desc) into [dev](https://codecov.io/gh/pgmpy/pgmpy/commit/a9e69513d6b3557a1e35292820bb31971b4c2ec4?src=pr&el=desc) will **increase** coverage by `0.03%`.
> The diff coverage is `98.97%`.

[![Impacted file tree graph](https://codecov.io/gh/pgmpy/pgmpy/pull/976/graphs/tree.svg?src=pr&token=UaJMCdHaEF&width=650&height=150)](https://codecov.io/gh/pgmpy/pgmpy/pull/976?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##              dev     #976      +/-   ##
==========================================
+ Coverage   94.73%   94.77%   +0.03%     
==========================================
  Files         114      116       +2     
  Lines       11216    11314      +98     
==========================================
+ Hits        10626    10723      +97     
- Misses        590      591       +1
```


| [Impacted Files](https://codecov.io/gh/pgmpy/pgmpy/pull/976?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pgmpy/estimators/ScoreCache.py](https://codecov.io/gh/pgmpy/pgmpy/pull/976/diff?src=pr&el=tree#diff-cGdtcHkvZXN0aW1hdG9ycy9TY29yZUNhY2hlLnB5) | `100% <100%> (ø)` | |
| [pgmpy/tests/test\_estimators/test\_ScoreCache.py](https://codecov.io/gh/pgmpy/pgmpy/pull/976/diff?src=pr&el=tree#diff-cGdtcHkvdGVzdHMvdGVzdF9lc3RpbWF0b3JzL3Rlc3RfU2NvcmVDYWNoZS5weQ==) | `98.18% <98.18%> (ø)` | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pgmpy/pgmpy/pull/976?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/pgmpy/pgmpy/pull/976?src=pr&el=footer). Last update [a9e6951...db30cb9](https://codecov.io/gh/pgmpy/pgmpy/pull/976?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

julianreichinger: @ankurankan Tests are fixed, I replaced the unittest.mock package.
julianreichinger: @ankurankan I made the change you requested and squashed the commits. Actually I have never done that before but it is nice to finally learn my way around Git.
julianreichinger: @ankurankan Sorry, I misunderstood what you meant. I read through the numpy examples and changed the docstrings accordingly. Hopefully everything should be correct now.
julianreichinger: @ankurankan Any update?
ankurankan: @julianreichinger Looks good. Merging. Sorry for the delay.

Patch:
diff --git a/pgmpy/estimators/ScoreCache.py b/pgmpy/estimators/ScoreCache.py
new file mode 100644
index 00000000..bb9a13bf
--- /dev/null
+++ b/pgmpy/estimators/ScoreCache.py
@@ -0,0 +1,107 @@
+#!/usr/bin/env python
+from pgmpy.estimators import StructureScore
+
+
+class ScoreCache(StructureScore):
+
+    def __init__(self, base_scorer, data, max_size=10000, **kwargs):
+        """
+        A wrapper class for StructureScore instances, which implement a decomposable score,
+        that caches local scores.
+        Based on the global decomposition property of Bayesian networks for decomposable scores.
+
+        Parameters
+        ----------
+        base_scorer: StructureScore instance
+             Has to be a decomposable score.
+        data: pandas DataFrame instance
+            DataFrame instance where each column represents one variable.
+            (If some values in the data are missing the data cells should be set to `numpy.NaN`.
+            Note that pandas converts each column containing `numpy.NaN`s to dtype `float`.)
+        max_size: int (optional, default 10_000)
+            The maximum number of elements allowed in the cache. When the limit is reached, the least recently used
+            entries will be discarded.
+        **kwargs
+            Additional arguments that will be handed to the super constructor.
+
+        Reference
+        ---------
+        Koller & Friedman, Probabilistic Graphical Models - Principles and Techniques, 2009
+        Section 18.3
+        """
+        assert isinstance(base_scorer, StructureScore), "Base scorer has to be of type StructureScore."
+
+        self.base_scorer = base_scorer
+        self.cache = LRUCache(original_function=self._wrapped_original, max_size=int(max_size))
+        super(ScoreCache, self).__init__(data, **kwargs)
+
+    def local_score(self, variable, parents):
+        hashable = tuple(parents)
+        return self.cache(variable, hashable)
+
+    def _wrapped_original(self, variable, parents):
+        expected = list(parents)
+        return self.base_scorer.local_score(variable, expected)
+
+
+# link fields
+_PREV, _NEXT, _KEY, _VALUE = 0, 1, 2, 3
+
+
+class LRUCache:
+
+    def __init__(self, original_function, max_size=10000):
+        """
+        Least-Recently-Used cache.
+        Acts as a wrapper around a arbitrary function and caches the return values.
+
+        Based on the implementation of Raymond Hettinger
+        (https://stackoverflow.com/questions/2437617/limiting-the-size-of-a-python-dictionary)
+
+        Parameters
+        ----------
+        original_function: callable
+            The original function that will be wrapped. Return values will be cached.
+            The function parameters have to be hashable.
+        max_size: int (optional, default 10_000)
+            The maximum number of elements allowed within the cache. If the size would be exceeded,
+            the least recently used element will be removed from the cache.
+        """
+        self.original_function = original_function
+        self.max_size = max_size
+        self.mapping = {}
+
+        # oldest
+        self.head = [None, None, None, None]
+        # newest
+        self.tail = [self.head, None, None, None]
+        self.head[_NEXT] = self.tail
+
+    def __call__(self, *key):
+        mapping, head, tail = self.mapping, self.head, self.tail
+
+        link = mapping.get(key, head)
+        if link is head:
+            # Not yet in map
+            value = self.original_function(*key)
+            if len(mapping) >= self.max_size:
+                # Unlink the least recently used element
+                old_prev, old_next, old_key, old_value = head[_NEXT]
+                head[_NEXT] = old_next
+                old_next[_PREV] = head
+                del mapping[old_key]
+            # Add new value as most recently used element
+            last = tail[_PREV]
+            link = [last, tail, key, value]
+            mapping[key] = last[_NEXT] = tail[_PREV] = link
+        else:
+            # Unlink element from current position
+            link_prev, link_next, key, value = link
+            link_prev[_NEXT] = link_next
+            link_next[_PREV] = link_prev
+            # Add as most recently used element
+            last = tail[_PREV]
+            last[_NEXT] = tail[_PREV] = link
+            link[_PREV] = last
+            link[_NEXT] = tail
+        return value


Test patch:
diff --git a/pgmpy/tests/test_estimators/test_ScoreCache.py b/pgmpy/tests/test_estimators/test_ScoreCache.py
new file mode 100644
index 00000000..6b3d0b3b
--- /dev/null
+++ b/pgmpy/tests/test_estimators/test_ScoreCache.py
@@ -0,0 +1,74 @@
+import unittest
+from mock import Mock, MagicMock, call
+from pgmpy.estimators.ScoreCache import LRUCache, ScoreCache
+from pgmpy.estimators import BicScore
+import pandas as pd
+
+
+class TestScoreCache(unittest.TestCase):
+
+    def test_caching(self):
+        function_mock = Mock(side_effect=[1, 2])
+        cache = LRUCache(function_mock, max_size=2)
+
+        self.assertEqual(cache("key1"), 1)
+        self.assertEqual(cache("key2"), 2)
+
+        # Test will fail if the cache calls the function mock again
+        self.assertEqual(cache("key2"), 2)
+        self.assertEqual(cache("key1"), 1)
+        self.assertEqual(cache("key1"), 1)
+
+    def test_small_cache(self):
+        function_mock = Mock(side_effect=lambda key: {"key1": 1, "key2": 2}[key])
+        cache = LRUCache(function_mock, max_size=1)
+
+        cache("key1")
+        cache("key1")  # cached
+        cache("key1")  # cached
+        cache("key2")
+        cache("key2")  # cached
+        cache("key1")
+
+        expected_function_calls = [call("key1"), call("key2"), call("key1")]
+        function_mock.assert_has_calls(expected_function_calls, any_order=False)
+
+    def test_remove_least_recently_used(self):
+        function_mock = Mock(side_effect=lambda key: {"key1": 1, "key2": 2, "key3": 3}[key])
+        cache = LRUCache(function_mock, max_size=2)
+
+        cache("key1")
+        cache("key2")
+        cache("key3")  # kicks out 'key1'
+        cache("key2")  # cached
+        cache("key1")
+
+        expected_function_calls = [call("key1"), call("key2"), call("key3"), call("key1")]
+        function_mock.assert_has_calls(expected_function_calls, any_order=False)
+
+    def test_score_cache_invalid_scorer(self):
+        with self.assertRaises(AssertionError) as e:
+            ScoreCache("invalid_scorer", None)
+
+    def test_score_cache(self):
+
+        def local_scores(*args):
+            if args == ("key1", ["key2", "key3"]):
+                return -1
+            if args == ("key2", ["key3"]):
+                return -2
+
+            assert False, "Unhandled arguments"
+
+        data = pd.DataFrame({"key1": [1, 2], "key2": [1, 2]})
+        base_scorer = MagicMock(spec=BicScore)
+        base_scorer.local_score = Mock(side_effect=local_scores)
+        cache = ScoreCache(base_scorer, data)
+
+        self.assertEqual(cache.local_score("key1", ["key2", "key3"]), -1)
+        self.assertEqual(cache.local_score("key1", ["key2", "key3"]), -1)  # cached
+        self.assertEqual(cache.local_score("key2", ["key3"]), -2)
+        self.assertEqual(cache.local_score("key2", ["key3"]), -2)  # cached
+
+        expected_function_calls = [call("key1", ["key2", "key3"]), call("key2", ["key3"])]
+        base_scorer.local_score.assert_has_calls(expected_function_calls, any_order=False)