[Predator] Move ``SingleFeatureScore`` to LLM.

appengine/findit/crash/loglinear/model.py

 # Copyright 2016 The Chromium Authors. All rights reserved.
 # Use of this source code is governed by a BSD-style license that can be
 # found in the LICENSE file.
 
 # TODO(http://crbug.com/669639): there are lots of ways to make the code
 # in this file better. We avoid having separate todos per task; instead
 # see that meta-issue ticket.
 
 import math
 import numpy as np
 # N.B., ``np.array`` can't take generators; you must pass explicit lists.
 
 from libs.math.functions import MemoizedFunction
 from libs.math.logarithms import logsumexp
 from libs.math.vectors import vsum
 
 EPSILON = 0.00001
 
 
-def ToFeatureFunction(fs):
-  """Given an array of scalar-valued functions, return an array-valued function.
-
-  Args:
-    fs (iterable): A collection of curried functions ``X -> Y -> A``.
-      That is, given a particular ``x`` they return a function ``Y -> A``.
-
-  Returns:
-    A function ``X -> Y -> list(A)`` where for all ``x``, ``y``, and
-    ``i`` we have that ``ToFeatureFunction(fs)(x)(y)[i] == fs[i](x)(y)``.
-  """
-  def _FeatureFunction(x):
-    fxs = [f(x) for f in fs]
-    return lambda y: [fx(y) for fx in fxs]
-
-  return _FeatureFunction
-
-
 class UnnormalizedLogLinearModel(object):
   """An unnormalized loglinear model.
 
   We use this model for combining a bunch of different features in order
   to decide who to blame. In particular, the nice thing about loglinear
   models is that (a) they allow separating the amount of weight we
   give to each feature from the feature itself, and (b) they allow us
   to keep adding features at will without needing to worry about the
   fiddly details needed for it to be a probability model.
 
@@ skipping 12 matching lines @@
   rather than returning a probability per se.
   """
 
   def __init__(self, feature_function, weights, epsilon=None):
     """Construct a new model with the given weights and feature function.
 
     Args:
       feature_function: A function ``X -> Y -> list(FeatureValue)``. N.B.,
         for all ``x`` and ``y`` the length of ``feature_function(x)(y)``
         must be the same as the length of ``weights``.
-      weights (list of float): coefficients for how important we consider
-        each component of the feature vector for deciding which ``y``
-        to blame.
+      weights (dict of float): the weights for the features. The keys of
+        the dictionary are the names of the feature that weight is
+        for. We take this argument as a dict rather than as a list so that
+        callers needn't worry about what order to provide the weights in.
       epsilon (float): The absolute-error threshold for considering a
         weight to be "equal to zero". N.B., this should be a positive
         number, as we will compare it against the absolute value of
         each weight.
     """
     if epsilon is None:
       epsilon = EPSILON
-    self._weights = np.array([
-        w if isinstance(w, float) and math.fabs(w) >= epsilon else 0.
-        for w in weights])
+
+    self._weights = {
+        name: weight if isinstance(weight, float) and
+        math.fabs(weight) >= epsilon else 0.

[wrengr, 2017/01/11 20:38:30]

The ``if...`` should be moved to after the ``for...in...``; thus, ``{name:
weight for name, weight in weights.iteritems() if ...}``

[Sharu Jiang, 2017/01/12 01:41:38]

Done.

+        for name, weight in weights.iteritems()
+    }
 
     self._quadrance = None
 
     # TODO(crbug.com/674752): we need better names for ``self._features``.
     def _Features(x):
       """Wrap ``feature_function`` to memoize things and ensure types.
 
       This outer wrapping takes each ``x`` to a memoized instance of
       ``_FeaturesGivenX``. That is, for each ``x`` we return a
-      ``MemoizedFunction`` from ``Y`` to ``list(FeatureValue)``.
+      ``MemoizedFunction`` from ``Y`` to ``dict(str to FeatureValue)``.
       """
       fx = feature_function(x)
       def _FeaturesGivenX(y):
         """Wrap ``feature_function(x)`` to ensure appropriate types.
 
         This inner wrapper ensures that the resulting ``FeatureValue``
         array has the same length as the weight covector.
         """
         fxy = fx(y)
         # N.B., we're assuming that ``len(self.weights)`` is O(1).
         assert len(fxy) == len(self.weights), TypeError(
             "vector length mismatch: %d != %d" % (len(fxy), len(self.weights)))
         return fxy
 
       # Memoize on ``Y``, to ensure we don't need to recompute
       # ``FeatureValue``s nor recheck the lengths.
       return MemoizedFunction(_FeaturesGivenX)
 
     # Memoize on ``X``, to ensure we share the memo tables on ``Y``.
     self._features = MemoizedFunction(_Features)
 
     # TODO(crbug.com/674752): we need better names for ``self._scores``.
     # N.B., this is just the inner product of ``self.weights``
     # against ``self._features(x)``. If we can compute this in some
     # more efficient way, we should. In particular, we will want to
     # make the weights sparse, in which case we need to use a sparse
     # variant of the dot product.
