This paper presents a study on personalized add-on filters applied to web search results in order to make those results more intuitive to users. Fuzzy Sets and Logic are used in order to construct such filters. Linguistic features are extracted as their universe of discourse. Three experimental filters are presented in the following specific contexts: (1) narrowing down results, (2) product specification and (3) tutorial level classification. Their performance is briefly studied mostly in qualitative manners.
Users on the Internet very likely use search engines such as Google and Bing in order to search and access to information of interest. As they enter some key words, the search engines instantaneously respond lists of web pages that are relevant to those key words in the order of significance. While the quality of search results is generally satisfactory, the users often demand finer tunings, e.g. in terms of contexts, descriptors and dependencies among key words in phrases. The following lists a few examples of such discrepancies: Contexts. Totally different contexts intended by users, e.g. a type of coffee beans vs. software components for the key word ’java beans’.
Descriptors. Descriptors that do not symbolically match with words in target web pages, e.g. some quantifiers such as ’most’ vs. actual quantities such as ’99%’ and qualifiers such as ’good’ vs. similar ones such as ’high quality’ and ’well written’.
Dependencies among words. Symbolic keyword matching in search engines is most likely performed based on regular grammars (to handle word conjugations) and often yields weak or no relevancy, e.g. ’fuzzy parser’, when interpreted as a list of two key words ’fuzzy’ and ’parser’, vs. texts in target web pages such as ’The parser avoids fuzzy words...’, ’Parsing a query e.g. founder of fuzzy logic’ and ’... fuzzy sets. ... C parser to compile ...’.
In theoretical aspects, web page ranking predominantly
follows a fundamental ingredient in the development and
success of the Google search engine, and the significance
is determined based on references and citations (i.e. links)
made to that web page (a comprehensive survey is made in
reference
On the other hand, many others hope for additional fine tunings on the search results in order to overcome those discrepancies. As having been already noticed, all of those discrepancies are caused generally by lack of various linguistic processing on target web pages–e.g. lexical and semantic processing for the matters of contexts and descriptors, and syntactic and morphological processing for those of the dependencies among words. Knowing this difference on the basis of determining significance, i.e. structural (links) versus linguistic (texts), we anticipate an effectiveness of some linguistic functionalities that compensates the structural page ranking methods.
In this paper, we consider a study on such linguistic
functionalities as personalized add-on filters that alter web
page rankings generated by conventional web engines, e.g.
Google and Bing, in specific, personalized contexts. The
input of such a filter is a list of (links to) web pages in an order
of significance based on their structures. In text
processing aspects, this is considered as stream processing of texts
with a demand of real-time response (e.g. just as Google
responds to a search query). We deploy Fuzzy Sets and Logic
as the base method given its proven efficiency on stream
processing (e.g. Fuzzy Controls
Related concepts such as page ranking and fuzzy sets and logic are briefly introduced in the next section. Then three experimental filters are presented along with their qualitative studies on performance for the following specific contexts: 1In practice, massive web pages and their ranks are precompiled and key words are indexed by web crawlers, autonomous processes that explore links and URLs. narrowing down results, product specification and tutorial level classification. Some clear distinction from other similar works is made within the experimental setting.
The following related concepts are briefly introduced: Page Ranking, Regular Grammar, Fuzzy Sets and Fuzzy Logic.
Let I(P ) the significance of page P and B be the set of
pages that refer to (i.e. have a link to) page P
I(P ) = X I(Pi)
Pi2B li
To determine I(P ), we need I(Pi) 8Pi 2 B and so do we for each and every one of those pages. This certainly causes ”chicken and egg” situation. To resolve this situation, we use the power method. Let H = [Hij ] be a square matrix2 representing references (links) among all web pages P1; : : : ; Pn such that
Hij = 1 lj 0 if Pj 2 Bj otherwise and let I = [I(Pi)] be a vector whose components are the significance of all the web pages. Then we observe I = H I. This means that I is an eigenvector (aka a stationary vector) with = 1. The power method iteratively computes
H Ii = v = i+1 Ii+1 until Ii = Ii+1 (i.e. practically jIi(P ) Ii+1(P )j < for all components). The initial eigenvector usually has only one component whose value is 1, and the remaining components have 0s. The initial eigenvector is 1 = 1. The convergence of this iteration is determined whether j 2j < 1, and its speed (i.e. #iterations) is determined by the magnitude of j 2j such that it gets slower as j 2j is closer to 0.
Regular grammar can describe a set of strings by a
collection of rules in the following patters: A ! c and A !
cB
(1) (2) (3)
In the most cases, fuzzy sets represent linguistic expressions
that intrinsically contain fuzziness such as ’tall’ on height
and ’low’ on leftover stipend
Definition. A fuzzy subset of a set U is defined by means of a membership function The set U is so-called the universal set. In the above two examples, linguistic terms ’tall’ and ’low’ correspond to fuzzy sets defined over appropriate universal sets such as ’height’ (i.e. a set (interval) of real numbers representing human height, e.g. [100; 220] in centimeters) and ’leftover stipend’ (e.g. [0; 100] in USD). In case of a crisp set, the range of the membership function becomes f0; 1g instead of [0; 1].
Usually, fuzzy sets are defined in simple canonical shapes such as triangles and trapezoids (see fig. 1 as an example of three trapezoidal fuzzy sets). In this simplicity, you may easily see the elasticity of fuzzy sets such that every crisp (i.e. non-fuzzy) interval has only one fuzzy set i.e. (x 2 U ) > 0 and (x) = 1 (i.e. the complete membership), and every fuzzy interval has more than one fuzzy set i.e. (x) > 0 and (x) < 1 for all within that interval (i.e. the partial memberships). Further, a fuzzy partition is often considered for the sake of completeness in computational models. Definition. A fuzzy partition of a set U is a set of normal (i.e. at least one element x 2 U s.t. (x) = 1) fuzzy sets of U such that
X i(x) = 1 8x 2 U
i
Fuzzy sets may be defined subjectively, unlike probability distributions. Appropriate fuzzy partitions with simple canonical shapes as shown in fig. 1 are often used in many cases. They are also dynamically generated or refined by applying some machine learning methods. In such cases, simple and smooth shapes of fuzzy sets should be maintained due to their elasticity and approximation nature.
Finally, their (standard) set operations are defined as follows:
A\B(x) = min[ A(x); B(x)] A[B(x) = max[ A(x); B(x)] A(x) = 1 A(x) (5) (6)
Fuzzy logic is originally proposed by Zadeh as a qualitative,
simplistic method for (especially complex) system
analysis
x where all the membership functions represent those fuzzy statements (e.g. high in the above example), U and V represent their universal sets (e.g. ’temperature’ in the above example), and Rf is the fuzzy relation that represents the (fuzzy) implication a ! b.
That fuzzy relation is further specified as a result of projecting material implication (i.e. a ! b = :a _ b) such that (7) (8) Rf (x; y) = (a b)[(a V ) = ( a(x)^ b(y))_ a(x) (9) where a
U and b
V .
In fuzzy control, we only need to consider the special case3 such that
Rf (x; y) = (a
b) [ (a
;) = ( a(x) ^ b(y))
(10)
This is indeed Mamdani’s fuzzy control model when
selecting a(x) ^ b(y) = min[ a(x); b(y)]
When multiple fuzzy implications (aka fuzzy IF-THEN rules) exist in the system, we need to disjunctively combine all the results, i.e. partial truth such that c = c1 _ : : : _ cn, where c1 i n is a fuzzy set representing the result for the 3System control cannot specify outputs for complements of inputs, i.e. a ; = ;. i-th fuzzy implication and c is the one for all results combined. In case of fuzzy control, c represents all possible outputs with associated partial truth values. In order to determine a single output, we need to select one output such that c( V ) ! y (2 V ) (so-called defuzzification). Centerof-Gravity (CoG) method is proposed in Mamdani’s model (see fig. 2).
y =
R c(y) y dy
R c(y) dy
Takagi-Sugeno fuzzy control model better integrates
fuzzy implications and defuzzification as a model-free
regression
Pi ai (x) fi(x)
Pi ai (x) (11) (12)
In discrete problem domains such as classification, we need to identify a class as a result of disjunctively combining all those result fuzzy sets ci. Since their membership functions are all constants (i.e. ci (y) = zi 2 [0; 1] s.t. zi = ai (x) from fuzzy implication ai ! bi), the defuzzification is achieved simply as a result of the disjunctive combination with max[ ] in order to select the class label. This is corresponding to the definition of fuzzy classifier such that C = ARGMAXi[ ai (x)] (13) where C is a class label associated with bi from fuzzy implication ai ! bi, as well as its result ci .
Three experimental filters are presented along with brief studies on their performance for the following specific contexts: narrowing down results, product specification and tutorial level classification. The experimental setting is presented first together with some clear distinction from other similar works.
In general, we consider simplicity as the core of development. In particular, the following setting is followed in the development of experimental filters.
Add-on Filters. Given all possible bias on intentions and interpretations, we focus on development of personalized add-on filters on web browsers. Such filters are very likely implemented as extensions and other forms of modules according to architectural specifications of web browsers as well as application programming interfaces (APIs). Fuzzy Sets and Logic are used as the technical framework of those filters and are easily implemented in any forms of development environment, application framework and programming language. The input of each filter is a list of web pages, most likely that of URLs, generated as a result of using a web search engine such as Google and Bing. The filter then accesses to texts from that list. The output is a modified list of those web pages, e.g. altered orders, selective lists and grouped lists.
In doing so, users can easily switch back and forth
between the ordinary and this filtered search results. In
addition, the inputs, i.e. keywords, remain the same in both
options. This is different from other works that utilize fuzzy
sets and logic in a similar manner. For instance, Choi’s
work
Recent search engines such as Google and Bing keep track of search results for various personalization and customization purpose. They are implemented as a part of server (i.e. search engine) functionalities. In contrast, ours are implemented as extensions of web browsers, thus are served as additional personalization.
Context Dependency. Each user has one’s own intention and bias in many different situations and none are likely identical to the others. In other words, it is ideal (i.e. the simplest) to facilitate a collection of add-on filters that cater such different situations with various intentions and biases.
While many works in intelligent systems tend to handle
context dependencies by adaptive capacity on the server, this
causes substantial overheads. Anari et. al. approach to
context dependencies by incorporating capacities of adaptive
behaviors and generalization (i.e. capacity of fuzzy sets and
logic) directly in the page ranking method
Linguistic Keyword Processing. Fuzzy sets and logic are well incorporated with the standard statistical natural language processing such that simple features are extracted from texts in order to apply various methods of machine learning and reasoning. Such simple features may include word frequencies and word appearances as the core. We then consider other variations within those features such as those on words that are linguistically related, e.g. synonyms, antonyms, acronyms, etc. those on words with simply conjugation processing, more generally processing morphological structures. those on a sequence of n words, i.e. n-grams.
The most significant advantages of such simple features are with regard to text stream processing. Texts are parsed only once (aka one-pass) in order to yield real-time responses. Morphological structures are mostly handled by regular grammars (expressions), and those linguistically related features demand lexicons such as thesauri. Fortunately, those are feasible within the text stream processing framework. Conventional syntactic analysis is unlikely feasible within this framework; however, stochastic and probabilistic analysis on n-grams (e.g. Markov process) and simple parsing with regular grammar may often compensate for this shortcoming.
It is commonly known that the web search inputs, i.e. keywords, are short and simple–consisting only of a few keywords. As a consequence, a canonical structure such as a pair of an adjective and a noun can be expected. This very well fits within the frame work of fuzzy sets and logic such that the adjective (a word or a phrase) corresponds to a fuzzy subset on the universal set and the noun (a word or a phrase) corresponds to that universal set. The elements in that universal set are one of those simple linguistic features and the fuzzy set is generated accordingly on those.
Prototype. All the experimental filters presented in this paper are required to be rigorously prototyped. The web search results are indeed extracted from Google and Bing for specific queries, i.e. lists of keywords. The standard models of fuzzy sets and logic are deployed, e.g. the standard fuzzy set operations and Mamdani’s fuzzy control model, for implementation advantages such as simplicity and available tools. As a trade-off, performance studies became very limited at this time–i.e. a continuing work.
This experimental filter considers narrowing down and reordering search results from a web search engine about favorite music. The intention is exploration of relevant information, thus is broad and general. More technical details are as follows: Queries. For this experiment, we only consider ”good reggae songs.” Features. The universal set is the normalized frequency f(w2t^d) f = f(w2t) f(w2t^i) of affirmative words in a text t, e.g. ’good’, ’favorite’, ’love’, etc. Function f (w) indicates the frequency of word w with a specified membership (e.g. t, t ^ d and t ^ i). A thesaurus d is used in order to identify a set of words and their conjugations. We remove meaningless words such as prepositions and pronouns and they are maintained in the ignored word list i.
Fuzzy model. A fuzzy classifier consisting of three fuzzy sets in a fuzzy partition similar to those in fig. 1: high(f (t)), medium(f (t)) and low(f (t)).
Output. (1) a class of the word frequency as a fuzzy degree of significance, and (2) a defuzzification of those three membership functions as the degree in order to determine the rank.
A small and simple performance evaluation was conducted as follows: Subjects to evaluation. Significance labels generated by the fuzzy classifier.
Examinee(s). One person who is familiar with reggae songs. Procedure. Several web pages (texts) that are randomly selected from the filtered results are presented to the examinee and ask the one to put one of those three labels (’low’, ’medium’ and ’high’) in order to indicate significance. Results. Compiled as a confusion matrix (see table 1) where H indicates the human examinee and M indicates this add-on filter.
Despite its very simple linguistic feature, i.e. the normalized word frequency of single word, we noticed some improvements. Two out of three misclassification cases are classified in adjacent classes: ’high’ where it should be ’medium’. One case is completely off; however, this was the web page containing a song list and hardly contained affirmative words.
Table 2 indicates the results of the top 5 from Bing search. Two pages are off, but both are song lists and hardly contain affirmative words. Needless to say, more extensive studies are necessary. Nevertheless, this small performance study positively suggested further study.
This experimental filter anticipates to enhance product search results. The key idea is that a certain specification is accounted to significance of products appeared in the search results. Such a specification is automatically identified as a result of mapping a set of key words to some fuzzy model. The technical details of this filter follows: Queries. For this experiment, we only consider ”energy efficient light bulbs.” Features. The universal set is the efficiency e(b) = wl((bb)) 2 [5; 100], where l(b) is the lumen and w(b) is #watts of a light bulb b. Product specification such as l(b) and e(b) are obtained from Google’s product search results by parsing XML attributes and keywords.
Fuzzy model. A single fuzzy set representing ’energy efficiency’ such that
8 0 (e(b) 2 [5; 100]) = < e(b3)5 15 if e(b) 2 (15; 50) : 1 if e(b) 2 [50; 100] (14) This is determined based on the official chart of Energy Federation Incorporated (EFI). Output. Reordered list of products according to the membership degree of (e(b)).
Search engine. Google Shopping (product search service).
A qualitative performance study on this filter is conducted as follows: Subjects to evaluation. Quality of product search results. Examinee(s). A few people who are in need of light bulbs. Procedure. Obtain testimonials by presenting both product lists: filtered and not-filtered.
Results. A collection of testimonies are listed below. See fig. 3&4 to compare top 8 products (i.e. energy efficient light bulbs). Five bulbs in the filtered results also appear in the not-filtered one. Among those, only one (the top bulb) appear in the same rank. Three new bulbs appear in the filtered list.
Here is the sample testimonies: 1. ”I think [the filtered result] is better it sticks more to sorting the wattage in order, making the energy efficiency stand out more if people are looking to cut costs by reducing wattage. This is not taking things like price or actual lumenage of the bulb into effect (if people are looking for a brighter, yet energy efficient bulb, which might actually be a higher wattage).” 2. ”I’d have to go with [the filtered result] mainly because it ranked the Satco Halogen among the lowest. The Satco Halogen uses the most energy out of all the bulbs with the least gain of lumen. 57 watts for 1100 lumens vs 13 watts for 900 lumens.”
This filter, despite its simplicity in uncertainty management, turned out to be better effective than we expected. The current trends on ecology stimulated the bulb market so that manufacturers release new types of bulbs and users (i.e. consumers) are not yet familiar with those new types. More comprehensive implementation of such a filter is likely significant from marketing aspects and is certainly feasible from technical aspects. This experimental filter classifies tutorial sites into three classes: ’beginner’, ’intermediate’ and ’advanced’. Only a set of few general keywords are taken into account for this classification. In doing so, we maintain a high degree of generality (i.e. domain independence). Each of such keywords are associated with appropriate membership degrees per class. Mamdani’s model is deployed for this classification as a result of defining singleton fuzzy sets over a shared universal set representing those classes.
(cjrubyjpython)(tutorials?jguides?) Features. We only use the following keywords and their conjugation (handled by regular expressions): intro(aj : : : jz) , novice, intermediate, advanc(aj : : : jz) , experts?. We also use their frequencies: fi(t) for intro(aj : : : jz) , fn(t) for novice, fm(t) for intermediate, fa(t) for advanc(aj : : : jz) and fe(t) for experts?.
Fuzzy model. The following IF-THEN rules and fuzzy sets are defined: we consider: 1. h(fi(t)) ! cih = f1:0=0g 2. h(fn(t)) ! chn = f1:0=0:25g 3. h(fm(t)) ! chm = f1:0=0:5g 4. h(fa(t)) ! cah = f1:0=0:75g 5. h(fe(t)) ! ceh = f1:0=1g 6. m(fi(t)) ! cim = f0:5=0g 7. m(fn(t)) ! cnm = f0:5=0:25g 8. m(fm(t)) ! cmm = f0:5=0:5g
Fig. 5 and 6 show a search result and a classified result of Google with query ”python tutorial.” As you may notice, there are a few pages in unintentional context, i.e. Pokemon. This is a trade off with generality, that is caused due to a shallow linguistic analysis such as word frequencies of only a few keywords. Nevertheless, we received several positive feedbacks about this filter that mainly commends such a classification offers more efficient information browsing. (15) (16)
A preliminary study on page ranking refinement using fuzzy sets and logic is presented. Three simply experimental filters are presented in order to demonstrate their effectiveness. Their performance studies, despite their rough and mostly qualitative contents, positively suggest continuing works. In experimental setting, clear difference from similar works is discussed.
Among many future works, we will first conduct more extensive performance studies and prepare some development frameworks for popular web browsers such as Fire Fox and Chrome. Sets and Logic at EWU at the end of Fall 2010. The duration of this project was two weeks. The best three projects are presented as experimental filters in this paper and those students are recognized as its co-authors.