A Novel Algorithm: the “Bi-PageRank-HITS” Algorithm
In class, we discussed the HITS algorithm developed by Professor Kleinberg at Cornell University. The HITS algorithm stands for hyperlink-induced topic search algorithm, a link analysis algorithm that rates Web pages. It assigns two scores to each page: its authority, the page people were originally seeking, and its hubs for the query, the high-value lists. We repeat the Authority Update Rule and Hub Update Rule to refine our estimates for authorities and hubs. It is a process whereby pages “vote” through in-links to assess the influence in social networks. Another algorithm we talked about in class is PageRank based on the settings where endorsement is passing directly from one page to another. According to the textbook, it can be viewed as a “fluid” that circulates through the network, passing from nodes to nodes.
The article I read recently introduces a new algorithm called a “Bi-PageRank-HITS” algorithm. It alternately conducts PageRank step and HITS step, a combination that consists of both the popular pages and a program that can obtain the most credible and relevant pages to the query. It is applied to a newly developed conversation system that can take the initiative to start conversations with new content while communicating with human beings. In this case, the algorithm can recognize meaningless utterances that represent “awkward silence” and then retrieve possible replies that contain relevant items from its knowledge base. The researchers denote queries (the utterances) as hubs, and candidate replies as authorities. The algorithm starts with the PageRank step to score the queries, and then a high hub score implies that the query is important. The following HITS step is to assess the appropriateness of replies to queries by interaction between to sides. Then another PageRank over authority side indicates important candidate replies and the information is sent back to queries similarly. In this way, the Bi-PageRank-HITS algorithm performs PageRank and HITS alternately and reinforces the important replies and queries.
I think the Bi-PageRank-HITS algorithm is interesting and makes sense to me. By performing the PageRank step and HITS step, the system computes the importance of the hubs and authorities in a reinforced way. The result theoretically becomes more credible and has higher quality. It is fundamentally a “reranking algorithm” that repeatedly performs a global iteration that includes ranking either side in the bipartite graph, propagating information to the other side, and then ranking the other side. After several iterations, the score will also converge to the limits. By employing this novel algorithm, the “chatbot” like Siri is able to initiate conversation itself after several smooth conversations and attempt to break the awkward silence. This will be typically useful in some particular scenarios; for example, when two people meet for the first time, they do not know what to say after several conversations. With this little conversation system, the AI is able to detect the “awkward silence” and come up with some sentences related to the topics that they mentioned before to facilitate the communication.
Reference:
Easley, David, and Jon Kleinberg. Networks, Crowds, and Markets Reasoning about a Highly Connected World. New York: Cambridge UP, 2010. Print.
http://www.dailymail.co.uk/sciencetech/article-3548387/Shut-Siri-Researchers-reveal-proactive-AI-mean-end-awkward-silence.html#comments
https://arxiv.org/pdf/1604.04358v1.pdf