{"action":"created","issue":{"url":"https://api.github.com/repos/fchollet/keras/issues/3170","repository_url":"https://api.github.com/repos/fchollet/keras","labels_url":"https://api.github.com/repos/fchollet/keras/issues/3170/labels{/name}","comments_url":"https://api.github.com/repos/fchollet/keras/issues/3170/comments","events_url":"https://api.github.com/repos/fchollet/keras/issues/3170/events","html_url":"https://github.com/fchollet/keras/pull/3170","id":164393342,"number":3170,"title":"Potential New Feature: Hierarchical Softmax","user":{"login":"jmhessel","id":178075,"avatar_url":"https://avatars.githubusercontent.com/u/178075?v=3","gravatar_id":"","url":"https://api.github.com/users/jmhessel","html_url":"https://github.com/jmhessel","followers_url":"https://api.github.com/users/jmhessel/followers","following_url":"https://api.github.com/users/jmhessel/following{/other_user}","gists_url":"https://api.github.com/users/jmhessel/gists{/gist_id}","starred_url":"https://api.github.com/users/jmhessel/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jmhessel/subscriptions","organizations_url":"https://api.github.com/users/jmhessel/orgs","repos_url":"https://api.github.com/users/jmhessel/repos","events_url":"https://api.github.com/users/jmhessel/events{/privacy}","received_events_url":"https://api.github.com/users/jmhessel/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":19,"created_at":"2016-07-07T19:55:57Z","updated_at":"2016-08-30T22:11:16Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/fchollet/keras/pulls/3170","html_url":"https://github.com/fchollet/keras/pull/3170","diff_url":"https://github.com/fchollet/keras/pull/3170.diff","patch_url":"https://github.com/fchollet/keras/pull/3170.patch"},"body":"(pull request version of issue #3143 , hoping to get some feedback as a pull request, though I doubt the code I currently have written is adequate. I don't want to go through doing PEP-8 things/squashing everything down into a single commit just yet, because there's still work to do.)\r\n\r\n# What is hierarchical softmax used for?\r\n\r\nHierarchical softmax is an approximate version of softmax that is much faster to compute when the number of potential classes is high. In general, hierarchical softmax is used in language modeling tasks, where vocabulary sizes exceed ~10K. For very large vocabulary scenarios (think 1M word vocab) the normal softmax is computationally expensive. Two popular methods for approximating the softmax in cases of large vocabularies are negative sampling (a simplification of noise-constrastive estimation) and hierarchical softmax. The version I have implemented is the two-layer version, originally given [here](http://arxiv.org/abs/cs/0108006). This version is thought to be efficient for GPUs, in particular, because it decomposes the softmax into two reasonably sized matrix multiplications.\r\n\r\n# How does hierarchical softmax work?\r\n\r\nHierarchical softmax can be thought of as a tree -- each leaf node of the tree is a class of softmax. Instead of computing a probability distribution over all possible classes given an input vector, hierarchical softmax computes the probability of a *single given class* (generally the correct class) given an input vector. Each node on the path from the root to the correct leaf node is tasked with making a decision about which of its children it should go to. Each node learns a linear classifier to pick a child node given an input, and the total probability of the correct class is modeled as the product of the probabilities of the correct decision at each node from the root to the correct leaf node.\r\n\r\nFor a much better explanation, check out Hugo Larochelle's [video](https://www.youtube.com/watch?v=B95LTf2rVWM)\r\n\r\n# What's the status of the implementation?\r\n\r\nI have forked keras, and believe that I have a somewhat functional version of [two-layer hierarchical softmax](https://github.com/jmhessel/keras/blob/master/keras/layers/advanced_activations.py#L268-L395). However, it's pretty messy (see below).\r\n\r\nI have tested it on a simple MNIST MLP classification model, and in a \"large number of classes\" case. In some cases, it runs 10x faster than normal softmax. In other cases, it's comparable or even slower than normal softmax. I wrote a [dummy task](https://github.com/jmhessel/keras/blob/master/examples/hsm_benchmark.py) script, which also demonstrates how to use the layer..\r\n\r\n# Remaining questions\r\n- Is this a feature keras wants to have in the main repo? Should I keep working on this?\r\n- I added an additional objective function: \"mean identity error,\" which basically ignores the targets, and simply takes a mean over the input tensor. This causes Theano to raise a warning about unused portions of the computation graph. Mean identity error is good for hierarchical softmax, because the layer outputs the negative log probability of the correct class -- this is something that should probably be minimized. The \"right\" solution might be to have models that require no labels (e.g. it could become legal to pass \"None\" as the target when using mean identity error; this could be useful for a variety of models outside of hierarchical softmax).\r\n- Is my implementation too messy? It was a bit of a pain to write, and seems a bit inefficient, and I had to do some things in a relatively round-about way (e.g. the indexing operations are strange and messy). The messiness potentially derives from both my own coding skills, and from the limited set of functions supported by the backend (see below).\r\n- Theano has an [implementation](https://github.com/Theano/Theano/blob/master/theano/tensor/nnet/nnet.py#L2234-L2347) of hierarchical softmax, which would be ideal to use. Theano's HSM is made efficient by a specialized call to \"sparse_block_dot,\" which is not in the keras backend because, to my knowledge, this operation doesn't exist in tensorflow. Many of the messy operations I had to write would be eliminated if there were access to this operation through keras. Would it be possible to support an operation only for one backend (this would allow for the use of theano's optimized implementation)? Or is that not worth it? "},"comment":{"url":"https://api.github.com/repos/fchollet/keras/issues/comments/243597874","html_url":"https://github.com/fchollet/keras/pull/3170#issuecomment-243597874","issue_url":"https://api.github.com/repos/fchollet/keras/issues/3170","id":243597874,"user":{"login":"braingineer","id":1455742,"avatar_url":"https://avatars.githubusercontent.com/u/1455742?v=3","gravatar_id":"","url":"https://api.github.com/users/braingineer","html_url":"https://github.com/braingineer","followers_url":"https://api.github.com/users/braingineer/followers","following_url":"https://api.github.com/users/braingineer/following{/other_user}","gists_url":"https://api.github.com/users/braingineer/gists{/gist_id}","starred_url":"https://api.github.com/users/braingineer/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/braingineer/subscriptions","organizations_url":"https://api.github.com/users/braingineer/orgs","repos_url":"https://api.github.com/users/braingineer/repos","events_url":"https://api.github.com/users/braingineer/events{/privacy}","received_events_url":"https://api.github.com/users/braingineer/received_events","type":"User","site_admin":false},"created_at":"2016-08-30T22:11:16Z","updated_at":"2016-08-30T22:11:16Z","body":"in case you all didn't seen this paper, from some folks at Facebook [Strategies for Training Large Vocabulary Neural Language Models](http://arxiv.org/abs/1512.04906).\r\n\r\n> Welin Chen, David Grangier, Michael Auli\r\n(Submitted on 15 Dec 2015)\r\nTraining neural network language models over large vocabularies is still computationally very costly compared to count-based models such as Kneser-Ney. At the same time, neural language models are gaining popularity for many applications such as speech recognition and machine translation whose success depends on scalability. We present a systematic comparison of strategies to represent and train large vocabularies, including softmax, hierarchical softmax, target sampling, noise contrastive estimation and self normalization. We further extend self normalization to be a proper estimator of likelihood and introduce an efficient variant of softmax. We evaluate each method on three popular benchmarks, examining performance on rare words, the speed/accuracy trade-off and complementarity to Kneser-Ney."}}
{"actor":{"display_login":"braingineer"}}