AdWords and Generalized On-line Matching.The objective is to maximize the total revenue while respecting the daily budgets.

How does a search engine company like Google decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem.

We here introduce the notion of a tradeoff revealing LP and use it to derive an optimal algorithm achieving a competitive ratio of 1 - 1/e for this problem.

Introduction
Internet search engine companies, such as Google, Yahoo and MSN, have revolutionized notonly the use of the Internet by individuals but also the way businesses advertise to consumers.Instead of flooding consumers with unwanted ads, search engines open up the possibility of a dialogue between consumers and businesses, with consumers typing in keywords, called Ad-words by Google, that reveal what they are looking for and search engines displaying highly targeted ads relevant to the specific  query.
The AdWords market is essentially a large auction where businesses place bids for individual keywords, together with limits specifying their maximum daily budget. The search engine company earns revenue from businesses when it displays their ads in response to a relevant search query (if the user actually clicks on the ad). Indeed, most of the revenues of search engine companies are derived in this manner.

It is well known that Internet companies, such as Amazon and eBay, are able to open up new markets by tapping into the fat tails of distributions. This holds for search engine companies as well: The advertising budgets of companies and organizations follows a power law distribution, and unlike conventional advertising, search engine companies are able to cater to low budget advertisers on the fat tail of this distribution. This is partially responsible for their dramatic success.The following computational problem, which we call the Adwords problem, was posed to us by Henzinger : assign user queries to advertisers to maximize the total revenue. Observe that the task is necessarily online { when returning results of a specific  query, the search engine company needs to immediately determine what ads to display on the side. The computational problem is specified as follows: each advertiser places bids on a number of keywords and specifies a maximum daily budget. As queries arrive during the day, they must be assigned to advertisers. 
The objective is to maximize the total revenue while respecting the daily budgets.

This market dwarfs the AdSense market where the ad is based on the actual contents of the website.According to a recent New York Times article (Feb 4, 2005), the revenue accrued by Google from this market in the last three months of 2004 alone was over a billion dollars.

In this article, we present a deterministic algorithm achieving a competitive ratio of 1-1/e for this problem, under the assumption that bids are small compared to budgets. The algorithm is simple and time efficient.
No randomized algorithm can achieve a better competitive ratio, even under this assumption of small bids.

how this Ad word advertisement works for search engines and its algorithm and analysis can be generalized to the following more realistic situations while still maintaining the same competitive ratio:

•  A bidder pays only if the user clicks on his ad.

•  Advertisers have different daily budgets.

•  Instead of charging a bidder his actual bid, the search engine company charges him the next highest bid.

•  Multiple ads can appear with the results of a query.

• Advertisers enter at different times.

Previous work
The adwords problem is clearly a generalization of the online bipartite matching problem: the special case where each advertiser makes unit bids and has a unit daily budget is precisely the online matching problem. Even in this special case, the greedy algorithm achieves a competitive ratio of 1/2. The algorithm that allocates each query to a random interested advertiser does not do much better { it achieves a competitive ratio of 1/2 + O(log n/n)}.

In [KVV90], Karp, Vazirani and Vazirani gave a randomized algorithm for the online matching problem achieving a competitive ratio of 1- 1/e. Their algorithm, called RANKING, fixes a random permutation of the bidders in advance and breaks ties according to their ranking in this permutation. They further showed that no randomized online algorithm can achieve a better competitive ratio.

In another direction, Kalyanasundaram and Pruhs [KP00] considered the online b-matching problem which can be described as a special case of the adwords problem as follows: each advertiser has a daily budget of b dollars, but makes only 0/1 dollar bids on each query. Their online algorithm, called BALANCE, awards the query to that interested advertiser who has the highest unspent budget. They show that the competitive ratio of this algorithm tends to 1- 1/e as b tends to infnity. They also prove a lower bound of 
1 - 1/e for deterministic algorithms.

New idea
To generalize the algorithms of [KP00] to arbitrary bids, it is instructive to examine the special case with bids restricted to {0; 1; 2}. The natural algorithm to try assigns each query to a highest bidder, using the previous heuristic to break ties (largest remaining budget). We provide an example in the appendix to show that such an algorithm achieves a competitive ratios strictly smaller and bounded away from 1 - 1/e.

This indicates the need to consider a much more delicate tradeo between the bid versus unspent budget. The correct tradeo® function is derived by a novel LP-based approach, which we outline below. The resulting algorithm is very simple, and is based on the following tradeoff function:

The algorithm assumes that the daily budget of advertisers is large compared to their bids.

Subscribe for new innovation in this area.
 

Structured Data to Knowledge Graph and Knowledge Graph Identifcation,Bayes' Theorem and Theorem of total probability used as Predictive Algorithm.

Large-scale information processing systems are able to ex- tract massive collections of interrelated facts, but unfortunately trans- forming these candidate facts into useful knowledge is a formidable chal-
lenge. In this paper, we show how uncertain extractions about entities and their relations can be transformed into a knowledge graph. The ex-tractions form an extraction graph and we refer to the task of removing noise, inferring missing information, and determining which candidate facts should be included into a knowledge graph as knowledge graph identi cation. In order to perform this task, we must reason jointly about candidate facts and their associated extraction con dences, identify co- referent entities, and incorporate ontological constraints. Our proposed approach uses probabilistic soft logic (PSL), a recently introduced probabilistic modeling framework which easily scales to millions of facts. We
demonstrate the power of our method on a synthetic Linked Data corpus derived from the MusicBrainz music community and a real-world set of extractions from the NELL project containing over 1M extractions and 70K ontological relations. We show that compared to existing methods, our approach is able to achieve improved AUC and F1 with signi cantly lower running time.

The web is a vast repository of knowledge, but automatically extracting that knowledge at scale has proven to be a formidable challenge. Recent evaluation e orts have focused on automatic knowledge base population [1, 2], and many well-known broad domain and open information extraction systems exist, including the Never-Ending Language Learning (NELL) project , OpenIE , and e orts at Google , which use a variety of techniques to extract new knowledge, in the form of facts, from the web. These facts are interrelated, and hence,recently this extracted knowledge has been referred to as a knowledge graph .

A key challenge in producing the knowledge graph is incorporating noisy information from di erent sources in a consistent manner. Information extraction systems operate over many source documents, such as web pages, and use a collection of strategies to generate candidate facts from the documents, spanning syntactic, lexical and structural features of text. Ultimately, these extraction systems produce candidate facts that include a set of entities, attributes of these entities, and the relations between these entities which we refer to as the extraction graph.However errors in the extraction process introduce inconsistencies in the extraction graph, which may contain duplicate entities and violate key ontological constraints such as subsumption, mutual exclusion, inverse, domain and range constraints. Such noise obscures the true knowledge graph, which captures a consistent set of entities, attributes and relations.

Google work infers the knowledge graph from the extraction graph generated by an information extraction system.
We demonstrate that the errors encountered by information extraction systems require jointly reasoning over candidate facts to construct a consistent knowledge graph. Our approach performs entity resolution, collective classi cation and link prediction while also enforcing global constraints on the knowledge graph, a process which we refer to as knowledge graph identi cation.

In order to implement knowledge graph identi cation, we use probabilistic soft logic (PSL) , a recently introduced framework for reasoning probabilistically over continuously-valued random variables. PSL provides many advantages: models are easily de ned using declarative rules with rst-order logic syntax, continuously-valued variables provide a convenient representation of uncertainty,weighted rules and weight learning capture the importance of model rules, and advanced features such as set-based aggregates and hard constraints are supported. In addition, inference in PSL is a convex optimization that is highly scalable allowing us to handle millions of facts in minutes.

convex optimization is a mathematical concept,where in  3d System we define the quantity to be optimized along Z axis which is a function of a point in x-y plane,where x,y are the domain or parameters upon which Quantity to be optimized depends.
Mathematically it can be represented as
 Z=f(x,y) ,where z= the Quantity to be optimized
                       x,y=domain or variable upon which the Quantity Z depends.
We can extend this concept to n dimensional system too.

Here we develop a PSL model for knowledge graph identi cation that both captures probabilistic dependencies which will be analysed in the next paper between facts and enforces global constraints
between entities and relations. Through this model, we de ne a probability distribution over interpretations - or truth value assignments to facts - each of which corresponds to a possible knowledge graph. By performing inference using the extraction graph and an ontology, we are able to fi nd the most probable knowledge graph. We will try to establish the bene ts of our approach on two large datasets: a synthetic dataset derived from the MusicBrainz com and ontological relationships de ned in the Music Ontology as well as noisy extractions from NELL, a large-scale operational knowledge extraction system.
What you readers can try is
1) formulating the knowledge graph identi cation problem that supports reasoning about multiple, uncertain extractorsources in the presence of ontological constraints;
 2) solving knowledge graph identi cation e ciently with convex optimization using PSL; and
 3) demonstrating the power of knowledge graph identi cation by presenting results on benchmark datasets that are superior to state-of-the-art methods and generating massive knowledge graphs on the scale of minutes that are infeasible to compute in competing systems.


