以社群網路為基礎之問答系統

Social Network-Based Question Answering Systems

艾伊曼(Ali, Imad)

指導教授 ： 張佑榕 ； 徐正炘

國立清華大學/電機資訊學院/社群網路與人智計算國際博士學/博士(2020年)

摘要

Google，Bing和Yahoo!等網路搜尋引擎使用了自然語言處理、資訊檢索等諸多先進技術來取得相關網頁資訊，以回答使用者查詢的問題；一般而言，客觀事實問題可以得到很好的答案，然而，對於非客觀事實問題（例如觀點、推薦、建議等）則不是那麼容易回答，通常需要真人透過線上問答系統的方式來回應。在過去十年中，社群網站已廣泛用於線上溝通，並可基於興趣交流建立關係，這些社群網路有利於人們彼此共享和交換有用的資訊。因此，針對非客觀事實性問題，或可利用社群網路找到解答。但是，社群網路眾多使用者的興趣南轅北轍，專業程度亦有高有低，尤其在社群網路使用者多為弱連結，且上線使用時間亦非規律固定的情況下，如何透過如此動態的社群網路，適才適所地轉薦其中相對應程度的合適人選來回答問題，實非易事。此外，關於政治、宗教、黨派、醫療疾病等敏感議題，使用者可能不願涉入轉薦，然這些問題卻最需要專業知識水準等級的專家來回答。在社群網路中，由於使用者僅擁有一度分隔內的好友資訊，而最高等級的專家可能是他們第k度分隔的朋友，因此如何從動態社群網路中，以分散式檢索的方式，找出最高等級專家的應答者，是一大挑戰。

進一步想，在行動網路的環境下有各種網路頻寬、記憶體、處理器運算能力、與電力等限制，系統的輕量化更是極為重要。而輕量化檢索的設計卻十分困難。另外，由於在社群網路中提問者與k度分隔的使用者互不認識，也無法直接溝通，提問者不清楚k度分隔的應答者的可信度，也就很難評斷解答的正確性。因此，建立一個便於使用者評估所提供答案正確性的機制至關重要。此外，由於隱私問題，很多社群網路使用者並不會揭露自己的地理位置，因此，如果需要回答的問題是與地理位置相關的，從社群網路中找到合適的應答者也不太容易。針對上述的各項挑戰，本論文提出了一種基於社群網路的問答框架。

首先，本論文要解決的問題是，能夠透過動態社群網路鏈，轉薦適合的問題給特定專業等級的應答者，以期最快地取得所有問題的答案。社群網站使用者擁有不同的興趣愛好和專業知識，每個人的線上活動時間也大不相同，因此透過動態社群網路鏈，轉薦適合的問題給特定專業等級的應答者，使所有問題能夠最快地取得答案，會是一個非常具有挑戰性的問題。為了解決這個問題，本論文提出一個最佳化的問答系統，能夠透過動態社群網路鏈，轉薦適合的問題給特定專業等級的回答者，在最短的時間內取得回答。我們使用群播樹來（i）避免遇到在長時間內碰巧處於離線狀態的使用者而造成瓶頸，和（ii）蒐集多個應答者的回應，以提升答案的品質。該系統使用混合模型來估計每位應答者的專業級別，以便確定答題者的專業水準。所提方法與現存最佳方法相比，其獲得回應的時間更短，明確地來說，結果顯示所提系統可達到：（i）平均回應速率高出27％，（ii）平均最長回應時間降低多達60％，（iii）在應答者數量、問題出現率、應答者專業級別、可預測性等面向達到更好的效能。