-    self._scores = MemoizedFunction(lambda x:
-        self._features(x).map(lambda fxy:
-            self.weights.dot(np.array([feature.value for feature in fxy]))))
+    self._scores = MemoizedFunction(lambda x: self._features(x).map(
+        lambda fxy: sum(self.SingleFeatureScore(feature)

[wrengr, 2017/01/11 20:38:30]

Should use ``math.fsum`` whenever adding floats; never use ``sum``.

[Sharu Jiang, 2017/01/12 01:41:38]

Done.

+                        for feature in fxy.itervalues())))

[wrengr, 2017/01/11 20:38:30]

N.B., you're not taking advantage of the sparsity of the weights dictionary
here; you're still iterating over all the features. See the first part of
crbug.com/680207

We really want to do ``math.fsum(fxy[i].value * weight_i for i, weight_i in
self._weights.iteritems())``

[Sharu Jiang, 2017/01/12 01:41:38]

That's because I didn't filter those 0 weights in this cl yet, there are some
places in training also need to be changed (while training, it's possible that a
zero weight turns into a non-zero one.), I'd rather do this optimization in
another cl.

Added a todo.

[wrengr, 2017/01/12 18:16:16]

Yeah, the weights will change during training, but once we set the new weight
dict (and clear any weight-dependent memos) none of the methods have any way of
noticing the change; they'll keep on working just fine.

Since this is the CL that makes the weights be stored as a dict, it makes sense
to iterate over self.weights in this CL. Once we do, this method will
automatically start taking advantage of the sparsity of the weights whenever
another CL adds the filtering for that in; no need to go back and change it
again at that point. It's one less thing for the person writing that CL to keep
in mind, one less point for the git diff to break, and besides it's a one-line
change.

+
+  def SingleFeatureScore(self, feature_value):
+    """Returns the score (aka weighted value) of a ``FeatureValue``.
+
+    This function assumes the report's stacktrace has already had any necessary
+    preprocessing (like filtering or truncating) applied.
+
+    Args:
+      feature_value (FeatureValue): the feature value to check.
+
+    Returns:
+      The score of the feature value.
+    """
+    return feature_value.value * self._weights.get(feature_value.name, 0.)
 
   def ClearWeightBasedMemos(self):
     """Clear all the memos that depend on the weight covector."""
     self._quadrance = None
     self._scores.ClearMemos()
 
   def ClearAllMemos(self):
     """Clear all memos, even those independent of the weight covector."""
     self.ClearWeightBasedMemos()
     self._features.ClearMemos()
 
   @property
   def weights(self):
     """The weight covector.
 
-    At present we return the weights as an ``np.ndarray``, but in the
-    future that may be replaced by a more general type which specifies
-    the semantics rather than the implementation details.
+    At present we return the weights as an dict mapping feature name to its
+    weight, but in the future that may be replaced by a more general type which
+    specifies the semantics rather than the implementation details.
     """
     return self._weights
 
   @property
   def l0(self): # pragma: no cover
     """The l0-norm of the weight covector.
 
     N.B., despite being popularly called the "l0-norm", this isn't
     actually a norm in the mathematical sense."""
-    return float(np.count_nonzero(self.weights))
+    return float(np.count_nonzero(self.weights.itervalues()))

[wrengr, 2017/01/11 20:38:30]

