Google's voice based search Impressive

It is impressive that Google is able to obtain high accuracy for frequently used search terms in voice based search. This is an excellent engineering work. This is not an easy task since the speech recognizer needs to be stable under various accents. It must have required a lot of training data. I believe that they probably used a large scale finite state transducer to map to the correct word. It will be interesting to know what are the main tricks they employed in order to get this high accuracy.

More Binary search variants

# Search a sorted array of unknown length
# Degree of difficulty: Easy

Assume: Exception will be thrown for array out of bound.

Descriptive answer:
First find the length.
Then do a normal bin search.

How to find the length?
Assume, length 2^n.
Find out valid k for which no exception is thrown.

Again binsearch between 0 and 2^k+1. Consider exception in the
termination criteria.

# Search a sorted array of distinct integer for A[i]=i

# Degree of difficulty: Easy.



def binsearch_var3(list):

    l=0

    u=len(list)-1

    while l<=u:

        m=(l+u)/2

        print '%d %d' %(m,list[m])

        if list[m]==m:

            return m

        elif list[m]            l=m+1

        else:

            u=m-1



    return -1

On auction

Here's Amy Greenwald's essay on Game Theory and the Design of Electronic Markets.

A news article on IBM

On IBM

What does it mean by MSFT's purchase of Skype?

MSFT is going through stiff competition from GOOG and APPL. It has been barely keeping a presence in Internet search industry, even a purchase of sinking YHOO search did not put them in a better shape yet. The PC industry trend is going downward. MSFT is still stronger there but the growth of the PC market itself has already been penetrated by the "Tablets and other devices". Moreover, MSFT has almost lost its presence in the Mobile market which is one of the highest growth segment. The only good news for the software giant is perhaps its growing influence in the games market. Anyway, lets analyze what could be the reasons for MSFT paying a large sum of money for VoIP service like Skype. Skype has 663 million registered users and very significant gross profitability. Skype contributed more net new minutes of international voice than the rest of the industry put together in 2010, according to Telegeography. Skype has never struggled to achieve growth, but its profitability has often been criticized. MSFT can potentially develop a technology with Skype to disrupt the smart phone mobile industry. However, this is an absolutely daunting task to challenge APPL and GOOG in mobile market. But, only MSFT posses the strength for that. However, they need to find one or multiple people who can make that happen. They have many talented leaders. But they need someone different and it is a hard business+technology problem.

An interesting talk

This talk was given in 2004 on collaborative giftedness (work and development). by Henry Tirri.

Growth of eBay An article from 2003

An article published in Forbes magazine in 2003:


NEW YORK - Why did eBay work where Enron failed? Both set out to create revolutionary new Internet-based marketplaces. One of them is a legend in the making, the other is already the stuff of history.

This is no matter of idle curiosity to economists, who are paying increasing attention to how electronic markets work. In one sense, it is work they thought they wouldn't need to do. The mechanisms of markets are well understood and have been little changed--from an economist's perspective--for hundreds of years.

Save for the goods, a medieval European market is much the same as a 21st-century financial market: It is a place where buyers and sellers can come together to trade information and strike bargains; it vouches for the trustworthiness of participants and their goods, and regulates them through codes of behavior, tacit or otherwise; it lets the appropriate prices for a bargain be discovered; and it provides a clearing house for the financial side of transactions.

That seems to describe eBay (nasdaq: EBAY - news - people ), in an economist's dry sort of way. Yet if that is all there is to markets, the world wouldn't be littered with the remains of moribund business-to-business electronic markets. Many of these were started in the bubble-era years on the if-you-build-it-they-will-come principle. When they didn't come, these B2B Web exchanges failed. Electronic markets are more complex and multifaceted, it seems, than traditional markets.

In multifaceted markets, the value of a product to one group depends on the value of another product to another one. To grasp a sense of that complexity, take this example from the physical world: A real estate agent's value to a house seller is a function of the agent's value as a house finder to home seekers.

Marco Iansiti, a professor at Harvard Business School, believes there are eight such principles that have to be honored if such a market--or market platform, as the jargon now has it--is to succeed.

Pricing. Prices have to be set so that the relevant communities are attracted to the market in appropriate numbers. An effective pricing strategy won't necessarily reflect the incremental costs on either side of a market, and establishing optimal prices that maximize profits are complex calculations. A magazine publisher may be prepared to subsidize readers through discounted subscriptions in order to attract more advertisers, but a change in subscription rates could change the numbers and demographics of the readers, thus affecting the price that can be charged for advertisements.

Operations. To thrive, markets have to generate more value than they cost. Many B2B electronic markets failed because they failed to integrate into their buyers' and sellers' own procurement and account management systems.

Technology. Enron's (otc: ENRNQ - news - people ) experience showed that it is difficult to have core technology expertise across a large number of markets. The risk-management-focused technology a bond market needs is very different from the matching algorithms that dating markets like Yahoo! (nasdaq: YHOO - news - people ) Personals rely on. And the best technology in the world won't matter if market participants can't connect to it. Two years ago eBay introduced third-party APIs, which now drive 30% of the site's revenue.