接下來，本論文解決另一個問題：當使用者可能不願意轉薦關於政治、宗教、黨派、醫療疾病等敏感問題時，如何從動態社群網路中以分散式檢索最高專業級別的應答者？在社群網路中，使用者僅能從一度分隔內的好友中尋求答案，雖然他們第k度分隔的朋友中可能有最高級別的專家應答者，但他們彼此並不認識。為了解決這個問題，本文提出一種基於分散式社群網路的問答機制，該機制可以找到對應每個提問問題的最高專業級別應答者，並使回答率更高、回應時間更短。此方案在k度分隔內搜尋最高專業等級的應答者，並在每度分隔間選擇最佳轉薦者，以通過社交推薦鏈結成功轉薦問題。特別是利用在k度分隔內交換資訊的方式，在每度分隔間選擇最佳轉薦者，以搜尋出最高專業等級的應答者。模擬結果顯示，與現存最佳方法相比，所提方法可達到：（i）平均專業等級提高42％以上，（ii）平均回應率提高26％以上，（iii）縮短回應時間達27％。此外，在各種系統參數（例如問題出現率、每個問題的關鍵字數、每個問題的答覆者數、分隔度數和可預測性等）下，所提方法都比現存最佳方法有更好的表現。

本論文要解決的下一個問題，是提高問答系統的效能，設計更輕量化的方式以符合行動網路的需求。透過適當的朋友（或幫助者）轉發問題，也許能夠在多度分隔下取得特定問題的答案。但是，在有效訊息量有限的情況下，如何分散式搜尋最佳幫助者，是一個具挑戰性的問題。本論文提出一種分散式的輕量化架構，將幫助者選擇的方法結合到基於社群網路的問答系統中。所有使用者都看得到一度分隔內好友的資訊登錄，我們所提方法則運用上述訊息記錄來選擇幫助者，以轉發問題至朋友群中有能力且有意願合作的幫助者，從而提升問答系統的效能。足跡驅動的模擬結果顯示，平均而言，我們所提出的幫助者選擇方法達到更高的回應速度、更高的最佳回答率、更快的回應時間，相較於現存最佳方法，上述各項分別可達到14％、13％和14％的進步。此外，亦觀察到所提方法在各種系統參數設定下，都超越現存最佳方法而有更好的表現。

接下來，本論文解決了評估k度分隔應答者的答案正確性的問題。在分散式社群網路中，提問者不知道k度分隔應答者的可信程度，因此很難評估答案的正確性。因此，一套以分散式社群網路為基礎且提供答案可信度參考的問答系統，對於確定答案的正確性至關重要。本論文提出一套架構，幫助每個使用者評估所接收答案的正確性。此方法在不確定性條件下利用主觀邏輯建立了朋友對朋友的信譽參考值，並按興趣分類，將如此形成的主觀意見累積統計當成每位使用者的可信度匯總參考值，以反映使用者的實際可信度，再將問題轉發給在該類別中具有最佳可信度參考值的使用者。結果顯示，與現存最佳方法相較，我們的方法具有更高的成功率、更高的答案正確性和更低的答案不確定性，平均差距分別達12.1％、16.4％和22.2％。

最後，本論文解決了地理相關性的問題，也就是當使用者所關注的問題具有地理位置資訊。我們發現有51％的使用者會查尋與其所在地理位置相關的資訊，然現有系統卻無法回答此類問題，因為處理此類問題並非現存系統設計的主要目的。為了解決這個問題，本論文提出一種在動態社群網路中讓使用者能夠提供及時準確的答案的架構。此方法挖掘使用者的共享資訊與內容脈絡，以找出每個問題的最相關使用者。我們提出一種多模式激勵架構，利用使用者的社交聯繫和金錢獎勵提高意願程度。此方法利用多模式激勵架構找出相關使用者的意願等級，並透過我們提出的三種演算法在動態社群網路中積極地指派問題給最相關、最高信譽且意願程度最高的使用者來回答。我們完成了：（i）一項調查，以檢視是否支持我們提出的多模式激勵架構的假設，以及（ii）足跡驅動的實驗，以評估我們提出的三種演算法的效能。

關鍵字

社群網站 ； 問答系統 ； 高級別的專家 ； 路由 ； 通訊協定 ； 非客觀事實問題

並列摘要