You can't use ``np.count_nonzero`` anymore since ``self.weights`` isn't an
np.ndarray anymore. Instead do ``float(len(self.weights))``

[Sharu Jiang, 2017/01/12 01:41:38]

Since I haven't filtered 0 weights yet, I just use 
float(len(self.weights) - self.weights.values().count(0.))

[wrengr, 2017/01/12 18:16:16]

Testing for exact equality with 0.0 isn't reliable. If self.weights isn't
already filtered, then you can use the same ``math.fabs(weight) >= epsilon``
test as in __init__

 
   @property
   def l1(self): # pragma: no cover
     """The l1 (aka: Manhattan) norm of the weight covector."""
-    return math.fsum(math.fabs(w) for w in self.weights)
+    return math.fsum(math.fabs(w) for w in self.weights.itervalues())
 
   @property
   def quadrance(self):
     """The square of the l2 norm of the weight covector.
 
     This value is often more helpful to have direct access to, as it
     avoids the need for non-rational functions (e.g., sqrt) and shows up
     as its own quantity in many places. Also, computing it directly avoids
     the error introduced by squaring the square-root of an IEEE-754 float.
     """
     if self._quadrance is None:
-      self._quadrance = math.fsum(math.fabs(w)**2 for w in self.weights)
+      self._quadrance = math.fsum(
+          math.fabs(w)**2 for w in self.weights.itervalues())
 
     return self._quadrance
 
   @property
   def l2(self):
     """The l2 (aka Euclidean) norm of the weight covector.
 
     If you need the square of the l2-norm, do not use this property.
     Instead, use the ``quadrance`` property which is more accurate than
     squaring this one.
     """
     return math.sqrt(self.quadrance)
 
   def Features(self, x):
     """Returns a function mapping ``y`` to its feature vector given ``x``.
 
     Args:
       x (X): the value of the independent variable.
 
     Returns:
-      A ``MemoizedFunction`` of type ``Y -> np.array(float)``.
+      A ``MemoizedFunction`` of type ``Y -> dict(str to float)``.
     """
     return self._features(x)
 
   def Score(self, x):
     """Returns a function mapping ``y`` to its "score" given ``x``.
 
     Semantically, the "score" of ``y`` given ``x`` is the
     unnormalized log-domain conditional probability of ``y`` given
     ``x``. Operationally, we compute this by taking the inner product
     of the weight covector with the ``Features(x)(y)`` vector. The
@@ skipping 27 matching lines @@
         subset of ``Y`` which has non-zero probability given the
         ``x``. When in doubt about whether some ``y`` has zero probability
         or not, it is always safe/correct to return a larger subset of
         ``Y`` (it'll just take more computation time is all). This is
         needed for computing the partition function and expectation. N.B.,
         we do not actually need to know/enumerate of *all* of ``Y``,
         only the subsets for each ``x``.
       feature_function: A function ``X -> Y -> list(float)``. N.B.,
         for all ``x`` and ``y`` the length of ``feature_function(x)(y)``
         must be the same as the length of ``weights``.
-      weights (list of float): coefficients for how important we consider
-        each component of the feature vector for deciding which ``y``
-        to blame.
+      weights (dict of float): the weights for the features. The keys of
+        the dictionary are the names of the feature that weight is
+        for. We take this argument as a dict rather than as a list so that
+        callers needn't worry about what order to provide the weights in.
       epsilon (float): The absolute-error threshold for considering a
         weight to be "equal to zero". N.B., this should be a positive
         number, as we will compare it against the absolute value of
         each weight.
     """
     super(LogLinearModel, self).__init__(feature_function, weights, epsilon)
 
     self._Y = Y_given_X
 
     def _LogZ(x):
@@ skipping 70 matching lines @@
       function returns; rather, it's a sort of average of all the results
       returned. For more information you can take a look at Wikipedia
       <https://en.wikipedia.org/wiki/Expected_value>.
     """
     prob_given_x = self.Probability(x)
     # N.B., the ``*`` below is vector scaling! If we want to make this
     # method polymorphic in the return type of ``f`` then we'll need an
     # API that provides both scaling and ``vsum``.
     return vsum([prob_given_x(y) * f(y) for y in self._Y(x)])