Technology Trends

If you’re like me, I bet you hate moments when you’re in a hurry and all the traffic lights seem to intentionally switch to red just in front of your car. Now, according to Nature, a Belgian traffic researcher thinks that traffic lights that respond to local conditions could ease congestion and reduce your frustration. His method would not give you the individual power to switch the light to green. But if you were part of a group of cars approaching a red light, inexpensive traffic-flow sensors would detect your group in advance and turn the light to green. His simulations show that such adaptive traffic control is 30% more efficient than traditional ways of regulating traffic. However, his system has not been adopted by any large city. So you’ll continue to be frustrated by these ?%&$!§ traffic lights for a while. Read more…

Here is a description of the problem.

Carlos Gershenson at the Free University of Brussels, Belgium, says his system of traffic lights would be able to adapt to changing traffic conditions, allowing it to find a better switching sequence than one imposed rigidly on all situations.

There have been some attempts to make traffic signals more flexible, responding to the state of the traffic. These intelligent ‘advanced traffic management systems’ generally connect the lights to a centralized computer that is constantly seeking an optimal switching sequence.

Such approaches are costly to implement, however, and can be computationally very challenging. In Gershenson’s method, by contrast, traffic lights at a junction act on their own, responding simply to the local conditions.

Gershenson used computer simulations to estimate traffic conditions under four systems, traditional ones and his proposed adaptive ones.

Gershenson also tries two adaptive schemes. In the first, called ‘request’ control, a traffic light switches from red to green if the number of vehicles approaching it, or the time vehicles have spent waiting, exceeds a certain threshold. Under such conditions, a large convoy of cars can force a red light to go green as it approaches a junction, opening up a ‘green corridor’ as the convoy progresses across the grid.

Alternatively, in so-called ‘phase’ control, the same rules apply except that there is a minimum time for switching from stop to go or vice versa. Gershenson finds that, in his simulations, adaptive request control is the most efficient for low traffic densities, but works poorly for dense traffic. Adaptive phase control also works well at low densities, and doesn’t clog up at high densities either; so on average, it is the best method overall. Both schemes are typically around 30% more efficient than the non-adaptive ones.

Gershenson admits that the benefits wouldn’t be as large in a big city where the situation is much more complex than in his simulations. But as the method involves only low costs for its implementation, maybe it will be used one of these days.

The research work has been published by arXiv. Here is the abstract of the paper named “Self-Organizing Traffic Lights.”

Steering traffic in cities is a very complex task, since improving efficiency involves the coordination of many actors. Traditional approaches attempt to optimize traffic lights for a particular configuration. of traffic and density. The disadvantage of this lies in the fact that traffic configurations change constantly. Traffic seems to be an adaptation problem rather than an optimization problem. We propose a simple and feasible alternative, in which traffic lights self-organize to improve traffic flow. We use a multi-agent simulation to study two self-organizing methods, which are able to outperform two traditional rigid methods. Using simple rules, traffic lights are able to self-organize and adapt to changing traffic conditions, reducing waiting times, stopped cars, and increasing average speeds. Even when the scenario simplifies real traffic, results are very promising, and encourage further research in more realistic environments.

And here is a direct link to a draft of the full paper (PDF format, 16 pages, 426 KB).

And if you want to know more about traffic lights, here is an article from HowStuffWorks, “How does a traffic light detect that a car has pulled up and is waiting for the light to change?”.

Sources: Philip Ball, Nature, December 3, 2004; arXiv, November 30, 2004; HowStuffWorks website

Related stories can be found in the following categories.

• Artificial Intelligence
  
  
• Sensors
  
  
• Transportation
  

Imagine you work for a company which introduces a new product. Obviously, you would want to know if the public likes it or not. But how would you find it? You could search the Web and read every possible document that mentions your product. This might be very time-consuming. Help is on the way, with a software that will scan the Web for you and separate the positive and negative reviews. This software might be based on research done at Cornell University and described by Technology Research News in “Software sorts out subjectivity.” The researchers are improving ’sentiment classification’ by removing neutral sentences. Their machine-learning method then applies only to subjective portions of the document. But the following negative statement, which contains only positive words, shows the difficulty to classify a sentence as positive or negative: “If you think this laptop is a great deal, I’ve got a nice bridge you might be interested in.” It may take a decade before such a system is widely available. Read more…

Here is how Technology Research News introduces the problem of automatic sentiment classification.

One of the fundamental challenges in getting computers to sort and analyze text is finding ways to automatically classify information.

Applications like search engines that group similar documents do so using topic-based categories. Sentiment analysis techniques add another dimension by determining the author’s attitude about a topic rather than just identifying a topic.

Existing techniques tend to concentrate on finding words, phrases and patterns that indicate sentiment. This has proven difficult, however. “This laptop is a great deal”, for instance, shows strong sentiment, but contains the same words as the neutral sentence “The release of this new laptop drew a great deal of media attention.”

So how do you teach a computer to ‘understand’ the meaning of words?

Researchers from Cornell University have devised a way to improve sentiment classification that sidesteps having to deal with meaning by instead concentrating on context. Their method weeds out neutral sentences. “Getting rid of neutral sentences like ‘The release of this new laptop drew a great deal of media attention’ [makes] the overall sentiment more obvious,” said Lillian Lee, an associate professor of computer science at Cornell University.

Here are more details about the method.

The researchers represented text as a network, or graph. “Imagine that each sentence is represented by a network point, or node,” said Lee. To model contextual information between each pair of sentence nodes, the researchers added a link whose strength represented how much the two sentences deserved the same label — objective or subjective — based on criteria including how close the sentences are to the text, and whether they are separated by a paragraph boundary.

The model also took into consideration the evidence within a sentence that the sentence is subjective or objective. Possible evidence that a sentence is subjective, for example, includes the presence of a word like ‘wonderful’, or ‘terrible’, said Lee.

Each sentence was linked strongly or weakly to a special subjective and objective nodes depending on the amount of evidence there was within the sentence that it was subjective or objective.

The sentences are then clustered into subjective and objective camps based on the strength of the links. This is a graph partitioning problem known as finding the minimum cut, and it can be solved exactly by a quick, efficient algorithm, said Lee.

And is this approach successful?

The method improved sentiment classification performance from 82.8 to 86.4 percent, which is statistically very significant, according to Lee. The method could eventually be used to maintain review-aggregator Web sites, to filter search results by viewpoint, and to track attitudes toward a given topic, she said.

When will be able to use such a software? And what will it be useful for?

It will take at least a decade before the system can readily handle unrestricted texts containing arbitrary rhetorical devices, she said.

The method could be used by search engines to sort or filter results by viewpoint to, for instance, help users distinguish between objective and biased Web sites, said Lee.

It could also be used to track changes in attitudes toward a given topic by, for instance, analyzing press articles, she said.

And companies could use the system to gather business intelligence such as finding out what people think of their products or the products of their competitors. “A computer company might crawl blogs to find out whether or not people like its latest laptop model,” said Lee.

The research work has been published in the Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics, held July 21 to 26, 2004 in Barcelona, Spain under the title “A Sentimental Education: Sentiment Analysis Using Subjectivity Summarization Based on Minimum Cuts.”

Here are two links to the abstract and to the full paper (PDF format, 8 pages, 264 KB). The above diagram was extracted from this paper.

Sources: Kimberly Patch, Technology Research News, November 17/24, 2004; Cornell University website

Related stories can be found in the following categories.

• Artificial Intelligence
  


• Business Intelligence
  


• Search
  


• Software