What is the Motivation behind Knowledge Graph Identi cation
 we represent the candidate facts from an information extraction system as a knowledge graph where entities are nodes, categories are labels associated with each node, and relations are directed edges between the nodes. Information extraction systems can extract such candidate facts, and these extractions
can be used to construct an extraction graph. Unfortunately, the extraction graph is often incorrect, with errors such as spurious and missing nodes and edges, and missing or inaccurate node labels. Our approach, knowledge graph identi cation (KGI) combines the tasks of entity resolution, collective classi cation
and link prediction mediated by rules based on ontological information.

From Structured Data to the Knowledge Graph
What actually transformed a Structured Data to the Knowledge Graph.
To understand this we require to understand the following terms,that can be of immense utility for web developers to introduce structured data into their HTML code and thus helping to produce Snippets which we call as brief introductory piece of information for a customer from search engine output corresponding to customer queries typed in search engine.

Agenda
● The end of search as we know it
● Knowledge Graph
● Schema.org and markup
● Developer tools
● What the future holds

If you type in the search engine any search queries the intelligent search engine does the following

1. Answer your queries according to text entered.
2. Anticipate from the text you have entered.

How search engine can Understand the world.Can it See the world through some sensors like camera,can it sense the environment through some sensors like temperature,humidity,sound etc sensors ,can it automatically learn environment ,its people and place information through some sensors and robot programs?

