帶約束的圖上學習算法研究 

《帶約束的圖上學習算法研究 》是依託揚州大學，由何萍擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：帶約束的圖上學習算法研究 
• 項目類別：青年科學基金項目
• 項目負責人：何萍
• 依託單位：揚州大學

項目摘要

基於圖的學習套用圖論處理具有潛在圖結構的機器學習問題。一個基於圖的學習算法能否產生好的性能在很大程度上取決於它對約束信息的利用程度。然而，人們卻鮮少從圖約束的角度系統地分析已有學習算法對約束信息的利用方式及其存在的不足之處。本項目擬將圖上學習的約束信息劃分為圖的一階、二階和高階約束，首先針對帶一階圖約束的分類和帶二階圖約束的聚類，分別提出一種採用對偶約束利用策略的流形分類算法和線上半監督聚類算法，它們與以往的分類和聚類算法相比，對低階圖約束的利用更高效更全面。在此基礎上，我們擬提出一種具有高階圖約束的半監督學習問題，證明它是以往具有圖的低階約束和超邊約束的半監督學習問題的泛化描述，並針對其中帶子圖約束的半監督分類問題，提出一種能充分利用高階約束結構特徵的半監督分類算法，提高對高階圖約束的利用範圍和效率。本項目的研究能夠為帶約束的圖上學習算法提供理論基礎，進一步推動圖上學習方法的發展和套用。

結題摘要

近年來，基於圖的學習越來越受到機器學習和數據挖掘研究者的關注。一個基於圖的學習算法能否產生好的性能在很大程度上取決於它對約束信息的利用程度。然而，人們卻鮮少從圖約束的角度系統地分析已有學習算法對約束信息的利用方式及其存在的不足之處。以往的圖學習研究大多孤立地看待圖和約束兩部分信息，僅限於局部地研究某種特定約束的利用方式，缺乏對各種形式各異的圖約束的一個整體認識，同時也缺乏在全局觀基礎上對圖約束的有效利用。本項目將圖上學習的約束信息劃分為圖的一階，二階和高階約束。針對具有圖的一階約束的有監督分類問題，我們提出一種採用“點→邊→點”的約束利用策略的流形非線性多分類算法，即有監督等度規映射分類器。與其他分類算法相比，該算法從圖的一階和二階結構兩方面同時利用給定約束信息，提高了對一階圖約束的利用效率，有利於提高分類準確率。針對具有圖的二階約束的半監督聚類問題，我們提出一種採用“邊→點→邊”約束利用策略的線上雙層隨機遊走半監督聚類算法。與其他半監督聚類算法相比，該算法不僅能夠處理靜態的半監督聚類問題，而且還能高效地處理數據和約束都隨時間更新的線上半監督聚類問題，提高了對二階圖約束的利用效率，有助於發現數據潛在的簇內亞結構。在處理低階圖約束的基礎上，我們進一步針對具有圖的高階約束的分類問題，提出一種能夠利用約束的高階結構特徵的層次多流形分類算法。該算法可以用於處理複雜數據內部包含子數據的分類問題。考慮到有標籤數據的高代價性，我們還把層次多流形分類算法擴展為能夠利用高階圖約束的半監督分類算法，可以從少量的無標籤數據準確推導出大量無標籤數據的類別。與以往的超圖學習算法相比，該算法不僅拓寬了對高階圖約束不同表現形式的利用範圍，而且還提升了半監督學習算法對高階圖約束的利用效率。此外, 我們還套用這些帶圖約束的學習算法有效解決了一些實際套用問題，包括人臉識別，手寫字元識別和醫療診斷等領域，取得了很好的效果。