?

2020年12月16日，中國(guó)科學(xué)技術(shù)大學(xué)管理學(xué)院王學(xué)欽教授團(tuán)隊(duì)與美國(guó)耶魯大學(xué)公共衛(wèi)生學(xué)院的Heping Zhang教授合作在美國(guó)科學(xué)院院刊《PNAS》在線發(fā)表題為“Apolynomial algorithm for best subset selection problem”的研究論文， 針對(duì)線性回歸模型的基準(zhǔn)問題——最優(yōu)子集選取，提出了一種快速算法。

發(fā)現(xiàn)事物間的關(guān)系是大部分科學(xué)研究的目的，這在統(tǒng)計(jì)學(xué)中稱之為回歸分析。其中，線性回歸模型由于其簡(jiǎn)潔性和可解釋性而成為最有用的科學(xué)研究工具之一。盡管線性回歸模型被如此廣泛的使用，但其中一個(gè)很基本的問題：如何在一組變量中選擇最優(yōu)的子模型，尚未解決。這個(gè)問題的求解被認(rèn)為是NP-hard問題。得益于現(xiàn)代科技的發(fā)展，數(shù)據(jù)的收集變得越來(lái)越便利，在典型的生物醫(yī)學(xué)研究中會(huì)收集到上百個(gè)變量，常規(guī)的全基因組研究中則涉及到成千上萬(wàn)甚至是百萬(wàn)級(jí)別的遺傳變異?，F(xiàn)有的算法難以在上萬(wàn)級(jí)別的實(shí)際問題中尋找到最優(yōu)子集。

為了解決這個(gè)問題，王學(xué)欽團(tuán)隊(duì)利用排序和剪接的思想結(jié)合一個(gè)新的信息準(zhǔn)則發(fā)展出一種新的算法，使得算法在有限步內(nèi)就能得到穩(wěn)定解；并證明了在一定條件下，依大概率，該算法具有多項(xiàng)式的時(shí)間復(fù)雜度，而且能夠選出最優(yōu)子集。

圖一算法的計(jì)算時(shí)間隨著變量個(gè)數(shù)增加的散點(diǎn)圖。其中上圖是新提出的算法，下圖是經(jīng)典的最優(yōu)子集選取算法。

中國(guó)科學(xué)技術(shù)大學(xué)王學(xué)欽教授和耶魯大學(xué)Heping Zhang教授為論文的共同通訊作者，中山大學(xué)博士生朱俊賢和中國(guó)科學(xué)技術(shù)大學(xué)溫燦紅特任副研究員為論文的共同第一作者。該研究得到了國(guó)家重點(diǎn)研發(fā)項(xiàng)目，國(guó)家自然基金委項(xiàng)目和安徽省自然基金委項(xiàng)目等資助。

論文鏈接：https://doi.org/10.1073/pnas.2014241117

（管理學(xué)院、科研部）