數據結構與算法創新實驗教學實踐
——以跨模態檢索為例

宗林林， 于 紅， 劉馨月， 徐秀娟， 張曉彤， 張憲超

（大連理工大學軟件學院，遼寧 大連 116620）

0 引言

數據結構與算法是信息學科相關專業學生掌握計算機程序與現實世界問題關聯的入門課程。該課程的任務是使學生從應用角度出發，掌握基本數據結構的邏輯結構、物理結構及常用算法，能夠運用課程所討論的結構和算法更好地進行數據處理，為進一步提高程序設計的能力、進一步學習和掌握計算機專業基礎知識奠定基礎。本課程分成5 大部分：基本概念及線性表結構、樹與二叉樹、圖、檢索、排序。傳統教學中均使用傳統的案例進行講解并分析算法應用，在大數據蓬勃發展的今天具有較大局限性。

大學生創新創業訓練計劃項目的實施，有助于改革人才培養的模式，增加本科生的創新實踐經歷［1-2］。學生可以自主選題或者參與教師科研項目中的課題，經過項目背景調研、問題提出、設計解決思路、數據處理與實驗驗證幾個階段，最終完成整個項目的研發。通過開展大學生創新創業訓練項目，重點培養學生將課本中的理論知識應用于實際問題的能力，從而提高大學生的創新能力，進一步培養適應國家創新發展需求的高水平創新人才［3-5］。

本文以數據結構與算法課程中的檢索任務為例，在創新訓練項目中，分析大學生如何利用課本中的內容來提高分析問題和解決問題的創新能力。在大數據時代，數據常表現為文本、圖片、視頻、音頻等多模態形式［6］，多模態數據作為近年來被廣泛分析的一類數據，其數據特性與傳統單模態數據具有較大的差異。基于多模態數據方面的科研項目，結合數據結構與算法中檢索一章的內容，在跨模態檢索任務中，引導本科生提出自己的想法，在老師的指導下完成4 項大學生創新訓練項目。

1 跨模態檢索設計

隨著移動互聯網的迅速發展，網絡平臺的多媒體數據呈現出多模態、多樣化的特征，網絡多媒體數據的形式從單一文本數據逐漸轉變為表達形式生動、內容豐富的圖片、視頻、音頻等多模態數據，多模態數據融合過程貼近人類自主學習和認識世界的內在規律，因此如何實現多模態數據的有效整合，亟待深入研究和突破。

針對多模態數據處理相關項目背景和研究意義與前景［7］，學生初期獲取最為廣泛使用的維基百科多模態數據集，為后續的具體計算與分析奠定基礎。該數據集由2866 對圖像和文本組成，每一對由圖像和對應的完整文本文章組成，用以描述總共10 個語義類（即藝術，生物，歷史等）中的一種。基于維基百科數據，首先對于兩個模態中的數據，將第j個樣本中第i個模態定義為，然后將其中的ni個數據一一標識為，其中，1｝c是對應的語義標簽向量，其中c代表著語義種類數。如果樣的語義類別為第k類，則＝1，否則＝0。

與傳統檢索任務類似，跨模態檢索［8］也需要首先給定待查詢樣本，然后在數據集合中通過依次比較數據進行檢索。這里跨模態檢索任務可以分解為通過圖片檢索文本和通過文本檢索圖片兩個子任務。在圖檢文和文檢圖兩個子任務中，如果檢索樣本和檢索結果樣本的語義類別相同，則認為檢索成功，否則視為檢索失敗。與傳統檢索任務相比，跨模態檢索的難點在于如何在文本和圖像之間進行比較。圖1 展示了跨模態檢索任務的流程圖。

圖1 跨模態檢索流程圖

（1）為了對數據進行更好地處理，學生需要接觸并學習Python、文本和圖像特征提取方法，用基于Python語言的文本和圖像特征提取工具實現維基百科數據中文本和圖像內容的特征提取；

（2）進行數據挖掘操作，考慮到圖像和文本語義表達形式的不同，將不同模態結果映射到相同的子空間中，連接標簽向量單元進行損失計算；

（3）學生采用平均精度（mAP）作為檢索成功率的評價指標，繪制mAP 分數表格表示這一指標，并繪制查全率-查重率曲線輔助進行額外的比較。

2 大學生跨模態檢索創新實驗

學生通過老師提供的國內外相關資料，初步掌握文本和圖像兩個模態數據的特點，在一般數據挖掘知識的基礎上，認識到多模態數據的特性。相關的大學生創新項目采取漸進式教學方法［9］，主要進行了圖像標注實驗、可擴展跨模態檢索實驗；聯邦跨模態檢索實驗。

2.1 圖像標注實驗

跨模態任務涉及圖像處理、文本處理等知識，因此，首先通過一個圖像標注的實驗，令學生掌握基本的圖像和文本處理方法，學習跨模態學習領域的基本知識，掌握Python 語言及其使用環境等運用方法，感受到共同合作、各取所長、團結協作的重要性。

