You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mxnet.apache.org by GitBox <gi...@apache.org> on 2018/03/09 03:47:58 UTC
[GitHub] zihaolucky closed pull request #9195: [WIP]NCE loss gluon
zihaolucky closed pull request #9195: [WIP]NCE loss gluon
URL: https://github.com/apache/incubator-mxnet/pull/9195
This is a PR merged from a forked repository.
As GitHub hides the original diff on merge, it is displayed below for
the sake of provenance:
As this is a foreign pull request (from a fork), the diff is supplied
below (as it won't show otherwise due to GitHub magic):
diff --git a/example/gluon/sampler/alias_method.py b/example/gluon/sampler/alias_method.py
new file mode 100644
index 00000000000..0e5ebe5923c
--- /dev/null
+++ b/example/gluon/sampler/alias_method.py
@@ -0,0 +1,154 @@
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements. See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership. The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License. You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing,
+# software distributed under the License is distributed on an
+# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+# KIND, either express or implied. See the License for the
+# specific language governing permissions and limitations
+# under the License.
+
+# coding: utf-8
+# pylint: skip-file
+import mxnet.ndarray as nd
+import numpy as np
+from mxnet.test_utils import verify_generator
+
+
+class AliasMethodSampler(object):
+ """ The Alias Method: Efficient Sampling with Many Discrete Outcomes.
+ Can be use in NCELoss.
+
+ Parameters
+ ----------
+ K : int
+ Number of events.
+ probs : array
+ Probability of each events, corresponds to K.
+
+ References
+ -----------
+ https://hips.seas.harvard.edu/blog/2013/03/03/the-alias-method-efficient-sampling-with-many-discrete-outcomes/
+ """
+
+ def __init__(self, F, K, probs):
+ if K != len(probs):
+ raise ValueError("K should be equal to len(probs). K:%d, len(probs):%d" % (K, len(probs)))
+ self.K = K
+ self.prob = F.zeros(K)
+ self.alias = F.zeros(K).astype('int32')
+
+ # Sort the data into the outcomes with probabilities
+ # that are larger and smaller than 1/K.
+ smaller = []
+ larger = []
+ for kk, prob in enumerate(probs):
+ self.prob[kk] = K * prob
+ if self.prob[kk] < 1.0:
+ smaller.append(kk)
+ else:
+ larger.append(kk)
+
+ # Loop though and create little binary mixtures that
+ # appropriately allocate the larger outcomes over the
+ # overall uniform mixture.
+ while len(smaller) > 0 and len(larger) > 0:
+ small = smaller.pop()
+ large = larger.pop()
+
+ self.alias[small] = large
+ self.prob[large] = (self.prob[large] - 1.0) + self.prob[small]
+
+ if self.prob[large] < 1.0:
+ smaller.append(large)
+ else:
+ larger.append(large)
+
+ for last_one in smaller + larger:
+ self.prob[last_one] = 1
+
+ def draw(self, F, n):
+ """Draw N samples from multinomial
+ """
+ samples = F.zeros(n, dtype='int32')
+
+ kk = F.floor(F.random.uniform(0, self.K, n)).astype('int32')
+ rand = F.random.uniform(0, 1, n)
+
+ prob = self.prob[kk]
+ alias = self.alias[kk]
+
+ for i in xrange(n):
+ if rand[i] < prob[i]:
+ samples[i] = kk[i]
+ else:
+ samples[i] = alias[i]
+ return samples
+
+
+def speed():
+ # use numpy
+ import time
+ import numpy.random as npr
+
+ K = 500
+ N = 10000
+
+ # Get a random probability vector.
+ probs = npr.dirichlet(np.ones(K), 1).ravel()
+
+ # Construct the table.
+ elaps = []
+ F = nd
+ alias_method_sampler = AliasMethodSampler(F, K, probs)
+ for i in range(100):
+ start = time.time()
+ X = alias_method_sampler.draw(F, N)
+ time_elaps = time.time() - start
+ elaps.append(time_elaps)
+ print(
+ 'Use NDArray. Avg:%.2f ms, Min:%.2f ms, Max:%.2f ms, Std:%.2f ms'
+ % (np.average(elaps), np.min(elaps), np.max(elaps), np.std(elaps)))
+
+ # Construct the table.
+ elaps = []
+ F = nd
+ alias_method_sampler = AliasMethodSampler(F, K, probs)
+ for i in range(100):
+ start = time.time()
+ X = alias_method_sampler.draw(F, N)
+ time_elaps = time.time() - start
+ elaps.append(time_elaps)
+ print(
+ 'Use Numpy. Avg:%.2f ms, Min:%.2f ms, Max:%.2f ms, Std:%.2f ms'
+ % (np.average(elaps), np.min(elaps), np.max(elaps), np.std(elaps)))
+
+
+def chi_square_test():
+ probs = [0.1, 0.2, 0.3, 0.05, 0.15, 0.2]
+ buckets = list(range(6))
+
+ F = np
+ alias_method_sampler = AliasMethodSampler(F, len(probs), probs)
+
+ generator_mx = lambda x: alias_method_sampler.draw(F, x)
+ verify_generator(generator_mx, buckets, probs)
+
+ generator_mx_same_seed = \
+ lambda x: np.concatenate(
+ [alias_method_sampler.draw(F, x // 10) for _ in range(10)]
+ )
+ verify_generator(generator=generator_mx_same_seed, buckets=buckets, probs=probs)
+
+
+if __name__ == '__main__':
+ speed()
+ chi_square_test()
+
diff --git a/python/mxnet/gluon/data/sampler.py b/python/mxnet/gluon/data/sampler.py
index 66d6cfb2979..0dcdbc76c0f 100644
--- a/python/mxnet/gluon/data/sampler.py
+++ b/python/mxnet/gluon/data/sampler.py
@@ -18,9 +18,11 @@
# coding: utf-8
# pylint: disable=
"""Dataset sampler."""
-__all__ = ['Sampler', 'SequentialSampler', 'RandomSampler', 'BatchSampler']
+__all__ = ['Sampler', 'SequentialSampler', 'RandomSampler', 'BatchSampler', 'AliasMethodSampler']
import random
+from ... import nd
+
class Sampler(object):
"""Base class for samplers.
@@ -136,3 +138,74 @@ def __len__(self):
raise ValueError(
"last_batch must be one of 'keep', 'discard', or 'rollover', " \
"but got %s"%self._last_batch)
+
+
+class AliasMethodSampler(object):
+ """ The Alias Method: Efficient Sampling with Many Discrete Outcomes.
+ Can be use in NCELoss.
+
+ Parameters
+ ----------
+ K : int
+ Number of events.
+ probs : array
+ Probability of each events, corresponds to K.
+
+ References
+ -----------
+ https://hips.seas.harvard.edu/blog/2013/03/03/the-alias-method-efficient-sampling-with-many-discrete-outcomes/
+ """
+ def __init__(self, K, probs):
+ if K != len(probs):
+ raise ValueError("K should be equal to len(probs). K:%d, len(probs):%d" % (K, len(probs)))
+ self.K = K
+ self.prob = nd.zeros(K)
+ self.alias = nd.zeros(K, dtype='int32')
+
+ # Sort the data into the outcomes with probabilities
+ # that are larger and smaller than 1/K.
+ smaller = []
+ larger = []
+ for kk, prob in enumerate(probs):
+ self.prob[kk] = K*prob
+ if self.prob[kk] < 1.0:
+ smaller.append(kk)
+ else:
+ larger.append(kk)
+
+ # Loop though and create little binary mixtures that
+ # appropriately allocate the larger outcomes over the
+ # overall uniform mixture.
+ while len(smaller) > 0 and len(larger) > 0:
+ small = smaller.pop()
+ large = larger.pop()
+
+ self.alias[small] = large
+ self.prob[large] = (self.prob[large] - 1.0) + self.prob[small]
+
+ if self.prob[large] < 1.0:
+ smaller.append(large)
+ else:
+ larger.append(large)
+
+ for last_one in smaller+larger:
+ self.prob[last_one] = 1
+
+ def draw(self, n):
+ """Draw N samples from multinomial
+ """
+ samples = nd.zeros(n, dtype='int32')
+
+ kk = nd.floor(nd.random.uniform(0, self.K, shape=n), dtype='int32')
+ rand = nd.random.uniform(shape=n)
+
+ prob = self.prob[kk]
+ alias = self.alias[kk]
+
+ for i in xrange(n):
+ if rand[i] < prob[i]:
+ samples[i] = kk[i]
+ else:
+ samples[i] = alias[i]
+ return samples
+
diff --git a/python/mxnet/gluon/loss.py b/python/mxnet/gluon/loss.py
index 614025cd35e..c9413f369bd 100644
--- a/python/mxnet/gluon/loss.py
+++ b/python/mxnet/gluon/loss.py
@@ -28,6 +28,7 @@
from .. import ndarray
from ..base import numeric_types
from .block import HybridBlock
+from .data import AliasMethodSampler
def _apply_weighting(F, loss, weight=None, sample_weight=None):
"""Apply weighting to loss.
@@ -696,3 +697,85 @@ def hybrid_forward(self, F, pred, positive, negative):
axis=self._batch_axis, exclude=True)
loss = F.relu(loss + self._margin)
return _apply_weighting(F, loss, self._weight, None)
+
+
+class NoiseContrastiveEstimationLoss(Loss):
+ r"""Calculates the noise contrastive estimation loss:
+
+ The central idea of NCE is to perform a nonlinear logistic regression to
+ discriminate between the observed data and some artificially generated
+ noise data. So basically it based on one positive and
+
+ .. math::
+
+ pred = class_embedding * activation
+
+ prob = \frac{1}{1 + \exp(-{pred})}
+
+ L = - \sum_i {label}_i * \log({prob}_i) +
+ (1 - {label}_i) * \log(1 - {prob}_i)
+
+ where `pred` is a scalar result from inner product of `class_embedding` vector
+ and an `activation` vector, they have the same dimension. For positive class,
+ `label` is 1, for sampled negative classes, their label are 0.
+
+ Parameters
+ ----------
+ num_sampled : int
+ Number of sampled noise targets for NCE calculation.
+ num_classes : int
+ Number of classes.
+ noise_distribution : list of float or NDArray
+ Distribution of corresponding classes, for generating noisy targets.
+
+
+ Inputs:
+ - **weight**: The class embeddings. Type: Embedding, Shape (num_classes, dim).
+ - **inputs**: Forward activation tensor of the network. Shape (batch_size, dim).
+ - **targets**: truth tensor. Shape (batch_size, ).
+
+ Outputs:
+ - **loss**: loss tensor with shape (batch_size,). Dimenions other than
+ batch_axis are averaged out.
+
+ References
+ ----------
+ `Noise-contrastive estimation: A new estimation principle for
+ unnormalized statistical models
+ <proceedings.mlr.press/v9/gutmann10a/gutmann10a.pdf>`_
+
+ """
+
+ def __init__(self, num_sampled, num_classes, noise_distribution, **kwargs):
+ super(NoiseContrastiveEstimationLoss, self).__init__(num_sampled, num_classes, **kwargs)
+ self.sigmoid_binary_ce_loss = SigmoidBinaryCrossEntropyLoss(**kwargs)
+ self.alias_method_sampler = AliasMethodSampler(num_classes, noise_distribution)
+ self._num_sampled = num_sampled
+
+ def hybrid_forward(self, F, weights, inputs, targets, **kwargs):
+ preds, labels = self._compute_sampled_values(F, weights, inputs, targets)
+ return self.sigmoid_binary_ce_loss(preds, labels, **kwargs)
+
+ def _compute_sampled_values(self, F, weights, inputs, targets):
+ """Sample negative targets and compute activations"""
+ # (batch_size, dim)
+ targets_embedding = weights(targets)
+ targets_pred = F.broadcast_mul(targets_embedding, inputs)
+ targets_pred = F.sum(data=targets_pred, axis=1)
+
+ # Sample the negative labels.
+ batch_size = inputs.shape[0]
+ sampled_negatives = self.alias_method_sampler.draw(batch_size * self._num_sampled)
+
+ # shape:[batch_size, num_sampeld]
+ negatives_embedding = weights(sampled_negatives)
+ negatives_embedding = F.reshape(negatives_embedding, (batch_size, self._num_sampled, -1))
+ _inputs = F.reshape(inputs, (batch_size, 1, -1))
+ negatives_pred = F.broadcast_mul(_inputs, negatives_embedding) # shape:(batch_size, num_sampled, embed_size)
+ negatives_pred = F.sum(negatives_pred, axis=2)
+ negatives_pred = F.reshape(negatives_pred, (-1, ))
+
+ preds = F.concat(targets_pred, negatives_pred, dim=0)
+ labels = F.concat(F.ones_like(targets_pred), F.zeros_like(negatives_pred), dim=0)
+
+ return preds, labels
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services