Liquidity. Achieve it first, then scale up. EBay is a textbook example of becoming pervasive among a small community with minimal investment in technology and operating infrastructure before growing.

Flexibility. EBay, Iansiti says, has gone through five generations of technology in its relatively short life. A market has to be able to evolve as it grows.

Adaption. Enron encouraged employees to target markets and go after them. EBay encourages its employees to follow its customers and build up the areas of its market that are working well. Just such an approach led to the creation of eBay Business, potentially a billion-dollar market in its own right. (See: "EBay's Newest $1 Billion Business.")

Leverage participants. EBay created easy-to-use tools and rules that made it simple for their buyers and sellers to clear their transactions.

Trust. Trustworthiness of the participants is an essential foundation of any successful market. EBay's distributed rating system for sellers lets it exercise a trust management system despite handling millions of transactions a day. Market owners should also not be market participants. Enron was a player in its own markets, eBay is not. Enron, of course, also developed bigger trust issues, but those turned bad into disastrous for its marketplace because it was such an important market participant.

The market-platform view extends the concept of a market to all sorts of business value and supply chains. Companies like Sony (nyse: SNE - news - people ), IBM (nyse: IBM - news - people ), Sun Microsystems (nasdaq: SUNW - news - people ) and Palm (nasdaq: PALM - news - people ) are applying the concepts to software marketing, where success depends on attracting both developers of applications and users of them. They manage their intellectual property as if it were a market place.

This approach is not without commercial risk. As David Evans of NERA Economic Consulting and Peter Passell of the Milken Institute say, the recent antitrust suits against Microsoft (nasdaq: MSFT - news - people ) "were directly related to marketing practices peculiar to two-sided markets."

Market platforms encourage concentration more than traditional ones. Multisided markets create network effects that increase the size at which the market will be most efficient. The more people that use eBay overall, the more it will be valued by individual buyers and sellers.

"This creates a considerable challenge for antitrust regulators to distinguish between actions that would undermine competition in one-sided markets yet serve the long-term interests of consumers in two-sided markets," say Evans and Passell.

85% of Web-based auction revenue goes to eBay, they note--a bigger share than Microsoft has of software sales.

Zynga

Zynga has seen phenomenal growth since its inception. They are now almost a 6 billion dollar brand soon to be IPO company. However, they are under a sustainability risk. The problem is that their games are too simple and it is not hard to make similar games with better graphics and better other attributes. I found at least a few example of such games that are coming to facebook very soon. These games are made by well known gaming companies such as Electronic Arts. Here is a discussion on one such game.

Computer science conference ranking

Link: ualberta's page

Pandora's plight

Pandora has an interesting business in constructing radio channels automatically based on some kind of user preference and/or content analysis. The idea is simple and appealing. Realization is hard and it requires advanced machine learning technology. I have been using this radio service for some time. However, it seems that their collection of music leaves a lot to be desired and is not as satisfying as one might expect. This is a typical problem in the collaborative filtering type of applications. In academic jargon, this can be considered as the problem of incorporating diversity with limited supply. Limited supply in this case is clearly a business limitation related to finance and the current state of music industry. However, Pandora definitely requires to address this problem.

Computer science good conferences in ML/IR/Data mining/Vision and NLP

1. NIPS.
2. COLT (Theory)
3. FOCS (Theory)
4. AIStat (Theory)
5. ICML (Application)
6. KDD (Data mining, applications)
7. SDM (Data Mining)
8. ICDM (Data mining)
9. SIGIR (IR)
10. WWW (IR)
11. CIKM (IR)
12. CVPR (Vision)
13. ECCV (Vision)
14. ICCV (Vision)
15. ACL (NLP)
16. EMNLP (NLP)

Learning to rank.

There have been tons of research papers on learning to rank. However, a critical problem of all these methods is that they are some kind of classification or regression techniques that are dependent on human judgement. While it is possible to obtain human judgement for large scale of data, it is hard to obtain good judgement for sufficient amount of search results. Behavioral signals such as clicks can play a role for using unsupervised data, however there are a lot of documents without any behavioral data. Hence, the real problem is actually harder than the theoretical problem. It is also to note that learning to rank is actually a static solution and in order to take the relevance to a new level simulations (such as what is used in economics) are the only useful tools. Fortunately, search engines can iterate through the experiment and can validate the changes using hypothesis testing kind of frameworks (Ron Kohavi, Roger Longbotham, and Toby Walker, Online Experiments: Practical Lessons, IEEE Computer, Vol 43, issue 9, pp. 82-85, Sept 2010. DOI.). This means although the theoretical work on learning to rank is interesting, the major revenue improvement for engines are coming from intelligent trial and error frameworks which has not been captured in theory yet. So interestingly, we perform many minor miracles through these trial and error, excessive use of brute force, and lots and lots of testing, and--so often- and so far -- it has been found to be quite enough. I would view this as something that requires more attention from the theory community.