The Web-search engines such as Google, Bing, and Yahoo! retrieve relevant Web-pages to users’ factual questions using modern technologies such as natural language processing and information retrieval; however, they are less suitable for answering non-factual questions (e.g., opinions, recommendations, suggestions, etc.) which are better answered by humans via online question answering systems. In the last decade, social networks have been vastly adopted for online communications. Besides, using social networks for building interest-based relationships, people also utilize these networks for sharing and exchanging useful information with each other, and hence could be leveraged for answering non-factual questions. However, social network users own different interests and have diverse expertise levels; therefore, identifying answerers of particular expertise levels and routing the questions to them via social referral chains in the dynamic social networks, where users have a diverse range of availability times and are sporadically connected to each other, is not easy.

Moreover, users may not be willing to route political, religious, sectarian, medical disease, etc., kind of questions over the Internet due to its sensitive nature; however, at the same time, they do require answers from answerers of the highest expertise levels. Since users in social networks have information of their 1-hop friends only where answerers of the highest expertise levels may exist in the k-hop friends, therefore, distributively identifying the answerers of the highest expertise levels in dynamic social networks is a challenging problem. Further, when considering a mobile environment, a light-weight scheme is crucial for finding the answerers as mobile users are associated with limited resources such as bandwidth, memory, processing power, and energy. Finding answerers with a light-weight scheme is, however, challenging. Additionally, since askers do not communicate with k-hop answerers directly in social networks, they do not know the k-hop answerers’ credibility levels, thereby making it difficult for askers to assess the correctness of their provided answers. Thus, facilitating users to assess the correctness of the provided answers is crucial. Also, a significant fraction of social network users do not declare their locations due to privacy concerns; thus, finding relevant answerers for answering local intent questions in social networks is not easy. To address these challenges, this dissertation proposes a social network-based question answering framework.

First, this dissertation addresses the problem of finding answerers of particular expertise levels and routing the questions to them via social referral chains in a dynamic social network so as to minimize the response time of each question. Social network users own different interests, expertise levels, and online activity times, thus identifying answerers of particular expertise levels and routing the question to them in a dynamic social network, so as to receive the answers for every question in a short time is a challenging problem. To address this problem, this dissertation proposes an optimal question answering system that identifies answerers with the required expertise levels and routes the question with minimum possible response time in the dynamic social network. A multicast tree is employed to (i) avoid the chance of running into bottleneck users who happen to be offline for considerable time durations, and (ii) increase the quality of answers from multiple answerers. The proposed system uses a hybrid model for estimating the expertise levels of each user in order to identify the answerers’ expertise levels. The proposed method demonstrates improved response time performance as compared to state-of-the-art systems. In particular, the evaluation results reveal that the proposed system achieves: (i) higher average response rate up to 27%, (ii) lower average maximal response time by up to 60%, and (iii) consistently better performance when the number of answerers, the arrival rate of questions, the level of expertise, and the predictability are varied.

Next, this dissertation addresses the problem of distributively finding answerers of highest expertise levels in a dynamic social network when users are not willing to route political, religious, sectarian, medical disease, etc., kind of questions over the Internet while requiring answers from answerers of the highest expertise levels. In social networks, askers’ search answerers among their 1-hop friends; however, answerers of highest expertise levels may exist in the k-hop friends of social networks who are not known to askers directly. To address this problem, this dissertation proposes a distributive social network-based question answering scheme that finds answerers of the highest expertise levels to each asker’s question with a higher response rate and lower response time. The scheme finds answerers of highest expertise levels in the k-hop dynamic social network and selects optimal relays at each hop to forward the question to, via social referral chains. In particular, the profile information is exchanged among the k-hop friends, and leveraged for finding answerers of the highest expertise levels and optimal relays at each hop. The simulation results show that, compared to state-of-the-art schemes, the proposed scheme achieves: (i) higher average expertise levels by more than 42%, (ii) higher average response rate by more than 26%, and (iii) lower response time with as high as 27% reduction. Furthermore, under various system parameters like question arrival rate, keywords per question, answerers per question, number of hops, and predictability, the proposed scheme consistently outperforms the state-of-the-art schemes.