圖像標注的任務是根據圖像給出對應描述的自然語言語句。學生主要練習圖像特征提取和Transformer模型［10］的使用。學生在編碼器中通過ImageNet 上預訓練的InceptionV3 完成對圖像的相關特征提取［11］，得到一組64 ×2048 的特征向量，然后再經過一層全連接層對特征進行編碼，同時在解碼器中使用4 層Transformer。第1 層的輸入是真實標注命名為x，以及編碼器的輸出標注命名為enc_output。首先對x使用多頭注意力處理得到out，然后將out 作為下一個多頭注意力機制的查詢，enc_output 作為下一個多頭注意力的關鍵碼、值，然后輸出得到下一層的輸入y，往復執行之前的操作。

具體實施過程中，采用Python 環境下的TensorFlow 庫對圖像進行操作。通過tf. keras.applications.InceptionV3 使用在ImageNet 上預訓練的InceptionV3 模型。由于InceptionV3 模型要求輸入圖片的大小為299 × 299，因此在此之前需要使用tf.image.resize函數將所有圖片大小調整到299 ×299。預處理和標注處理時，選擇所有標注中的前100000個單詞來生成序列，計算所有標注的最大長度為52。實驗結果如圖2 所示，給定圖2 中的圖像，輸出圖2 的文字描述。

圖2 圖像標注結果展示（一輛雙層巴士在街上行駛）

2.2 可擴展跨模態檢索實驗

本項目主要研究可擴展跨模態檢索，以期望得到一個模態動態增加時的高效模型［12］。學生學習一個可拓展的深度跨模態檢索模型（SDML）［13］，分析模型的優缺點，保留模型優點，突破模型缺點，提出相應的解決方案，并進行實踐驗證。

SDML模型的基本思路是為每一個模態建立單獨的網絡，這些網絡各自的目標是讀取各自模態的數據，然后學習并轉換到固定子空間中進行學習，將數據投影到預定義的公共子空間P中，這種操作將使得不同類別之間數據之間的相關性被進一步提高。該方法可以在4 個核心部分進行優化：優化編碼器；優化解碼器；優化P矩陣；優化損失計算函數。經過反復試驗，發現對損失計算函數的修改導致效果提升不明顯，測試還發現解碼器對最后效果有提升作用但是并沒有預期中的提升，另外，因公共子空間過于繁雜且最后采取的樣本語義數量相同而忽略了對P 矩陣的修改。因此，主要在編碼器角度進行模型優化。

學生深入分析原模型中的編碼器，發現其僅僅由全連接層組成，這種結構非常依賴于輸入數據，一旦輸入數據特征不明顯就會導致模型的表現較差，僅僅依靠全連接層簡單地實現模型的通用性是不夠的。因此，指導學生優化編碼器結構。

對于圖像模態，學生將全連接結構替換成了卷積神經網絡（CNN）結構，具體而言，在全連接層前增加了4 層卷積層用于提取圖像特征，每層卷積層后連接了一個歸一化層以防止數據在進入下一層函數前因為數據過大而導致網絡性能的不穩定，下一層的線性整流層作為激勵函數給模型增加非線性語義，之后相連的一層最大池化層減少卷積層輸出的特征防止出現過擬合。卷積層和其余各層數量一致為4 個。對于全連接層，因卷積層的特征提取已經足夠，將其修改為單層全連接層做維度修改以映射到公共子空間中。

對于文本模態，學生采用對文本友好的文本卷積神經網絡（textCNN）模型，其思路和CNN類似，該模型對無上下文語義的文本分類非常有效。文本與圖像有著模態異構性，具體而言彩色圖像通常是三維表示，而文本則是二維數據，因此將卷積層進行縮減，由原先的4 層縮減到3 層以更高效地提取特征，并且在實現細節有區別，比如textCNN 使用的一維卷積，而CNN 使用的二維卷積。修改后的模型具體如圖3 所示。

圖3 修改后的模型展示

本項目的實驗在維基百科數據上，學生對比SDML模型，SDML-1 模型（上文中描述的使用CNN和textCNN 的版本）和SDML-2 模型（使用VGGNet 和Doc2 Vec提取特征的版本），3 種版本分別對應著無針對性神經網絡模型，簡單的神經網路模型，復雜的神經網絡模型。

在維基百科數據集上，圖4 分別顯示了圖像-文本和文本-圖像的查重率（Precision）、查全率（Recall）曲線。表1 中展示了修改模型mAP 的對比結果。通過它們之間的比較可以看出，為每個模態添加在各自分類中表現較好的特征提取模塊將提升跨模態檢索模型的效果，進而驗證學生修改方向的正確性。

表1 維基百科數據集上修改模型的mAP數值

圖4 維基百科數據集上的查全率-查重率曲線

2.3 聯邦跨模態檢索實驗

