數(shù)據(jù)結(jié)構(gòu)與算法創(chuàng)新實驗教學(xué)實踐
——以跨模態(tài)檢索為例

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

（大連理工大學(xué)軟件學(xué)院，遼寧 大連 116620）

0 引言

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

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

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

1 跨模態(tài)檢索設(shè)計

隨著移動互聯(lián)網(wǎng)的迅速發(fā)展，網(wǎng)絡(luò)平臺的多媒體數(shù)據(jù)呈現(xiàn)出多模態(tài)、多樣化的特征，網(wǎng)絡(luò)多媒體數(shù)據(jù)的形式從單一文本數(shù)據(jù)逐漸轉(zhuǎn)變?yōu)楸磉_形式生動、內(nèi)容豐富的圖片、視頻、音頻等多模態(tài)數(shù)據(jù)，多模態(tài)數(shù)據(jù)融合過程貼近人類自主學(xué)習(xí)和認識世界的內(nèi)在規(guī)律，因此如何實現(xiàn)多模態(tài)數(shù)據(jù)的有效整合，亟待深入研究和突破。

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

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

圖1 跨模態(tài)檢索流程圖

（1）為了對數(shù)據(jù)進行更好地處理，學(xué)生需要接觸并學(xué)習(xí)Python、文本和圖像特征提取方法，用基于Python語言的文本和圖像特征提取工具實現(xiàn)維基百科數(shù)據(jù)中文本和圖像內(nèi)容的特征提取；

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

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

2 大學(xué)生跨模態(tài)檢索創(chuàng)新實驗

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

2.1 圖像標注實驗

跨模態(tài)任務(wù)涉及圖像處理、文本處理等知識，因此，首先通過一個圖像標注的實驗，令學(xué)生掌握基本的圖像和文本處理方法，學(xué)習(xí)跨模態(tài)學(xué)習(xí)領(lǐng)域的基本知識，掌握Python 語言及其使用環(huán)境等運用方法，感受到共同合作、各取所長、團結(jié)協(xié)作的重要性。

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

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

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

2.2 可擴展跨模態(tài)檢索實驗

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

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

學(xué)生深入分析原模型中的編碼器，發(fā)現(xiàn)其僅僅由全連接層組成，這種結(jié)構(gòu)非常依賴于輸入數(shù)據(jù)，一旦輸入數(shù)據(jù)特征不明顯就會導(dǎo)致模型的表現(xiàn)較差，僅僅依靠全連接層簡單地實現(xiàn)模型的通用性是不夠的。因此，指導(dǎo)學(xué)生優(yōu)化編碼器結(jié)構(gòu)。

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

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

圖3 修改后的模型展示

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

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

表1 維基百科數(shù)據(jù)集上修改模型的mAP數(shù)值

圖4 維基百科數(shù)據(jù)集上的查全率-查重率曲線

2.3 聯(lián)邦跨模態(tài)檢索實驗

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

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

圖5 聯(lián)邦訓(xùn)練過程

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

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

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

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

表2、3 介紹了FedCMR的mAP評分和比較方法。從表中來看，有以下觀察結(jié)果：①FedCMR 顯著優(yōu)于基準的聯(lián)邦學(xué)習(xí)方法FedAvg。②FedCMR 的總體表現(xiàn)優(yōu)于DSCMR。結(jié)果表明，研究多模態(tài)聯(lián)邦學(xué)習(xí)是合理的，特別是在數(shù)據(jù)少量的情況下，多模態(tài)聯(lián)合學(xué)習(xí)對聚合跨模態(tài)檢索模型更有效。

表2 維基百科數(shù)據(jù)集上圖像→文本的mAP數(shù)值

表3 維基百科數(shù)據(jù)集上文本→圖像的mAP數(shù)值

3 實驗效果

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

4 結(jié)語

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