[GitHub] zihaolucky commented on a change in pull request #9195: [WIP]NCE loss gluon
zihaolucky commented on a change in pull request #9195: [WIP]NCE loss gluon URL: https://github.com/apache/incubator-mxnet/pull/9195#discussion_r166171054 ## File path: python/mxnet/gluon/data/sampler.py ## @@ -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): Review comment: @piiswrong As the `NoiseContrastiveEstimationLoss` use it, where should I put the code? 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: us...@infra.apache.org With regards, Apache Git Services
[GitHub] zihaolucky commented on a change in pull request #9195: [WIP]NCE loss gluon
zihaolucky commented on a change in pull request #9195: [WIP]NCE loss gluon
URL: https://github.com/apache/incubator-mxnet/pull/9195#discussion_r161791018
##
File path: python/mxnet/gluon/loss.py
##
@@ -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
+`_
+
+"""
+
+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)
Review comment:
@szha I failed to figure out a way to prettify the `axis` and `dim`,
although we have `batch_axis`. Any idea?
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:
us...@infra.apache.org
With regards,
Apache Git Services
[GitHub] zihaolucky commented on a change in pull request #9195: [WIP]NCE loss gluon
zihaolucky commented on a change in pull request #9195: [WIP]NCE loss gluon
URL: https://github.com/apache/incubator-mxnet/pull/9195#discussion_r161791018
##
File path: python/mxnet/gluon/loss.py
##
@@ -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
+`_
+
+"""
+
+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)
Review comment:
I failed to figure out a way to prettify the `axis` and `dim`, although we
have `batch_axis`. @szha
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:
us...@infra.apache.org
With regards,
Apache Git Services
[GitHub] zihaolucky commented on a change in pull request #9195: [WIP]NCE loss gluon
zihaolucky commented on a change in pull request #9195: [WIP]NCE loss gluon
URL: https://github.com/apache/incubator-mxnet/pull/9195#discussion_r161788287
##
File path: python/mxnet/gluon/data/sampler.py
##
@@ -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:
Review comment:
@eric-haibin-lin The test code `speed` in my server, the Numpy is 100x
faster than NDArray.
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:
us...@infra.apache.org
With regards,
Apache Git Services
[GitHub] zihaolucky commented on a change in pull request #9195: [WIP]NCE loss gluon
zihaolucky commented on a change in pull request #9195: [WIP]NCE loss gluon
URL: https://github.com/apache/incubator-mxnet/pull/9195#discussion_r161788287
##
File path: python/mxnet/gluon/data/sampler.py
##
@@ -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:
Review comment:
@eric-haibin-lin I ran the test code `speed` on my server, the Numpy is 100x
faster than NDArray.
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:
us...@infra.apache.org
With regards,
Apache Git Services
[GitHub] zihaolucky commented on a change in pull request #9195: [WIP]NCE loss gluon
zihaolucky commented on a change in pull request #9195: [WIP]NCE loss gluon URL: https://github.com/apache/incubator-mxnet/pull/9195#discussion_r158801163 ## File path: example/gluon/sampler/alias_method.py ## @@ -0,0 +1,46 @@ +# 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 numpy as np +import numpy.random as npr +from collections import Counter + +import mxnet.gluon as gluon + +K = 5 +N = 1000 + +# Get a random probability vector. +probs = npr.dirichlet(np.ones(K), 1).ravel() + +# Construct the table. +alias_method_sampler = gluon.data.AliasMethodSampler(K, probs) + +# Generate variates. +X = alias_method_sampler.draw(N).asnumpy() +c = Counter(X) + +# check sampled probabilities +sampled_probs = [float(x)/N for x in c.values()] Review comment: @sxjscience Good idea. 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: us...@infra.apache.org With regards, Apache Git Services
[GitHub] zihaolucky commented on a change in pull request #9195: [WIP]NCE loss gluon
zihaolucky commented on a change in pull request #9195: [WIP]NCE loss gluon
URL: https://github.com/apache/incubator-mxnet/pull/9195#discussion_r158791226
##
File path: python/mxnet/gluon/data/sampler.py
##
@@ -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:
Review comment:
I would compare the speed later and report here.
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:
us...@infra.apache.org
With regards,
Apache Git Services
[GitHub] zihaolucky commented on a change in pull request #9195: [WIP]NCE loss gluon
zihaolucky commented on a change in pull request #9195: [WIP]NCE loss gluon
URL: https://github.com/apache/incubator-mxnet/pull/9195#discussion_r158790932
##
File path: python/mxnet/gluon/data/sampler.py
##
@@ -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:
Review comment:
#9209 FYI, a relevant issue here.
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:
us...@infra.apache.org
With regards,
Apache Git Services
[GitHub] zihaolucky commented on a change in pull request #9195: [WIP]NCE loss gluon
zihaolucky commented on a change in pull request #9195: [WIP]NCE loss gluon URL: https://github.com/apache/incubator-mxnet/pull/9195#discussion_r158759782 ## File path: python/mxnet/gluon/data/sampler.py ## @@ -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/ +""" Review comment: Great. I'll try to do this once we finish this PR. 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: us...@infra.apache.org With regards, Apache Git Services
[GitHub] zihaolucky commented on a change in pull request #9195: [WIP]NCE loss gluon
zihaolucky commented on a change in pull request #9195: [WIP]NCE loss gluon
URL: https://github.com/apache/incubator-mxnet/pull/9195#discussion_r158759746
##
File path: python/mxnet/gluon/data/sampler.py
##
@@ -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):
Review comment:
Thanks, I would change it later.
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:
us...@infra.apache.org
With regards,
Apache Git Services
