To explore the relationship between HCN yields in smoke stream and main nitrogen compounds in flue-cured tobacco leaf, 60 samples were selected from main tobacco-planting areas in China. The new machine learning algorithm named MINE (maximal information-based nonparametric exploration) was used to study the relationship between the HCN and the main nitrogen compounds. The results showed that HCN yields in smoke stream exhibited close relationship with nitrogen compounds, the relationship strength (MIC) with protein, nicotine and total content of amino acid reached 0.396 7,0.403 4 and 0.352 1, respectively; and the MIC with cysteine, glutamic acid and arginine reached 0.388 7,0.326 3 and 0.353 7, respectively; indicating these nitrogen compounds significantly influence the HCN yields in smoke stream.