Back in April, I mentioned that Microsoft will be co-launching with Interamerican University of Puerto Rico, Metropolitan Campus the Microsoft Innovation Center (MIC) of Puerto Rico.
Well, tomorrow is the official inauguration. the university generously has provided me with lab and office space to start an interesting research project within the MIC building. These are exciting news. I cannot comment much about the project, except to say that it is at the interface of search engines, social networks, and information security.
It looks like I will have my hands full between workig at two universities, blogging, and doing consulting work.
I normally do not put online my lecture notes (ppt, pdf, videos). However, there are two public conferences that event organizers taped. Both last over 1 hour and are in Spanish, but with slides in English. Here are the links. The quality of the videos is so-so.
Since the videos were made available few months later after the events, these are not properly dated. I have included below the actual date of the events. If you don’t know Spanish, you are out of luck.
1. Understanding Search Engines (Entendiendo a los Buscadores), University of Puerto Rico, Bayamon, 4-23-2008
http://video.google.com/videoplay?docid=-653964730907023811
This one last for about two hours. The audience consisted of grad students and researchers. Unfortunately, the video has an audio-visual mismatch of about one slide. If you can coupe with this, I hope you like it.
2. Demystifying LSI (Desmitificando LSI)- OJOBuscador Congress, Madrid, Spain, 3-09-2007.
http://www.ojotube.com/videos/congreso-ojobuscador-2007-ponencia-desmitificando-lsi-de-dr-e-garcia/
This one last for over one hour. Since it was for a non-scientific audience (most Spanish SEOs) I tried to talk very slow.
Soon or later CS students, in particularly those in IR, will need to deal with similarity matrices.
In simple terms, any matrix M that exhibits the following five characteristics is a similarity matrix.
Squaredness = M must have the same number of rows and columns.
Non-Negativity = all elements of M must be real, non-negative numbers.
Boundedness = all elements of M must adopt values between 0 and 1.
Reflexivity = all diagonal elements of M (i.e. from left to bottom) must be filled with 1.
Symmetry = all ij elements must be identical to all ji elements.
A matrix that fails to exhibit any of these characteristics is not a similarity matrix.
Accordingly, some matrices found in the literature on LSI and whose elements have been referred to as similarities are not so since the corresponding matrix does not conform to the above definition.
Note. This information will help those that took the IR Quiz on Matrices to realize how well they did.
The current issue of IRW should reach subscribers inbox during the day or at the latest, tomorrow.
In this issue:
I’m putting together a piece on several local term weight models. It should be ready in few weeks.
It is a research paper that can be used as a tutorial. It describes a systematic approach for the derivation of any kind of local term weighting model. Students can use it as a recipe for proposing their own candidate models.
The article touches on some aspects of the problem of trusting models that lack of attenuation. Here is one snippet on the subject:
<last nail in KD coffin style=”intensity:100%;”>
“It should be stressed that term repetition not necessarily satisfies users’ queries nor is evidence of:
Pertinence (P); e.g., that a term repeated x times is x times more pertinent to the document.
Aboutness (A); e.g., that the document is x times more about the term.
Importance (I); i.e., that there is a term-document relationship of pertinence and aboutness.
Relevance (R);i..e., that a document repeating a term x times is x times more relevant.
Accordingly, fulfilling such ‘PAIR criteria’ on a regular basis is hard to accomplish with any model that lacks of attenuation.”
</last nail in KD coffin>
What is the (^H^H^H) best definition for data mining and database? It depends on who you ask and in which context.
According to Section 126 of the USA Patriot Act,
(1) DATA-MINING- The term `data-mining’ means a query or search or other analysis of one or more electronic databases, where
(A) at least one of the databases was obtained from or remains under the control of a non-Federal entity, or the information was acquired initially by another department or agency of the Federal Government for purposes other than intelligence or law enforcement;
(B) the search does not use personal identifiers of a specific individual or does not utilize inputs that appear on their face to identify or be associated with a specified individual to acquire information; and
(C) a department or agency of the Federal Government is conducting the query or search or other analysis to find a pattern indicating terrorist or other criminal activity.
(2) DATABASE- The term `database’ does not include telephone directories, information publicly available via the Internet or available by any other means to any member of the public, any databases maintained, operated, or controlled by a State, local, or tribal government (such as a State motor vehicle database), or databases of judicial and administrative opinions.
Asking the government or a KDDM researcher the question and using LSI to clusters results for the above question can be a futile exercise.
It is like asking President Obama or Vice President Cheney to agree on: “What is Torture?”
Today, a reader (name removed to protect confidentiality) asked me:
My name is **** ****. I working as a junior research fellow in a project in India. I red the SVD techniques from the web page http://www.miislita.com/information-retrieval-tutorial/svd-lsi-tutorial-3-full-svd.html#right-eigenvectors. I found it is quite satisfactory for me. Now I can understand how SVD works. But I have a query as follows.
query:
As mentioned in this tutorial that we have arrange these eigen-values in descending order. Cold you please tell me if I put these values in ascending order or arbitrary what will be wrong with the SVD.
Looking forward your early kind response.
Thanking you.
With best regards.
*******
My answer follows.
It depends on what you are trying to address.
SVD is used to identify singular values interpreted as dimensions. When used as a dimensionality reduction technique, the largest N singular values are normally retained and thus retaining the smaller singular values is meaningless. The largest singular values capture most of the information of the original data set and is therefore a noise minimization approach.
If the retention criterion used is reversed (smaller singular values are retained) this implies retaining the more noisy dimensions such that the reconstructed matrix will be a matrix of the hidden (latent) data noise. This is a noise maximization approach.
If the retention criterion is based on a random selection, the resultant reconstructed matrix might be one representing a data structure with randomized noise.
These scenarios depend on the original data under examination.
In Image Compression, these approaches have been already explored. If the goal is a stability study and not just SVD dimensionality reduction, “the ratio between the highest singular value and the lowest singular value of the Jacobian matrix quantifies the spread of the Jacobian’s singular values, which in practice, reflects the extent of the solution’s instability with respect to small changes in the observation” (Horesh’s Thesis )
Having said all that, we should not render noise in a data set as something that must be discarded at all cost.
This is intimate linked with the so-called Inverse Problem. Incorporating noise and a priori SVD information can provide the complete information in a linear sense. Qianqian Fang has a beautiful PPT presentation “Look Closer to Inverse Problem” on the subject. If you want to visualize the MATRIX Problem, this presentation is for you.
I’m thinking in putting together a tutorial on the Singular Value Expansion algorithm (SVE), if I ever find the time.
I hope this helps.
According to a report from the British Computer Society (BCS) covering a Security Panel Strategic Forum, “ethical hacking” is an oxymoron.
The report highligths do’s and don’t when it comes to defining terms like “hacker”, “ethical hacking”, “penetration tester”, “white/black hats”, and derivatives terms. These labels are frequently used in the IT industry. The report also underscores which terms should not be used by schools offering IT courses.
The problem with defining and redefining such labels is that there will always be others disagreeing with/circumventing said definitions.
For instance, in the December 1986 issue of MicroTimes, Bob Bickford wrote:
“A Hacker is any person who derives joy from discovering ways to circumvent limitations.”
If we accept this definition then a person that doesn’t derive any joy from discovering ways to circumvent limitations is not a hacker. Similarly a spouse cheater, an SEO, a spammer, a politician, a mobster, or a kid trying to get some candies from mom is a hacker.
I am taking this extreme, off-topic interpretation to illustrate the problem of semantics when it comes to defining things.
Whether you agree or disagree partial or totally with the report, it is a good read. For sure it will be a good piece for students planning to take my AIRWeb graduate course.
According to Ben Edelman, Google is engaged in a conversion-inflation syndyication fraud.
These tactics are nothing new.
In the featuring article of the November 2008 issue of IR Watch, “Fraudulent Web Analytics – Engineering the Fraud“, we covered how in-the-middle mechanisms are part of Web Analytic Frauds and Business Collusion Schemes.
As in man-in-the-middle attacks found in information security settings, the underlying goal is the same: the crafting of deceiving intermediary events.
Expect soon a pr damage control campaign from the useful idiots/moles.
What is next? A class action lawsuit?
Still, I have a little taste of satisfaction in my mouth when crooks disguised as advertisers/search marketers are gamed. Gaming the gamers: Life ironies!
Explain and give example for the following matrices used in IR:
1. Term-document occurrence matrix.
2. Term-term cooccurrence matrix.
3. Term-term correlation matrix.
4. Term-term similarity matrix.
5. Term-term coweights matrix.
6. Term-term distance matrix (*).
7. Covariance matrix (*).
(*) PS. I forgot to list these other matices.
The current of issue of IRW should reach subscribers inbox tomorrow.
In this issue:
Featuring article: RIA Vulnerabilities
This issue of the newsletter discusses how hackers might be exploiting Web vulnerabilities found in Rich Internet Applications (RIAs). As mentioned in our previous issue, some RIAs are based on Adobe’s technologies like Flash, Flex, or AIR. Some are designed to be run online or offline. Their rising popularity has attracted developers and marketers, and -as expected- hackers and spammers.
QA: Excel Vector Normalization: How do I convert a row vector into a unit vector?
Who is Who in IR: C.J. van Rijsbergen
Top CS Departments: Polytechnic University of Puerto Rico
Historical Notes: ENIAC Computer
Outstanding Graduate Theses
Calls and Events
Research Blogs
and more…
Today I feel like giving a piece of advise to spammers, so this will force raising the bar in the “we versus them” in the Spam War. Think of this as a love-hate relationship.
C’mon spammers, I know you can do better. Don’t make our IR life easy at neutralizing your tactics. He, He.
At the recent AIRWeb Workshops, Brian Davison presented the paper Looking into the Past to Better Classify Web Spam, which received high reviews from referees and the audience.
Wannabe spammers, if you are really committed to spamdexing, at least know the how-tos. Don’t leave a temporal fingerprint of your web presence. Try this:
1. Prevent online resources from caching your web pages, like the Wayback Machine and commercial search engines.
2. Use No-Cache and No-Archive.
3. Switch hosts whenever you can.
4. Constantly mutate your link structure.
5. Don’t profile yourself with easy to detect/predictable honeypots, link swapping, strongly-connected component structures, etc.
Why giving these advices? Check current AIRWeb “gems”.
This afternoon, Microsoft in partnership with The Interamerican University of Puerto Rico, Metropolitan Campus (Inter-Metro) will announce that they are officially co-launching the Microsoft Innovation Center (MIC) of Puerto Rico.
This will be the first MIC in the region. A two stores building has been abilitated within the Inter-Metro campus for this project. As member of the MIC steering committee, I have been invited to the presentation by President, Manuel J. Fernos.
They have also provided me with office and lab space in the MIC building to put together the Internet Business Development Center (IBDC). The objectives of the MIC is the development and commercialization of ecommerce-related software tools. Emphasis will be given to egovernment and ebusiness solutions.
It looks like I will split my schedules between being the IBDC principal investigator, MIC meetings, doing research at Inter-Metro, teaching at PUPR, and writing IRWs. These are exciting news. Let see how things go, especially with the other great news that PUPR’s ECE&CS department has been accredited by NSA as a CAE.
Here are the proceeding papers of AIRWeb 2009, available at http://airweb.cse.lehigh.edu/2009/proceedings.html
OK, SEOs, Spammers, and Hackers: start your engines and let the fun begin.
If you are a PUPR graduate student and are planning to take my AIR course, it might be a good idea to start browsing through these “gems”. Check also previous proceedings of AIRWeb.
The Potential for Research and Development in Adversarial Information Retrieval — slides
Web Spam Challenges: Looking Backward and Forward — slides
Looking into the Past to Better — slides
Classify Web Spam
A Study of Link Farm Distribution — slides
and Evolution Using a Time Series of Web Snapshots
Web Spam Filtering in Internet — slides
Archives
Dávid Siklósi
Web Spam Identification — slides
Through Language Model Analysis
An Empirical Study on — slides
Selective Sampling in Active Learning for Splog Detection
Tomohiro Fukuhara
Linked Latent Dirichlet Allocation — slides
in Web Spam Filtering
and András Benczúr
— slides
Tag Spam Creates Large Non- — slides
Giant Connected Components
Nullification Test Collections
— slides
for Web Spam and SEO
Web Spam Challenge Proposal for — slides
Filtering in Archives
Dávid Siklósi
George M. Zinkhan III, from Terry College of Business at the University of Georgia allegedly went into a killing rampage, killing his ex-wife and two others, and hurting two.
According to his university page (accessible at the time of writing), Zinkhan is a Coca-Cola Company Professor Department of Marketing and Distribution. Zinkhan is well known in the academic marketing research circles, having served as editor of the JOURNAL OF THE ACADEMY OF MARKETING SCIENCE.
His 40-page CV reveals he conducted extensive research on Marketing and Net Advertising.
In 2008 he was part of an American Marketing Association committee that redefined marketing. The new definition reads:
“Marketing is the activity, set of institutions, and processes for creating, communicating, delivering, and exchanging offerings that have value for customers, clients, partners, and society at large.”
According to the AMA committee,
“Marketing is no longer a function — it is an educational process.”.
Zinkhan published extensively with Yue Pan, associate professor of marketing, University of Dayton. He published on the concept of Netvertising (”Netvertising Characteristics, Opportunities and Challenges: A Research Agenda,” International Journal of Internet Marketing & Advertising, 1(3), 283-299.). According to their abstract:
“Netvertising, or “advertising on the internet”, is attracting much attention from advertising and marketing researchers. However, surprisingly little is known about its new features as compared to other forms of advertising and the implications of the new medium for advertisers. Here, we focus on the following issues: the opportunities and challenges associated with internet advertising; the differences of netvertising from other forms of communication; banner ads – the most popular type of netvertising. Applying this framing perspective, we propose a research agenda for the study of netvertising.”
Netvertising is something search marketers do using different out-of-the-thin-air theories/naming conventions.
Read more about the Netvertising Image Communication Model (NICM)
That was then. Today Zinkhan’s name is associated with a Negative Image on the Net. It will be a matter of time before others will dissassociate themselves with such an image. Life ironies!
He didn’t seem to fit the academic stereotype.
Unfortunately as in any profession, some people cannot coupe with their personal misfortunes and end up doing bad things.
According to a McAfee report,
Until now, spam’s impact has been measured in time, money, and aggravation. It turns out there is a massive environmental impact as well. McAfee recently commissioned climate-change consultant ICF International and spam expert Richi Jennings to calculate the environmental impact of spam. The results that came back were startling: The energy consumed in transmitting and deleting spam is equivalent to the electricity used in 2.4 million U.S. homes, with greenhouse gas (GHG) emissions equivalent to 3.1 million passenger cars(http://resources.mcafee.com/content/NACarbonFootprintSpam)
I first learned about these findings through ABC. Essentially,
Anything powered by electricity also emits greenshouse gases. McAfee researchers say each junk e-mail emits 0.3 grams of the greenhouse gas carbon dioxide (CO2). That may not sound like much, but when you consider the volume of global annual spam, it all adds up. (http://abcnews.go.com/Technology/GlobalWarming/story?id=7343518&page=1).
Following that reasoning, spamdexing search engines and any adversarial information retrieval (AIR) practice is also an insult to injury, so as too many things that comes to my mind.
I will tell that to students of my Fall 2009 AIRWeb Course.
Humm, shocking: AIR vs. Environment.
I never thought about such an obvious connection. 
Recently a known SEO (name reserved) inquired me about some aspects of IDF (Inverse Document Frequency). Below are three of his questions.
I am partially reproducing/editing my responses, so it might help other SEOs with similar questions.
Questions 1 and 3 are related so I will answer both now. After that, I will answer question 2.
1) Why is a log function used for calculating IDF?
3) Would it be accurate to describe IDF as “the ratio of documents in a collection to documents in that collection with a given term”? I’m guessing your answer would be, IDF is the [LOG of " the ratio of documents in a collection to documents in that collection with a given term"]? Which brings us back to question, I guess? heheThese are recurrent questions students asked me before. The reason for using logs is due to two assumptions frequently made in most IR models; i.e.
I. that scoring functions are additive.
II. that terms are independent.While in some models II might not be present, both (I and II) play well with logs since these also are additive.
These functions and why the use of logs is explained in the recent RSJ-PM Tutorial http://www.miislita.com/information-retrieval-tutorial/information-retrieval-probabilistic-model-tutorial.pdf
Document Frequency (DF) is defined as d/D, where d is number of documents containing a given term and D is the size of the collection of documents. If we take logs we obtain log(d/D).
But since often D > d the log of d/D, that is log(d/D) gives a negative value. To get rid off the negative sign, we simply invert the ratio inside the log expression. Essentially we are compressing the scale of values so that very large or very small quantities are smoothly compared. Now log(D/d) is conveniently called Inverse Document Frequency.
Now going back to d/D, this is a probability estimate p that a given event has occurred. Let the presence of a term in a document be that event. If terms are independent, it must follows that for any two events, A and B
p(AB) = p(A)p(B).
Taking logs we can write
log[p(AB)] = log[p(A)]+ log[p(B)]
It is easy to show that for two terms
log(d12/D) = log(d1/D) + log(d2/D)
Inverting and using the definition of IDF we end up with
IDF12 = IDF1 + IDF2
validating assumption I; that IDF as a scoring function is additive.
That is the IDF of a two term query is the sum of individual IDF values. However, this is only valid if terms are independent from one another. If terms are not independent we would have two possibilities; i.e.,
p(AB) > p(A) + p(B)
or
p(AB) < p(A) + p(B)
and we cannot say that the IDF of a two term query (e.g, a phrase) is the sum of individual IDF values. Assuming the contrary as many SEOs think in order to promote some dumb keyword research tools is plain snakeoil.
2) What do you mean by ‘discriminatory power’ in the phrase “IDF is a measure of the discriminatory power of a term in a
collection.”This is legacy idea from Robertson and Sparck Jones. The discriminatory power of a term (aka term specificity) implies that terms too frequently used are not good discriminators between documents. If a a term is used in too many documents its use to discriminate between documents is poor. By contrast, rare terms are assumed to be good discriminators since they appear in few documents.
The RSJ-PM Tutorial mentioned above was written to kill for good some misconceptions regarding IDF. In it we explain why IDF is considered by Robertson and Jones a particular RSJ weight in the absence of relevance information.
In a nutshell, IDF is a collection wide estimate and as such the information on whether documents containing the terms being queried are relevant to these is unknown. Similarly, the information on whether documents not containing the query terms are relevant or not is unknown and often remains unscrambled when we just look at the d/D and d/(D – d) collection-wide ratios. All we can say is that relevant documents might have a higher probability of containing query terms in comparison with other documents from the collection as a whole. But we could make such assertion without resourcing to IDF as well.
In the case of Web documents, often these are about multiple topics. Many documents aggregate content from dissimilar sources (news headlines, rss, blogs, etc) and said document content might change in time. The mere mention of a term (regardless of repetition) is not a proof of its relevancy or of its importance with respect to the topics discussed in a document.
Thus, the idea that we can assess if terms are relevant to a document by simply comparing IDF values is missing the whole point and defeats the purpose for which the RSJ-PM model and many of its variants (e.g., BM25) were developed.
I hope this helps to clear up some SEO misconceptions on the topic.
If you search this blog (IRThoughts) for LSI or visit its Latent Semantic Indexing category you will find many posts wherein SEO LSI Myths are debunked. Prior to this wordpress blog I used to maintain a personal blog wherein SEO myths regarding LSI were also debunked.
Over the years, many realized they were taken by the usual agents of misinformation, at least when it comes to “SEO LSI” and “LSI-Friendly” documents.
Recently, I found traffic coming from a blog discussion about a video (http://www.stomperblog.com/warning-advanced-seo-technique-does-not-work/) wherein LSI in relation with Google is debunked.
The video also discusses one flavor of LSI; i.e. one wherein weights are tf-IDF weights. This flavor does not incorporate relevance information or entropy information, like other LSI variants.
The video does a good job at debunking LSI Myths. However, it has at least a factually incorrect argument in relation to how the SVD algorithm works.
The video gives an example implying that SVD works by reducing a large set of words to a few words, such that, for example thousand of words are reduced to, let say 300 words. This is incorrect and certainly is not a trivial flaw.
SVD does not work by reducing a vocabulary, but by reducing dimensions, and there are as many dimensions as singular values. This is why is called a dimensionality-reduction and not a vocabulary-reduction algorithm. I should stress that an LSI Space is not like a Term Space wherein each term is a dimension such that there is a 1:1 correspondence.
In LSI, the SVD algorithm is used to reduce the dimensions of a matrix; the number of singular values of the matrix.
For instance in our SVD and LSI Tutorial series at
we present an LSI problem example consisting of many words and few initial dimensions such that for the initial matrix
#words >> # initial dimensions
more specific, we used 11 words and 3 dimensions
After truncation, we ended up with 11 words and 2 dimensions.
Other than this, the video is fun to watch, but ended up as an introductory promotion for another SEO proposal.
PS.
After reviewing several times the video, unfortunately I found the video has another incorrect argumentation.
When objecting to that Google might not use LSI, an argument is made in the sense that LSI has to return same results when word variants are used like plurals and tenses. This might be the case if stemming is heavily used in an LSI implementation, but the use of stemming is not a requirement for implementing LSI at all.
When stemming is not implemented, for sure the SVD reduction will return different results since these will be entered in the original term-doc matrix to be undergo decomposition as different tokens.
The video also misses what the power of LSI comes from: higher order co-occurrence connectivity path hidden (latent) in the original matrix. Whether terms have to be synonyms, related terms, or even of non-derivative forms is not a requirement for observing these hidden paths in LSI.
Terms no need to be related terms either to end up clustered with LSI. It is the hidden co-occurrence patterns what is behind the clustering. For example, in our SVD and LSI tutorial above, we intentionally used stopwords and zero synonyms/related terms and these ended-up in their corresponding clusters, without being necessarily semantically related. This simple example shows that in LSI the SVD algorithm produces an output based on crushing numbers, not on making sense out of meaning or intelligence, and contradicts the generalized opinion that LSI works at the level of meaning.
I have to conclude that while the video is intended to debunk LSI SEO myths (a noble effort), it uses incorrect arguments and hearsays lines from around the Web. Debunking hearsay with more hearsay: What a shame.
The current issue of IRW should be in subscribers inbox today or tomorrow, at the latest.
In this issue of the newsletter we cover Rich Internet Applications (RIAs) and how these can be used for Web/Data Mining. A RIA is a browser-independent application that can be compiled and run from the desktop.
In this issue:
Featuring article: Web & Data Mining with RIAs
QA: Recommended RIAs
Who is Who in IR: Bruce Croft
Top CS Departments: UMass, Amherst
Historical Notes: John von Neumann and Bugs
Outstanding Graduate Theses
Calls and Events
Research Blogs
and more…
IRW currently reaches a fine audience of university and government researchers and their labs. If you are a graduate student or IR practitioner and want to be known within this exclusive circle, submit a short article (2, 3 pages, IRW format, free from marketing and sale pitches) for its consideration
source: http://www.cs.princeton.edu/~blei/papers/BleiNgJordan2003.pdf
There is a kind of buzz about Probabilistic Latent Semantics Indexing, so this post goes.
From VSM to LSI
Prior to 1988 the prevalent IR model was Salton’s Vector Space Model (VSM). This model treats documents and queries as vectors in a multidimensional space. In this space a query is treated just as another document. In this term space, it is not possible to assign a position to terms simply because these are the dimensions of the space. Coordinate values assigned to document and query vectors are given by terms weights computed using a particular weighting scheme.
VSM and its many variants are based on matching query terms to terms found in documents. These models assume term independence. However, we know this assumption is not necessarily correct since terms can be dependent via (a) synonymity and (b) polysemy.
In 1988, Dumais and co-workers at Bellcore (now Telcordia) published two papers in which they applied Golub and Kahan’s 1965 SVD algorithm to “documents” exhibiting (a) and (b) and called that Latent Semantic Indexing (LSI).
LSI became an improvement over the simplistic point of view of term matching, accounting for term dependencies. The “documents” were not HTML Web documents (there were no Web documents back then), but just abstracts and memos from specific knowledge domains (HCI, scientific, med). As expected these consisted of synonyms and related terms used in these domains. Thus, clusters of these were obtained.
It was immediately claimed that LSI could be used to model aspects of basic linguistic -like synonymy and polysemy- and how the human mind associates words to concepts and concepts to meaning.
Moving twenty years forward, SEOs misread such outdated research and the synonym-stuffing myth was born.
There is now a crew of SEOs claiming that they can design documents “LSI-friendly” by making these rich in synonyms and related terms. We have demonstrated via our SVD and LSI tutorial series why this is not possible. These marketers are simply inventing out of thin air LSI Myths in order to market better whatever they sell or promote (often their own image as “experts”). Same goes for those that claim “PLSI-SEO” strategies.
Research findings suggest that what makes LSI works is first and higher-order co-occurrence paths hidden in the term-term LSI matrix. These paths are responsible for how and why of the redistribution of term weights in a truncated term-document matrix. Altering terms (even a single term) of this matrix provokes a redistribution of term weights across the entire matrix, whose outcome cannot be predicted. This is why “LSI-friendly” documents is plain SEO Snakeoil. Again, the same goes for those that claim “PLSI-SEO” strategies. Keep reading.
Enters Probabilistic Latent Semantic Indexing (PLSI) model
In 1998 LSI was put into question. Given a generative model of text: why adopt LSI when one could use Bayesian or maximum likelihood methods and fit the model to data?
In 1999, Thomas Hofmann presented the Probabilistic Latent Semantic Indexing (PLSI) model, also known as the Aspect Model, as an alternative to LSI. PLSI (or PLSA) models each word in a document as a sample from a mixture model. The mixture components are multinomial random variables viewed as representations of topics.
Each word is generated from a single topic, and different words in a document can be generated from different topics. In this model each document is represented as a list of mixing proportions for these mixture components. Thus, documents are reduced to a probability distribution over a set of topics, which is the expected “reduced description” associated with the document.
But there is a problem.
Enters Latent Dirichlet Allocation Model (LDA)
By 2003 Hofman’s PLSI model was put into question, this time by David Blei, Andrew Ng and Michael Jordan, who proposed that year the Latent Dirichlet Allocation Model (LDA). As noted by Blei, et al. (and quote) PLSI “is incomplete in that it provides no probabilistic model at the level of documents. In pLSI, each document is represented as a list of numbers (the mixing proportions for topics), and there is no generative probabilistic model for these numbers. “
Blei and co-workers then stated that this leads to two problems:
1. the number of parameter in the model grows linearly with the size of the corpus, which leads to serious problems with over fitting
2. it is not clear how to assign probability to a document outside of the training set.
Thus, it is not true that PLSI is the preferred model to work with in IR, as some have claimed. In addition, the model has non-trivial theoretical flaws and limitations.
In Salton Term Vector Model as in the LSI and PLSI models word order does not matter. Documents are simply considered a “bag of words”. However, common sense dictates that this is not a valid assumption since word semantics is sensitive to word ordering. This explains why searches in Google for college junior or junior college produce far different results.
To underscore the importance of word ordering consider this: applying a similarity measure like a Jaccard Coefficient computed from a term-term matrix to the above two queries produces identical results, but again the computed similarity scores are disconnected from word semantics.
Blei and co-workers have argued that if we want to consider exchangeable representations (ordering) for documents and words, we need to consider mixture models that capture the exchangeability of both words and documents. This is why they proposed their LDA model.
In LDA documents are represented as random mixtures over latent topics, and each topic is characterized by a distribution over words.
I believe we are moving toward a Unified IR Theory where Co-Occurrence, Probability and Geometry will converge. In this unified framework there is no room for the idea of term independence or of documents as mere “bags of words”. The former is IR’s Original Sin and the later is its copycat.
The image above gives me a flash back on research work I conducted in the late ’80s on sequential simplex optimization methods.
During the Fall of 2009, I will be teaching
Adversarial Information Retrieval on the Web: A Graduate Course on Web Spam and Internet Vulnerabilities
This a new one-full semester graduate course to be offered at Polytechnic University Puerto Rico. It is based on the material presented at the annual AIRWeb Workshops. KDDM graduate students are encouraged to enroll. An early announcement and preliminary syllabus is available at
http://www.miislita.com/courses/airweb-web-spam-syllabus.pdf
BTW, In November 5 of 2008 PUPR became the First Academic Institution in the Caribbean to be Certified by the Committee on National Security Systems (CNSS). Additional information is available at http://www.pupr.edu/ias.html
Their goal is to become a Center of Academic Excellence in Information Assurance Education (CAE/IAE). These are great news. Nationwide, how many universities you know that are in such an exclusive ”club”?
Here is the final list conforming the 18 International Conference of the W3C, WWW2009, of which AIRWeb2009 is a workshop.
http://www.webshine.org/2009reg.html
A lot of good stuff to please IRs, CS students, spammers/SEOs, and hackers.
In SEOs and their IDF Myths, we covered how many are mistaking the measure of term specificity known as Inverse Document Frequency (IDF).
In SEOs and their IDF Myths: Part 2, we exposed some of these folks.
In Understanding TFIDF, we wrote a rebuttal.
We are still seeing so many bloggers mistaking IDF for something that is not. We have to conclude these pseudo-teachers either are just trying to sell something or they don’t really understand what term specificity stands for. They should know that IDF is a small pixel section within the bigger picture of the Robertson-Sparck Jones Probabilistic Model for information retrieval.
Thus, we are writing a tutorial on RSJ-PM to kill for good their intentionally misleading efforts. Hopefully, the tutorial will be ready before the month ends. It will be a great way of putting to rest all the false information flying around from the usual agents of misinformation (mostly SEOs). CS students interested in knowing about the pros and cons of probability models in IR will find it useful.
I’m reading with great interest the paper
Efficient Condition Monitoring and Diagnosis Using a Case-Based Experience Sharing System, by Mobyen Uddin Ahmed, Erik Olsson, Peter Funk, Ning Xiong, and presented at the 20th International Congress and Exhibition on Condition Monitoring and Diagnostics Engineering Management, p 305-314, COMADEM 2007, Faro, Portugal,
I’m happy to read they referenced our Tutorial on Cosine Similarity Measures. Their CBR-based search system combines a tf*IDF term vector scoring scheme and ontologies.
Their abstract follows:
ABSTRACT
In a dynamic industrial environment changes occur more and more rapidly, new machines, new staff when scaling up production and reduced staff when scaling down during a recession, staff with varying experience etc. This puts a high focus on experience reuse and sharing; much experience is lost during down-scaling and tied up in knowledge transfer/teaching during up-scaling. This is recognised as very costly for industry and reduces productivity and competitiveness. Condition Monitoring and diagnostics is such an area where lack on knowledge and mistakes can have severe consequences for a company’s long term existence. Maintenance staffs, technicians and engineers also gain much experience during their every day work, often during many years, but there are rarely any good processes for experience sharing and reuse inside the organisations. In this paper we present an experience sharing system based on case-based reasoning and limited natural language processing. The system is a tool for maintenance staff and engineers and enables efficient experience collection, reuse and sharing. The implemented prototype is web-based to promote access from any location and may be local or global enabling experience sharing openly or in clusters of collaborating companies. Case based reasoning has proven to be an efficient method to identify and reuse experience if the application domain has cases. Our target application domain has these features and there are plenty of cases valuable to reuse. We have validated this in close collaboration with maintenance engineers through field studies. The prototype developed shows promising features and will be tested in real industrial environments during 2007 and 2008.
