我學者針對最優(yōu)子集選取提出新算法在有限步內(nèi)得到穩(wěn)定解

2020-12-25 09:43:36來源：科技日報

記者從中國科學技術(shù)大學獲悉，該校管理學院教授王學欽團隊與美國耶魯大學公共衛(wèi)生學院教授張和平合作，針對線性回歸模型的基準問題——最優(yōu)子集選取，提出一種新的快速算法，在有限步內(nèi)就能得到穩(wěn)定解。該成果日前發(fā)表于《美國科學院院刊》。

發(fā)現(xiàn)事物間的關(guān)系是大部分科學研究的目的，這在統(tǒng)計學中稱之為回歸分析。其中，線性回歸模型由于其簡潔性和可解釋性，成為最有用的科學研究工具之一。最優(yōu)子集算法泛指多元回歸分析中自變量選擇時旨在尋找為數(shù)不多的，根據(jù)指定準則是“最優(yōu)”回歸模型的計算方法。盡管線性回歸模型被如此廣泛使用，但其中一個很基本的問題——如何在一組變量中選擇最優(yōu)的子模型，尚未解決。

當前，得益于現(xiàn)代科技的發(fā)展，數(shù)據(jù)的收集越來越便利，在典型的生物醫(yī)學研究中會收集到上百個變量，常規(guī)的全基因組研究中則涉及成千上萬甚至是百萬級別的遺傳變異。然而，現(xiàn)有的算法難以在上萬級別的實際問題中尋找到最優(yōu)子集。

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

(吳長鋒桂運安)

責任編輯：hnmd003