Next, this dissertation addresses the problem of improving the performance of a mobile social network-based question answering system with the help of a light-weight scheme. Answers to the particular question may be found when the questions are forwarded via suitable friends (or helpers) in a multi-hop manner. However, with a limited amount of available information, distributively identifying the best helpers is a challenging problem. To this end, this dissertation proposes a distributed and a light-weight helper selection scheme, incorporated into a social network-based question answering system. All users share their information with the 1-hop friends and are recorded in each user’s information register. The proposed helper selection scheme utilizes the information to select and forward the questions to capable and cooperative helpers among the friends to improve the performance of the question answering system. The trace-driven simulations reveal that, on average, the proposed helper selection scheme achieves a higher response rate, higher best-answer rate, and lower response time by more than 14%, 13%, and 14%, respectively, in comparison to state-of-the-art helper selection schemes. Further, it is observed that the proposed helper selection scheme performs consistently better than the state-of-the-art systems under diverse system parameters settings.

Next, this dissertation addresses the problem of assessing the answer correctnesses of the k-hop answerers. In a distributed social network, an asker does not know a k-hop answerer’s credibility, thus making it difficult for the asker to assess the answer correctness. Therefore, a credibility-enabled distributed social network-based question answering system is crucial for determining the correctness of the answers. To this end, this dissertation proposes a scheme, which facilitates each user to assess the correctness of the received answers. The proposed scheme utilizes subjective logic to build interest-wise friend-to-friend credibility opinions under uncertainties. The developed opinions are then accumulated by the proposed scheme to get each user’s aggregated credibility opinion, which may reflect the user’s real credibility. The proposed scheme forwards a question to users with the highest credibility beliefs in the question interest category. Our evaluation results show that, on average, the proposed scheme accomplishes higher success ratio, higher answer correctness, and lower answer uncertainty by 12.1%, 16.4%, and 22.2%, respectively, as compared to the best-performing baseline systems.

Lastly, this dissertation addresses the problem of local intent questions where users are interested in finding specific information about various items over particular locations. It is found that 51% of users seek information about their localities. The existing systems fail to answer this class of questions as they are not mainly designed to handle it. To address this problem, this dissertation proposes a scheme where users provide timely and accurate answers in a dynamic social network. The scheme mines users’ shared and contextual information to identify the most relevant users for each question. We propose a multimodal motivation scheme that exploits users’ social ties and monetary rewards to raise their basic motivation levels. The scheme utilizes the multimodal motivation scheme to find the relevant users’ motivation levels, and actively assigns questions to most relevant users with the highest reputations and motivation levels in the dynamic social network via our three proposed algorithms. We conduct: (i) a survey to support our assumptions regarding the proposed multimodal motivation scheme, and (ii) trace-driven experiments to evaluate the performance of the three proposed algorithms.

並列關鍵字

Social Networks ； Question Answering Systems ； High-quality Answerers ； Routing ； Protocols ； Non-factual Questions

參考文獻

[1] R. Morris, J. Teevan, and K. Panovich, “A comparison of information seeking using search engines and social networks,” Proc. of ICWSM, vol. 10, pp. 23–26, May 2010.

[2] B. Li and I. King, “Routing questions to appropriate answerers in community question answering services,” in Proc. of ACM CIKM, Oct. 2010, pp. 1585–1588.

[3] F. M. Harper, D. Raban, S. Rafaeli, and J. A. Konstan, “Predictors of answer quality in online Q&A sites,” in Proc. of ACM SIGCHI, Apr. 2008, pp. 865–874.

[4] S. A. Paul, L. Hong, and E. H. Chi, “Is twitter a good place for asking questions,” in Proc. of ICWSM, Jun. 2011.

[5] Z. Liu and B. J. Jansen, “Predicting potential responders in social Q&A based onnon-QA features,” in Proc. of ACM CHI, Apr. 2014, pp. 2131–2136.