Knowledge Graph about an actor can look like this having a lot of nodes connected directly or indirectly to the central node that is the actor here.

Knowledge Graph helps answer user's queries,the text you enter in the search engine can give you direct answers and will also run prediction algorithm based on the text you have entered and history of that computer searches ,this pridiction algorithm is based on Bayes' Theorem.

Bayes' Theorem and Partition of a sample space
Consider that there are two bags I and II. Bag I contains 2 white and 3 red balls and Bag II contains 4 white and 5 red balls. One ball is drawn at random from one of the bags. We can find the probability of selecting any of the bags (i.e.12 ) or probability of drawing a ball of a particular colour (say white) from a particular bag (say Bag I). In other words, we can find the probability that the ball drawn is of a particular colour, if
we are given the bag from which the ball is drawn. But, can we find the probability that the ball drawn is from a particular bag (say Bag II), if the colour of the ball drawn is given? Here, we have to find the reverse probability of Bag II to be selected when an event occurred after it is known. Famous mathematician, John Bayes' solved the problem of finding reverse probability by using conditional probability. The formula developed by him is known as ‘Bayes theorem’ which was published posthumously in 1763.
Before stating and proving the Bayes' theorem, let us first take up a definition and some preliminary results.

Partition of a sample space


A set of events E1, E2, ..., En is said to represent a partition of the sample space S if
(a) Ei ∩ Ej = φ, i ≠ j, i, j = 1, 2, 3, ..., n
(b) E1 ∪ Ε2 ∪ ... ∪ En= S and
(c) P(Ei) > 0 for all i = 1, 2, ..., n.
In other words, the events E1, E2, ..., En represent a partition of the sample space S if they are pairwise disjoint, exhaustive and have nonzero probabilities.As an example, we see that any nonempty event E and its complement E′ form a partition of the sample space S since they satisfy E ∩ E′ = φ and E ∪ E′ = S.From the Venn diagram in Fig 13.3, one can easily observe that if E and F are any two events associated with a sample space S, then the set {E ∩ F′, E ∩ F, E′ ∩ F, E′ ∩ F′}is a partition of the sample space S. It may be mentioned that the partition of a sample space is not unique. There can be several partitions of the same sample space.We shall now prove a theorem known as Theorem of total probability.

Theorem of total probability
Let {E1, E2,...,En} be a partition of the sample space S, and suppose that each of the
events E1, E2,..., En has nonzero probability of occurrence. Let A be any event associated
with S, then

 Proof: Given that E1, E2,..., En is a partition of the sample space S (Fig below). Therefore

S = E1 ∪ E2 ∪ ... ∪ En   From the figure above

and Ei ∩ Ej = φ, i ≠ j, i, j = 1, 2, ..., n

Now, we know that for any event A,
 A = A ∩ S
     = A ∩ (E1 ∪ E2 ∪ ... ∪ En)
     = (A ∩ E1) ∪ (A ∩ E2) ∪ ...∪ (A ∩ En)
Also A ∩ Ei and A ∩ Ej are respectively the subsets of Ei and Ej . We know that
Ei and Ej are disjoint, for i ≠ j , therefore, A ∩ Ei and A ∩ Ej are also disjoint for all i ≠ j, i, j = 1, 2, ..., n.

Thus, P(A) = P [(A ∩ E1) ∪ (A ∩ E2)∪ .....∪ (A ∩ En)]
                  = P (A ∩ E1) + P (A ∩ E2) + ... + P (A ∩ En)

Now, by multiplication rule of probability, we have
P(A ∩ Ei) = P(Ei) P(A|Ei) as P (Ei) ≠ 0∀i = 1,2,..., n

Therefore, P (A) = P (E1) P (A|E1) + P (E2) P (A|E2) + ... + P (En)P(A|En)

Or

 Let's come back to the topic of Knowledge Graph discussion
Google Knowledge Graph helps answer user's queries as shown in the following Figure

 know what things exist against the text you type in the search engine...........

 summarize relevant facts about those things as shown below ... 

discover related things of interest as shown below........

So you must have realized that Google is a pioneer in the field of information structuring and management and providing you access to the information that is useful to you and that information is having utility for you in the best possible way.It also learns your interest based on the Queries you type in Google search engine and make your search more fruitful by showing information based on your search history and your interest using Some optimized predictive Algorithms.

I will come with more Advertisement Algorithms in the future if you have any query ask and Subscribe to my page to get the Latest updates.

To read my more pages click the link below

• http://artificialintelligenceadvancedmathema.blogspot.in/

• http://advancedmathematicalresearch.blogspot.in/

• http://artificialintelligenceadvancedmathema.blogspot.in/
• http://electronicsandcommunicationadvancedma.blogspot.in/2015/03/3g-networksorthogonal-frequency.html
• https://www.youtube.com/channel/UCd2Gfi81vXUZiQlz6zQjVKQ