Part III Web Information Retrieval Formal Theory of Connectionist Web Retrieval

Abstract

The term soft computing refers to a family of techniques consisting of methods and procedures based on fuzzy logic, evolutionary computing, artificial neural networks, probabilistic reasoning, rough sets, chaotic computing. With the discovery that the Web is structured according to social networks exhibiting the small world property, the idea of using taxonomy principles has appeared as a complementary alternative to traditional keyword searching. One technique which has emerged from this principle was the " web-as-brain " metaphor. It is yielding new, associative, artificial neural networks-(ANN-) based retrieval techniques. The present paper proposes a unified formal framework for three major methods used for Web retrieval tasks: PageRank, HITS, I 2 R. The paper shows that these three techniques, albeit they stem originally from different paradigms, can be integrated into one unified formal view. The conceptual and notational framework used is given by ANNs and the generic network equation. It is shown that the PageRank, HITS and I 2 R methods can be formally obtained from the generic equation as different particular cases by making certain assumptions reflecting the corresponding underlying paradigm. The unified formal view sheds a new light upon the understanding of these methods: it may be said that they are only seemingly different from each other, they are particular ANNs stemming from the same equation and differing from one another in whether they are dynamic (a page's importance varies in time) or static (a page's importance is constant in time), and in the way they connect the pages to each other. The paper also gives a detailed mathematical analysis of the computational complexity of WTA-based IR techniques using the I 2 R method for illustration. The importance of this analysis consists in that it shows that (i) intuition may be misleading (contrary to intuition, a WTA-based algorithm yielding circles is not always " hard "), and (ii) this analysis can serve as a model that may be followed in the analysis of other methods.