We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
NegativeSampling and WalkerAlias do not implement to_cpu()
`NegativeSampling` implements only `to_gpu()`. Therefore, `self.sampler` does not come back to the CPU side even if `to_cpu()` is called. `WalkerAlias` also does not have `to_cpu()`.

Currently this causes a problem with [word2vec example](https://github.com/pfnet/chainer/pull/270) when loading a GPU-trained model based on negative sampling, which [has been transferred](https://github.com/pfnet/chainer/blob/0bab97c584d462e4478f360c26ce427bfe81eb0f/examples/word2vec/train_word2vec.py#L183) by `model.to_cpu()` before save by pickle.


--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `chainer/functions/negative_sampling.py`
Content:
```
1 import numpy
2 import six
3 
4 from chainer import cuda
5 from chainer import function
6 from chainer.utils import type_check
7 from chainer.utils import walker_alias
8 
9 
10 class NegativeSampling(function.Function):
11     """Implementation of negative sampling.
12 
13     In natural language processing, especially language modeling, the number of
14     vocabulary is very large.
15     Therefore, you need to spend a lot of time to calculate the gradient of the
16     embedding matrix.
17 
18     Instead, in negative sampling trick, you only need to calculate the
19     gradient for a few sampled negative examples.
20 
21     The objective function is below:
22 
23     .. math::
24 
25        f(x, p) = \log\sigma(x^\\top w_p) + \\
26        k E_{i \sim P(i)}[\log\sigma(- x^\\top w_i)],
27 
28     where :math:`\sigma(\cdot)` is a sigmoid function, :math:`w_i` is the
29     weight vector for the word :math:`i`, and :math:`p` is a positive example.
30     It is approximeted with :math:`k` examples :math:`N` sampled from
31     probability :math:`P(i)`, like this:
32 
33     .. math::
34 
35        f(x, p) \\approx \log\sigma(x^\\top w_p) + \\
36        \sum_{n \in N} \log\sigma(-x^\\top w_n).
37 
38     Each sample of :math:`N` is drawn from the word distribution :math:`P(w)`.
39     This is calculated as :math:`P(w) = \\frac{1}{Z} c(w)^\\alpha`, where
40     :math:`c(w)` is the unigram count of the word :math:`w`, :math:`\\alpha` is
41     a hyper-parameter, and :math:`Z` is the normalization constant.
42 
43     Args:
44         in_size (int): Dimension of input vectors.
45         counts (int list): Number of each identifiers.
46         sample_size (int): Number of negative samples.
47         power (float): Power factor :math:`\\alpha`.
48 
49     See: `Distributed Representations of Words and Phrases and their\
50          Compositionality <http://arxiv.org/abs/1310.4546>`_
51     """
52 
53     parameter_names = ('W',)
54     gradient_names = ('gW',)
55 
56     def __init__(self, in_size, counts, sample_size, power=0.75):
57         self.sample_size = sample_size
58         p = numpy.array(counts, numpy.float32)
59         p = numpy.power(p, power)
60         self.sampler = walker_alias.WalkerAlias(p)
61 
62         vocab_size = len(counts)
63         self.W = numpy.zeros((vocab_size, in_size)).astype(numpy.float32)
64         self.gW = numpy.zeros_like(self.W)
65 
66     def _make_samples(self, t):
67         if hasattr(self, 'samples'):
68             return self.samples
69 
70         size = int(t.shape[0])
71         # first one is the positive, and others are sampled negatives
72         samples = self.sampler.sample((size, self.sample_size + 1))
73         if isinstance(samples, numpy.ndarray):
74             samples.T[0] = t
75         else:
76             cuda.elementwise(
77                 'const int* t, int* s, int m',
78                 ''' s[i * m] = t[i]; ''',
79                 'negative_sampling_assign'
80             )(t, samples, self.sample_size + 1)
81 
82         self.samples = samples
83 
84     def check_type_forward(self, in_types):
85         type_check.expect(in_types.size() == 2)
86         x_type, t_type = in_types
87 
88         type_check.expect(
89             x_type.dtype == numpy.float32,
90             x_type.ndim == 2,
91             t_type.dtype == numpy.int32,
92             t_type.ndim == 1,
93             x_type.shape[0] == t_type.shape[0]
94         )
95 
96     def check_type_backward(self, in_types, out_types):
97         type_check.expect(
98             out_types.size() == 1,
99             out_types[0].dtype == numpy.float32,
100             out_types[0].ndim == 0
101         )
102 
103     def to_gpu(self, device=None):
104         function.Function.to_gpu(self, device)
105         self.sampler.to_gpu()
106 
107     def forward_cpu(self, inputs):
108         x, t = inputs
109         self._make_samples(t)
110 
111         loss = numpy.float32(0.0)
112         for i, (ix, k) in enumerate(six.moves.zip(x, self.samples)):
113             w = self.W[k]
114             f = w.dot(ix)
115             f[0] *= -1  # positive sample
116             loss += numpy.sum(numpy.logaddexp(f, 0))
117         return numpy.array(loss, numpy.float32),
118 
119     def forward_gpu(self, inputs):
120         x, t = inputs
121         n_in = x.shape[1]
122         self._make_samples(t)
123 
124         wx = cuda.empty((x.shape[0], self.sample_size + 1))
125         cuda.elementwise(
126             '''float* wx, const float* W, const float* x, const int* k, int c,
127             int m''',
128             '''
129             x = &x[(i / m) * c];
130             W = &W[k[i] * c];
131             float f = 0;
132             for (int j = 0; j < c; ++j) {
133               f += x[j] * W[j];
134             }
135             wx[i] = f;
136             ''',
137             'negative_sampling_wx'
138         )(wx, self.W, x, self.samples, n_in, self.sample_size + 1)
139         self.wx = wx
140 
141         y = cuda.zeros_like(wx)
142         cuda.elementwise(
143             'float* y, const float* wx, int c, int m',
144             '''
145             float f = wx[i];
146             if (i % m == 0) {
147               f = -f;
148             }
149             float loss;
150             if (f < 0) {
151               loss = __logf(1 + __expf(f));
152             } else {
153               loss = f + __logf(1 + __expf(-f));
154             }
155             y[i] = loss;
156             ''',
157             'negative_sampling_forward'
158         )(y, wx, n_in, self.sample_size + 1)
159         loss = cuda.gpuarray.sum(y)
160         return loss,
161 
162     def backward_cpu(self, inputs, grads):
163         x, t = inputs
164         gloss, = grads
165 
166         gx = numpy.zeros_like(x)
167 
168         for i, (ix, k) in enumerate(six.moves.zip(x, self.samples)):
169             w = self.W[k]
170             f = w.dot(ix)
171 
172             # g == -y * gloss / (1 + exp(yf))
173             f[0] *= -1
174             g = gloss / (1 + numpy.exp(-f))
175             g[0] *= -1
176 
177             gx[i] = g.dot(w)
178             for ik, ig in six.moves.zip(k, g):
179                 self.gW[ik] += ig * ix
180         return gx, None
181 
182     def backward_gpu(self, inputs, grads):
183         x, t = inputs
184         gloss, = grads
185 
186         n_in = x.shape[1]
187         g = cuda.empty_like(self.wx)
188         cuda.elementwise(
189             'float* g, const float* wx, const float* gloss, int m',
190             '''
191             float y;
192             if (i % m == 0) {
193               y = 1;
194             } else {
195               y = -1;
196             }
197 
198             g[i] = -y * *gloss / (1.0f + __expf(wx[i] * y));
199             ''',
200             'negative_sampling_calculate_g'
201         )(g, self.wx, gloss, self.sample_size + 1)
202         gx = cuda.zeros_like(x)
203         cuda.elementwise(
204             '''float* gx, const float* g, const float* W, const int* k, int c,
205             int m''',
206             '''
207             int d = i / c;
208             g = &g[d * m];
209             k = &k[d * m];
210             float w = 0;
211             for (int j = 0; j < m; ++j) {
212               w += g[j] * W[k[j] * c + i % c];
213             }
214             gx[i] = w;
215             ''',
216             'negative_sampling_calculate_gx'
217         )(gx, g, self.W, self.samples, n_in, self.sample_size + 1)
218         cuda.elementwise(
219             '''const float * g, const float* x, const int* k, float* gW, int c,
220             int m''',
221             '''
222             x = &x[(i / m) * c];
223             gW = &gW[k[i] * c];
224             float gi = g[i];
225             for (int j = 0; j < c; ++j) {
226               atomicAdd(gW + j, gi * x[j]);
227             }
228             ''',
229             'negative_sampling_calculate_gw'
230         )(g, x, self.samples, self.gW, n_in, self.sample_size + 1)
231         return gx, None
232
```

Path: `chainer/utils/walker_alias.py`
Content:
```
1 import numpy
2 
3 from chainer import cuda
4 
5 
6 class WalkerAlias(object):
7     """Implementation of Walker's alias method.
8 
9     This method generates a random sample from given probabilities
10     :math:`p_1, \dots, p_n` in :math:`O(1)` time.
11     It is more efficient than :func:`~numpy.random.choice`.
12     This class has sampling methods in CPU and in GPU.
13 
14     Args:
15         probs (float list): Probabilities of entries. They are normalized with
16                             `sum(probs)`.
17 
18     See: `Wikipedia article <https://en.wikipedia.org/wiki/Alias_method>`_
19 
20     """
21 
22     def __init__(self, probs):
23         prob = numpy.array(probs, numpy.float32)
24         prob /= numpy.sum(prob)
25         threshold = numpy.ndarray(len(probs), numpy.float32)
26         values = numpy.ndarray(len(probs) * 2, numpy.int32)
27         il, ir = 0, 0
28         pairs = list(zip(prob, range(len(probs))))
29         pairs.sort()
30         for prob, i in pairs:
31             p = prob * len(probs)
32             while p > 1 and ir < len(threshold):
33                 values[ir * 2 + 1] = i
34                 p -= 1.0 - threshold[ir]
35                 ir += 1
36             threshold[il] = p
37             values[il * 2] = i
38             il += 1
39         # fill the rest
40         for i in range(ir, len(probs)):
41             values[i * 2 + 1] = 0
42 
43         assert((values < len(threshold)).all())
44         self.threshold = threshold
45         self.values = values
46         self.use_gpu = False
47 
48     def to_gpu(self):
49         """Make a sampler GPU mode.
50 
51         """
52         if not self.use_gpu:
53             self.threshold = cuda.to_gpu(self.threshold)
54             self.values = cuda.to_gpu(self.values)
55             self.use_gpu = True
56 
57     def sample(self, shape):
58         """Generates a random sample based on given probabilities.
59 
60         Args:
61             shape (tuple of int): Shape of a return value.
62 
63         Returns:
64             Returns a generated array with the given shape. If a sampler is in
65             CPU mode the return value is :class:`~numpy.ndarray`, and if it is
66             in GPU mode the return value is :class:`~pycuda.gpuarray.GPUArray`.
67         """
68         if self.use_gpu:
69             return self.sample_gpu(shape)
70         else:
71             return self.sample_cpu(shape)
72 
73     def sample_cpu(self, shape):
74         ps = numpy.random.uniform(0, 1, shape)
75         pb = ps * len(self.threshold)
76         index = pb.astype(numpy.int32)
77         left_right = (self.threshold[index] < pb - index).astype(numpy.int32)
78         return self.values[index * 2 + left_right]
79 
80     def sample_gpu(self, shape):
81         ps = cuda.empty(shape, numpy.float32)
82         cuda.get_generator().fill_uniform(ps)
83         vs = cuda.empty(shape, numpy.int32)
84         cuda.elementwise(
85             '''int* vs, const float* ps, const float* threshold,
86             const int* values, int b''',
87             '''
88             float pb = ps[i] * b;
89             int index = __float2int_rd(pb);
90             // fill_uniform sometimes returns 1.0, so we need to check index
91             if (index >= b) {
92               index = 0;
93             }
94             int lr = threshold[index] < pb - index;
95             vs[i] = values[index * 2 + lr];
96             ''',
97             'walker_alias_sample'
98         )(vs, ps, self.threshold, self.values, len(self.threshold))
99         return vs
100
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/chainer/functions/negative_sampling.py b/chainer/functions/negative_sampling.py
--- a/chainer/functions/negative_sampling.py
+++ b/chainer/functions/negative_sampling.py
@@ -104,6 +104,10 @@
         function.Function.to_gpu(self, device)
         self.sampler.to_gpu()
 
+    def to_cpu(self):
+        function.Function.to_cpu(self)
+        self.sampler.to_cpu()
+
     def forward_cpu(self, inputs):
         x, t = inputs
         self._make_samples(t)
diff --git a/chainer/utils/walker_alias.py b/chainer/utils/walker_alias.py
--- a/chainer/utils/walker_alias.py
+++ b/chainer/utils/walker_alias.py
@@ -54,6 +54,15 @@
             self.values = cuda.to_gpu(self.values)
             self.use_gpu = True
 
+    def to_cpu(self):
+        """Make a sampler CPU mode.
+
+        """
+        if self.use_gpu:
+            self.threshold = cuda.to_cpu(self.threshold)
+            self.values = cuda.to_cpu(self.values)
+            self.use_gpu = False
+
     def sample(self, shape):
         """Generates a random sample based on given probabilities.

{"golden_diff": "diff --git a/chainer/functions/negative_sampling.py b/chainer/functions/negative_sampling.py\n--- a/chainer/functions/negative_sampling.py\n+++ b/chainer/functions/negative_sampling.py\n@@ -104,6 +104,10 @@\n         function.Function.to_gpu(self, device)\n         self.sampler.to_gpu()\n \n+    def to_cpu(self):\n+        function.Function.to_cpu(self)\n+        self.sampler.to_cpu()\n+\n     def forward_cpu(self, inputs):\n         x, t = inputs\n         self._make_samples(t)\ndiff --git a/chainer/utils/walker_alias.py b/chainer/utils/walker_alias.py\n--- a/chainer/utils/walker_alias.py\n+++ b/chainer/utils/walker_alias.py\n@@ -54,6 +54,15 @@\n             self.values = cuda.to_gpu(self.values)\n             self.use_gpu = True\n \n+    def to_cpu(self):\n+        \"\"\"Make a sampler CPU mode.\n+\n+        \"\"\"\n+        if self.use_gpu:\n+            self.threshold = cuda.to_cpu(self.threshold)\n+            self.values = cuda.to_cpu(self.values)\n+            self.use_gpu = False\n+\n     def sample(self, shape):\n         \"\"\"Generates a random sample based on given probabilities.\n", "issue": "NegativeSampling and WalkerAlias do not implement to_cpu()\n`NegativeSampling` implements only `to_gpu()`. Therefore, `self.sampler` does not come back to the CPU side even if `to_cpu()` is called. `WalkerAlias` also does not have `to_cpu()`.\n\nCurrently this causes a problem with [word2vec example](https://github.com/pfnet/chainer/pull/270) when loading a GPU-trained model based on negative sampling, which [has been transferred](https://github.com/pfnet/chainer/blob/0bab97c584d462e4478f360c26ce427bfe81eb0f/examples/word2vec/train_word2vec.py#L183) by `model.to_cpu()` before save by pickle.\n\n", "before_files": [{"content": "import numpy\nimport six\n\nfrom chainer import cuda\nfrom chainer import function\nfrom chainer.utils import type_check\nfrom chainer.utils import walker_alias\n\n\nclass NegativeSampling(function.Function):\n    \"\"\"Implementation of negative sampling.\n\n    In natural language processing, especially language modeling, the number of\n    vocabulary is very large.\n    Therefore, you need to spend a lot of time to calculate the gradient of the\n    embedding matrix.\n\n    Instead, in negative sampling trick, you only need to calculate the\n    gradient for a few sampled negative examples.\n\n    The objective function is below:\n\n    .. math::\n\n       f(x, p) = \\log\\sigma(x^\\\\top w_p) + \\\\\n       k E_{i \\sim P(i)}[\\log\\sigma(- x^\\\\top w_i)],\n\n    where :math:`\\sigma(\\cdot)` is a sigmoid function, :math:`w_i` is the\n    weight vector for the word :math:`i`, and :math:`p` is a positive example.\n    It is approximeted with :math:`k` examples :math:`N` sampled from\n    probability :math:`P(i)`, like this:\n\n    .. math::\n\n       f(x, p) \\\\approx \\log\\sigma(x^\\\\top w_p) + \\\\\n       \\sum_{n \\in N} \\log\\sigma(-x^\\\\top w_n).\n\n    Each sample of :math:`N` is drawn from the word distribution :math:`P(w)`.\n    This is calculated as :math:`P(w) = \\\\frac{1}{Z} c(w)^\\\\alpha`, where\n    :math:`c(w)` is the unigram count of the word :math:`w`, :math:`\\\\alpha` is\n    a hyper-parameter, and :math:`Z` is the normalization constant.\n\n    Args:\n        in_size (int): Dimension of input vectors.\n        counts (int list): Number of each identifiers.\n        sample_size (int): Number of negative samples.\n        power (float): Power factor :math:`\\\\alpha`.\n\n    See: `Distributed Representations of Words and Phrases and their\\\n         Compositionality <http://arxiv.org/abs/1310.4546>`_\n    \"\"\"\n\n    parameter_names = ('W',)\n    gradient_names = ('gW',)\n\n    def __init__(self, in_size, counts, sample_size, power=0.75):\n        self.sample_size = sample_size\n        p = numpy.array(counts, numpy.float32)\n        p = numpy.power(p, power)\n        self.sampler = walker_alias.WalkerAlias(p)\n\n        vocab_size = len(counts)\n        self.W = numpy.zeros((vocab_size, in_size)).astype(numpy.float32)\n        self.gW = numpy.zeros_like(self.W)\n\n    def _make_samples(self, t):\n        if hasattr(self, 'samples'):\n            return self.samples\n\n        size = int(t.shape[0])\n        # first one is the positive, and others are sampled negatives\n        samples = self.sampler.sample((size, self.sample_size + 1))\n        if isinstance(samples, numpy.ndarray):\n            samples.T[0] = t\n        else:\n            cuda.elementwise(\n                'const int* t, int* s, int m',\n                ''' s[i * m] = t[i]; ''',\n                'negative_sampling_assign'\n            )(t, samples, self.sample_size + 1)\n\n        self.samples = samples\n\n    def check_type_forward(self, in_types):\n        type_check.expect(in_types.size() == 2)\n        x_type, t_type = in_types\n\n        type_check.expect(\n            x_type.dtype == numpy.float32,\n            x_type.ndim == 2,\n            t_type.dtype == numpy.int32,\n            t_type.ndim == 1,\n            x_type.shape[0] == t_type.shape[0]\n        )\n\n    def check_type_backward(self, in_types, out_types):\n        type_check.expect(\n            out_types.size() == 1,\n            out_types[0].dtype == numpy.float32,\n            out_types[0].ndim == 0\n        )\n\n    def to_gpu(self, device=None):\n        function.Function.to_gpu(self, device)\n        self.sampler.to_gpu()\n\n    def forward_cpu(self, inputs):\n        x, t = inputs\n        self._make_samples(t)\n\n        loss = numpy.float32(0.0)\n        for i, (ix, k) in enumerate(six.moves.zip(x, self.samples)):\n            w = self.W[k]\n            f = w.dot(ix)\n            f[0] *= -1  # positive sample\n            loss += numpy.sum(numpy.logaddexp(f, 0))\n        return numpy.array(loss, numpy.float32),\n\n    def forward_gpu(self, inputs):\n        x, t = inputs\n        n_in = x.shape[1]\n        self._make_samples(t)\n\n        wx = cuda.empty((x.shape[0], self.sample_size + 1))\n        cuda.elementwise(\n            '''float* wx, const float* W, const float* x, const int* k, int c,\n            int m''',\n            '''\n            x = &x[(i / m) * c];\n            W = &W[k[i] * c];\n            float f = 0;\n            for (int j = 0; j < c; ++j) {\n              f += x[j] * W[j];\n            }\n            wx[i] = f;\n            ''',\n            'negative_sampling_wx'\n        )(wx, self.W, x, self.samples, n_in, self.sample_size + 1)\n        self.wx = wx\n\n        y = cuda.zeros_like(wx)\n        cuda.elementwise(\n            'float* y, const float* wx, int c, int m',\n            '''\n            float f = wx[i];\n            if (i % m == 0) {\n              f = -f;\n            }\n            float loss;\n            if (f < 0) {\n              loss = __logf(1 + __expf(f));\n            } else {\n              loss = f + __logf(1 + __expf(-f));\n            }\n            y[i] = loss;\n            ''',\n            'negative_sampling_forward'\n        )(y, wx, n_in, self.sample_size + 1)\n        loss = cuda.gpuarray.sum(y)\n        return loss,\n\n    def backward_cpu(self, inputs, grads):\n        x, t = inputs\n        gloss, = grads\n\n        gx = numpy.zeros_like(x)\n\n        for i, (ix, k) in enumerate(six.moves.zip(x, self.samples)):\n            w = self.W[k]\n            f = w.dot(ix)\n\n            # g == -y * gloss / (1 + exp(yf))\n            f[0] *= -1\n            g = gloss / (1 + numpy.exp(-f))\n            g[0] *= -1\n\n            gx[i] = g.dot(w)\n            for ik, ig in six.moves.zip(k, g):\n                self.gW[ik] += ig * ix\n        return gx, None\n\n    def backward_gpu(self, inputs, grads):\n        x, t = inputs\n        gloss, = grads\n\n        n_in = x.shape[1]\n        g = cuda.empty_like(self.wx)\n        cuda.elementwise(\n            'float* g, const float* wx, const float* gloss, int m',\n            '''\n            float y;\n            if (i % m == 0) {\n              y = 1;\n            } else {\n              y = -1;\n            }\n\n            g[i] = -y * *gloss / (1.0f + __expf(wx[i] * y));\n            ''',\n            'negative_sampling_calculate_g'\n        )(g, self.wx, gloss, self.sample_size + 1)\n        gx = cuda.zeros_like(x)\n        cuda.elementwise(\n            '''float* gx, const float* g, const float* W, const int* k, int c,\n            int m''',\n            '''\n            int d = i / c;\n            g = &g[d * m];\n            k = &k[d * m];\n            float w = 0;\n            for (int j = 0; j < m; ++j) {\n              w += g[j] * W[k[j] * c + i % c];\n            }\n            gx[i] = w;\n            ''',\n            'negative_sampling_calculate_gx'\n        )(gx, g, self.W, self.samples, n_in, self.sample_size + 1)\n        cuda.elementwise(\n            '''const float * g, const float* x, const int* k, float* gW, int c,\n            int m''',\n            '''\n            x = &x[(i / m) * c];\n            gW = &gW[k[i] * c];\n            float gi = g[i];\n            for (int j = 0; j < c; ++j) {\n              atomicAdd(gW + j, gi * x[j]);\n            }\n            ''',\n            'negative_sampling_calculate_gw'\n        )(g, x, self.samples, self.gW, n_in, self.sample_size + 1)\n        return gx, None\n", "path": "chainer/functions/negative_sampling.py"}, {"content": "import numpy\n\nfrom chainer import cuda\n\n\nclass WalkerAlias(object):\n    \"\"\"Implementation of Walker's alias method.\n\n    This method generates a random sample from given probabilities\n    :math:`p_1, \\dots, p_n` in :math:`O(1)` time.\n    It is more efficient than :func:`~numpy.random.choice`.\n    This class has sampling methods in CPU and in GPU.\n\n    Args:\n        probs (float list): Probabilities of entries. They are normalized with\n                            `sum(probs)`.\n\n    See: `Wikipedia article <https://en.wikipedia.org/wiki/Alias_method>`_\n\n    \"\"\"\n\n    def __init__(self, probs):\n        prob = numpy.array(probs, numpy.float32)\n        prob /= numpy.sum(prob)\n        threshold = numpy.ndarray(len(probs), numpy.float32)\n        values = numpy.ndarray(len(probs) * 2, numpy.int32)\n        il, ir = 0, 0\n        pairs = list(zip(prob, range(len(probs))))\n        pairs.sort()\n        for prob, i in pairs:\n            p = prob * len(probs)\n            while p > 1 and ir < len(threshold):\n                values[ir * 2 + 1] = i\n                p -= 1.0 - threshold[ir]\n                ir += 1\n            threshold[il] = p\n            values[il * 2] = i\n            il += 1\n        # fill the rest\n        for i in range(ir, len(probs)):\n            values[i * 2 + 1] = 0\n\n        assert((values < len(threshold)).all())\n        self.threshold = threshold\n        self.values = values\n        self.use_gpu = False\n\n    def to_gpu(self):\n        \"\"\"Make a sampler GPU mode.\n\n        \"\"\"\n        if not self.use_gpu:\n            self.threshold = cuda.to_gpu(self.threshold)\n            self.values = cuda.to_gpu(self.values)\n            self.use_gpu = True\n\n    def sample(self, shape):\n        \"\"\"Generates a random sample based on given probabilities.\n\n        Args:\n            shape (tuple of int): Shape of a return value.\n\n        Returns:\n            Returns a generated array with the given shape. If a sampler is in\n            CPU mode the return value is :class:`~numpy.ndarray`, and if it is\n            in GPU mode the return value is :class:`~pycuda.gpuarray.GPUArray`.\n        \"\"\"\n        if self.use_gpu:\n            return self.sample_gpu(shape)\n        else:\n            return self.sample_cpu(shape)\n\n    def sample_cpu(self, shape):\n        ps = numpy.random.uniform(0, 1, shape)\n        pb = ps * len(self.threshold)\n        index = pb.astype(numpy.int32)\n        left_right = (self.threshold[index] < pb - index).astype(numpy.int32)\n        return self.values[index * 2 + left_right]\n\n    def sample_gpu(self, shape):\n        ps = cuda.empty(shape, numpy.float32)\n        cuda.get_generator().fill_uniform(ps)\n        vs = cuda.empty(shape, numpy.int32)\n        cuda.elementwise(\n            '''int* vs, const float* ps, const float* threshold,\n            const int* values, int b''',\n            '''\n            float pb = ps[i] * b;\n            int index = __float2int_rd(pb);\n            // fill_uniform sometimes returns 1.0, so we need to check index\n            if (index >= b) {\n              index = 0;\n            }\n            int lr = threshold[index] < pb - index;\n            vs[i] = values[index * 2 + lr];\n            ''',\n            'walker_alias_sample'\n        )(vs, ps, self.threshold, self.values, len(self.threshold))\n        return vs\n", "path": "chainer/utils/walker_alias.py"}], "after_files": [{"content": "import numpy\nimport six\n\nfrom chainer import cuda\nfrom chainer import function\nfrom chainer.utils import type_check\nfrom chainer.utils import walker_alias\n\n\nclass NegativeSampling(function.Function):\n    \"\"\"Implementation of negative sampling.\n\n    In natural language processing, especially language modeling, the number of\n    vocabulary is very large.\n    Therefore, you need to spend a lot of time to calculate the gradient of the\n    embedding matrix.\n\n    Instead, in negative sampling trick, you only need to calculate the\n    gradient for a few sampled negative examples.\n\n    The objective function is below:\n\n    .. math::\n\n       f(x, p) = \\log\\sigma(x^\\\\top w_p) + \\\\\n       k E_{i \\sim P(i)}[\\log\\sigma(- x^\\\\top w_i)],\n\n    where :math:`\\sigma(\\cdot)` is a sigmoid function, :math:`w_i` is the\n    weight vector for the word :math:`i`, and :math:`p` is a positive example.\n    It is approximeted with :math:`k` examples :math:`N` sampled from\n    probability :math:`P(i)`, like this:\n\n    .. math::\n\n       f(x, p) \\\\approx \\log\\sigma(x^\\\\top w_p) + \\\\\n       \\sum_{n \\in N} \\log\\sigma(-x^\\\\top w_n).\n\n    Each sample of :math:`N` is drawn from the word distribution :math:`P(w)`.\n    This is calculated as :math:`P(w) = \\\\frac{1}{Z} c(w)^\\\\alpha`, where\n    :math:`c(w)` is the unigram count of the word :math:`w`, :math:`\\\\alpha` is\n    a hyper-parameter, and :math:`Z` is the normalization constant.\n\n    Args:\n        in_size (int): Dimension of input vectors.\n        counts (int list): Number of each identifiers.\n        sample_size (int): Number of negative samples.\n        power (float): Power factor :math:`\\\\alpha`.\n\n    See: `Distributed Representations of Words and Phrases and their\\\n         Compositionality <http://arxiv.org/abs/1310.4546>`_\n    \"\"\"\n\n    parameter_names = ('W',)\n    gradient_names = ('gW',)\n\n    def __init__(self, in_size, counts, sample_size, power=0.75):\n        self.sample_size = sample_size\n        p = numpy.array(counts, numpy.float32)\n        p = numpy.power(p, power)\n        self.sampler = walker_alias.WalkerAlias(p)\n\n        vocab_size = len(counts)\n        self.W = numpy.zeros((vocab_size, in_size)).astype(numpy.float32)\n        self.gW = numpy.zeros_like(self.W)\n\n    def _make_samples(self, t):\n        if hasattr(self, 'samples'):\n            return self.samples\n\n        size = int(t.shape[0])\n        # first one is the positive, and others are sampled negatives\n        samples = self.sampler.sample((size, self.sample_size + 1))\n        if isinstance(samples, numpy.ndarray):\n            samples.T[0] = t\n        else:\n            cuda.elementwise(\n                'const int* t, int* s, int m',\n                ''' s[i * m] = t[i]; ''',\n                'negative_sampling_assign'\n            )(t, samples, self.sample_size + 1)\n\n        self.samples = samples\n\n    def check_type_forward(self, in_types):\n        type_check.expect(in_types.size() == 2)\n        x_type, t_type = in_types\n\n        type_check.expect(\n            x_type.dtype == numpy.float32,\n            x_type.ndim == 2,\n            t_type.dtype == numpy.int32,\n            t_type.ndim == 1,\n            x_type.shape[0] == t_type.shape[0]\n        )\n\n    def check_type_backward(self, in_types, out_types):\n        type_check.expect(\n            out_types.size() == 1,\n            out_types[0].dtype == numpy.float32,\n            out_types[0].ndim == 0\n        )\n\n    def to_gpu(self, device=None):\n        function.Function.to_gpu(self, device)\n        self.sampler.to_gpu()\n\n    def to_cpu(self):\n        function.Function.to_cpu(self)\n        self.sampler.to_cpu()\n\n    def forward_cpu(self, inputs):\n        x, t = inputs\n        self._make_samples(t)\n\n        loss = numpy.float32(0.0)\n        for i, (ix, k) in enumerate(six.moves.zip(x, self.samples)):\n            w = self.W[k]\n            f = w.dot(ix)\n            f[0] *= -1  # positive sample\n            loss += numpy.sum(numpy.logaddexp(f, 0))\n        return numpy.array(loss, numpy.float32),\n\n    def forward_gpu(self, inputs):\n        x, t = inputs\n        n_in = x.shape[1]\n        self._make_samples(t)\n\n        wx = cuda.empty((x.shape[0], self.sample_size + 1))\n        cuda.elementwise(\n            '''float* wx, const float* W, const float* x, const int* k, int c,\n            int m''',\n            '''\n            x = &x[(i / m) * c];\n            W = &W[k[i] * c];\n            float f = 0;\n            for (int j = 0; j < c; ++j) {\n              f += x[j] * W[j];\n            }\n            wx[i] = f;\n            ''',\n            'negative_sampling_wx'\n        )(wx, self.W, x, self.samples, n_in, self.sample_size + 1)\n        self.wx = wx\n\n        y = cuda.zeros_like(wx)\n        cuda.elementwise(\n            'float* y, const float* wx, int c, int m',\n            '''\n            float f = wx[i];\n            if (i % m == 0) {\n              f = -f;\n            }\n            float loss;\n            if (f < 0) {\n              loss = __logf(1 + __expf(f));\n            } else {\n              loss = f + __logf(1 + __expf(-f));\n            }\n            y[i] = loss;\n            ''',\n            'negative_sampling_forward'\n        )(y, wx, n_in, self.sample_size + 1)\n        loss = cuda.gpuarray.sum(y)\n        return loss,\n\n    def backward_cpu(self, inputs, grads):\n        x, t = inputs\n        gloss, = grads\n\n        gx = numpy.zeros_like(x)\n\n        for i, (ix, k) in enumerate(six.moves.zip(x, self.samples)):\n            w = self.W[k]\n            f = w.dot(ix)\n\n            # g == -y * gloss / (1 + exp(yf))\n            f[0] *= -1\n            g = gloss / (1 + numpy.exp(-f))\n            g[0] *= -1\n\n            gx[i] = g.dot(w)\n            for ik, ig in six.moves.zip(k, g):\n                self.gW[ik] += ig * ix\n        return gx, None\n\n    def backward_gpu(self, inputs, grads):\n        x, t = inputs\n        gloss, = grads\n\n        n_in = x.shape[1]\n        g = cuda.empty_like(self.wx)\n        cuda.elementwise(\n            'float* g, const float* wx, const float* gloss, int m',\n            '''\n            float y;\n            if (i % m == 0) {\n              y = 1;\n            } else {\n              y = -1;\n            }\n\n            g[i] = -y * *gloss / (1.0f + __expf(wx[i] * y));\n            ''',\n            'negative_sampling_calculate_g'\n        )(g, self.wx, gloss, self.sample_size + 1)\n        gx = cuda.zeros_like(x)\n        cuda.elementwise(\n            '''float* gx, const float* g, const float* W, const int* k, int c,\n            int m''',\n            '''\n            int d = i / c;\n            g = &g[d * m];\n            k = &k[d * m];\n            float w = 0;\n            for (int j = 0; j < m; ++j) {\n              w += g[j] * W[k[j] * c + i % c];\n            }\n            gx[i] = w;\n            ''',\n            'negative_sampling_calculate_gx'\n        )(gx, g, self.W, self.samples, n_in, self.sample_size + 1)\n        cuda.elementwise(\n            '''const float * g, const float* x, const int* k, float* gW, int c,\n            int m''',\n            '''\n            x = &x[(i / m) * c];\n            gW = &gW[k[i] * c];\n            float gi = g[i];\n            for (int j = 0; j < c; ++j) {\n              atomicAdd(gW + j, gi * x[j]);\n            }\n            ''',\n            'negative_sampling_calculate_gw'\n        )(g, x, self.samples, self.gW, n_in, self.sample_size + 1)\n        return gx, None\n", "path": "chainer/functions/negative_sampling.py"}, {"content": "import numpy\n\nfrom chainer import cuda\n\n\nclass WalkerAlias(object):\n    \"\"\"Implementation of Walker's alias method.\n\n    This method generates a random sample from given probabilities\n    :math:`p_1, \\dots, p_n` in :math:`O(1)` time.\n    It is more efficient than :func:`~numpy.random.choice`.\n    This class has sampling methods in CPU and in GPU.\n\n    Args:\n        probs (float list): Probabilities of entries. They are normalized with\n                            `sum(probs)`.\n\n    See: `Wikipedia article <https://en.wikipedia.org/wiki/Alias_method>`_\n\n    \"\"\"\n\n    def __init__(self, probs):\n        prob = numpy.array(probs, numpy.float32)\n        prob /= numpy.sum(prob)\n        threshold = numpy.ndarray(len(probs), numpy.float32)\n        values = numpy.ndarray(len(probs) * 2, numpy.int32)\n        il, ir = 0, 0\n        pairs = list(zip(prob, range(len(probs))))\n        pairs.sort()\n        for prob, i in pairs:\n            p = prob * len(probs)\n            while p > 1 and ir < len(threshold):\n                values[ir * 2 + 1] = i\n                p -= 1.0 - threshold[ir]\n                ir += 1\n            threshold[il] = p\n            values[il * 2] = i\n            il += 1\n        # fill the rest\n        for i in range(ir, len(probs)):\n            values[i * 2 + 1] = 0\n\n        assert((values < len(threshold)).all())\n        self.threshold = threshold\n        self.values = values\n        self.use_gpu = False\n\n    def to_gpu(self):\n        \"\"\"Make a sampler GPU mode.\n\n        \"\"\"\n        if not self.use_gpu:\n            self.threshold = cuda.to_gpu(self.threshold)\n            self.values = cuda.to_gpu(self.values)\n            self.use_gpu = True\n\n    def to_cpu(self):\n        \"\"\"Make a sampler CPU mode.\n\n        \"\"\"\n        if self.use_gpu:\n            self.threshold = cuda.to_cpu(self.threshold)\n            self.values = cuda.to_cpu(self.values)\n            self.use_gpu = False\n\n    def sample(self, shape):\n        \"\"\"Generates a random sample based on given probabilities.\n\n        Args:\n            shape (tuple of int): Shape of a return value.\n\n        Returns:\n            Returns a generated array with the given shape. If a sampler is in\n            CPU mode the return value is :class:`~numpy.ndarray`, and if it is\n            in GPU mode the return value is :class:`~pycuda.gpuarray.GPUArray`.\n        \"\"\"\n        if self.use_gpu:\n            return self.sample_gpu(shape)\n        else:\n            return self.sample_cpu(shape)\n\n    def sample_cpu(self, shape):\n        ps = numpy.random.uniform(0, 1, shape)\n        pb = ps * len(self.threshold)\n        index = pb.astype(numpy.int32)\n        left_right = (self.threshold[index] < pb - index).astype(numpy.int32)\n        return self.values[index * 2 + left_right]\n\n    def sample_gpu(self, shape):\n        ps = cuda.empty(shape, numpy.float32)\n        cuda.get_generator().fill_uniform(ps)\n        vs = cuda.empty(shape, numpy.int32)\n        cuda.elementwise(\n            '''int* vs, const float* ps, const float* threshold,\n            const int* values, int b''',\n            '''\n            float pb = ps[i] * b;\n            int index = __float2int_rd(pb);\n            // fill_uniform sometimes returns 1.0, so we need to check index\n            if (index >= b) {\n              index = 0;\n            }\n            int lr = threshold[index] < pb - index;\n            vs[i] = values[index * 2 + lr];\n            ''',\n            'walker_alias_sample'\n        )(vs, ps, self.threshold, self.values, len(self.threshold))\n        return vs\n", "path": "chainer/utils/walker_alias.py"}]}