Multi-intent natural language sentence classification aims at identifying multiple user goals in a single natural language sentence (e.g., “find Beyonce’s movie and music” ! find movie, find music). The main motivation of this work is to exploit the shared intents across different intent combinations rather than treating the combination as an atomic label. We propose to achieve this by (1) adding class features, and (2) adding hidden variables to identify segments belonging to each intent. Experimental results demonstrate significant gains in classification accuracy over the baseline methods across a number of training conditions (3%-8% absolute on multi-intent sentences, 2%-3% absolute on single intent sentences).