近年來由于互聯網的高速發展，互聯網用戶有關搜索引擎的旺盛需求不斷增加，而跨模態檢索在搜索引擎和多媒體數據中的地位也越來越重要。深度的跨模態檢索算法雖然性能很好但需要大量的訓練數據。然而，聚合大量的數據將會產生巨大的隱私風險和高昂的維護成本。該問題與學生日常生活非常接近，學生對此類問題興趣濃厚。經過調研后，發現要緩解用戶隱私問題，可以結合聯邦學習［14］的思想。本項目期待能夠使用分散的多模態數據學習模型。在跨模態檢索的基礎上，學生可以進一步接觸聯邦學習領域的知識，擴大學生知識面。

學生提出聯邦跨模態檢索方法FedCMR，在傳統的聯邦學習算法中，多個客戶端在可信中央服務器的協調下進行多輪通信，協作訓練模型。在每一輪通信過程中，各客戶端利用本地數據訓練模型，并將訓練成果模型上傳至中央服務器進行安全聚合。但是在客戶端本地模型架構復雜、參數量多的情況下，這樣的做法通常會導致訓練過程的通信開銷巨大。考慮到子空間學習法作為跨模態搜索的主流方法，其重點是找到不同模態數據共享的公共子空間，以度量不同模態數據之間的相似性。所以，如圖5 所示，提出用公共子空間代表客戶端模型，上傳至中央服務器，聯合尋找一個全局一致的潛在公共子空間。

圖5 聯邦訓練過程

具體實施過程分為本地訓練、聚合和本地更新3個過程。在本地訓練階段，每個客戶端都使用本地數據訓練跨數據檢索模型；在聚合階段，服務器會聚合客戶端的公共空間；在本地更新階段，每個客戶端根據最后一步計算的聚合模型更新本地模型的公共子空間。

學生在維基百科數據集上進行實驗，為了模擬聯邦跨模態檢索過程，在實驗中平均向3 個客戶端分配數據。為了使所有客戶獲得適合本地目標函數的高質量模型，將訓練過程分為聯合訓練和獨立增強訓練兩個階段。在聯合訓練階段，每個客戶端將隨機選擇80%的本地數據集來完成模型聚合過程。在獨立的增強訓練階段，每個客戶端完成本地更新過程，并繼續使用剩余20%的數據迭代本地模型，從而縮小全局一致的公共子空間，使其更適合本地模型測量來自不同模式的樣本之間的相似性。

在實驗中，采用一個19 層的VGNET 來學習圖像樣本的表示，并獲得VGNET的fc7 層為每幅圖像輸出的4096 維表示向量。為了表示文本樣本，使用句子BERT來學習每個文本的1024 維表示向量。利用廣泛使用的聯邦學習框架PySyft來模擬聯邦跨模態檢索過程。

為了證明所提出的聯邦學習方法的有效性，將FedCMR與以下方法進行了比較：①DSCMR［15］，它在每個客戶端上進行DSCMR，但不聚合客戶端；②FedAvg［16］，它在每個客戶機上執行DSCMR，然后使用FedAvg聚合客戶端。

表2、3 介紹了FedCMR的mAP評分和比較方法。從表中來看，有以下觀察結果：①FedCMR 顯著優于基準的聯邦學習方法FedAvg。②FedCMR 的總體表現優于DSCMR。結果表明，研究多模態聯邦學習是合理的，特別是在數據少量的情況下，多模態聯合學習對聚合跨模態檢索模型更有效。

表2 維基百科數據集上圖像→文本的mAP數值

表3 維基百科數據集上文本→圖像的mAP數值

3 實驗效果

目前，這些案例已在我校實施3 輪，共有3 屆學生受益。數據結構與算法課程于2020 年獲評遼寧省線上線下混合式一流課程。獲國家級大學生創新訓練項目1 項（多模態3D物體識別），省級大學生創新項目2項（基于深度神經網絡的跨模態檢索算法研究，基于跨模態學習的視頻檢索系統）和校級大學生創新項目1項（基于深度學習的跨模態檢索系統）。其中，省級大學生創新項目在第44 屆信息檢索研究與開發國際會議SIGIR 發表1 篇學術論文《FedCMR：Federated Cross-Modal Retrieval》［17］，并且其中一位成員推免至復旦大學攻讀研究生，一名成員推免至本校攻讀研究生。

4 結語

跨模態檢索創新實驗將教師的科研項目很好地融合到課程教學中，解決了數據結構與算法課程教學過程中理論與實際脫節的問題。通過參與跨模態檢索相關的創新實驗，學生的閱讀文獻、發現問題、創新意識、動手能力和團隊協作能力都得到了有效地提升，也加深了學生對理論學習的認識，深化了學生將理論知識應用到實際的能力。這些項目對于科研反哺教學、培養解決實際應用需求的高水平人才進行了一次有效的探索。