What's New

My name is Farhad and I am a postdoctoral researcher in KTH, Stockholm, Sweden. You can get to know more about me in here. This blog is about my thoughts on more-or-less everything including, but not limited to, my research, personal matters, book reviews, interesting articles, and etc.

[whatsnewblog]

Trust Me, I am Lying

We are surrounded by participatory-sensing systems. We use them on a daily basis for traffic forecast and navigation, selecting a network with the best coverage, understanding public opinion, and finding the best hotel. All these systems mostly rely on the benevolence of the participants and the sheer number of the users. Sure, there are filters to remove absurd reviews or insulting and irrelevant ones but there is no systematic way to exclude or prohibit malicious reviews and reports that seem fine at first but are advocating a hidden agenda. You might ask why the participants should provide false data. It essentially disrupts their favourite service. One reason could be that their means of communication is hacked. They might provide false data, unknowingly, on behalf of someone with a hidden agenda. For instance, the malicious hacker may want to create a traffic block somewhere or to promote or smear a hotel. It could also be that a user directly gains from providing false data. Recently, residents of less-known/congested roads in Los Angeles were outraged by the traffic which was rerouted to their neighbourhood by the navigation system relying on participatory-sensing forecast and started proving false reports to alleviate the situation. It did not work, as they wanted it to, because they did not plan the false data injection properly. But a coordinated effort can clearly work. Therefore, many researchers has started to look into estimation with strategic sensors. A recent study shows that the main reason that these systems work currently is benevolence. That is, if all the users were to be strategic and perfectly rational, we are hopeless in recovering anything meaningful from their messages. However, not all hope is lost. The study also points out that if the users are not perfectly rational and form herds (which means, if they imitate each other in their way of thinking), the system can extract accurate estimates. This is very good but we cannot always rely on people’s bounded-rationality or good heart for a system to work properly. This way, we would be too fragile when the first calculative evil attacks. A more recent study shows that we can design estimators to promote herding even when dealing with highly rational users. Therefore, we can engineer the behaviour of the strategic users to not lie. Further, the article shows that, even if circumstances are so that the strategic users lie for their benefits, the truth can always be extracted from a large group of users so long there is enough diversity in the interests. This is a simple, yet effective, social engineering phenomenon to construct safe participatory-sensing systems that are robust to cyber-threats. These days, cyber-physical infrastructures, such as intelligent transportation systems, are the building blocks of the smart cities across the globe. We therefore need to create a system that is robust to strategic users that wish to abuse or halt these systems, a system that we can trust even if we know that people lie to it.

[whatsnewblog]

Automated Driving Can Help the EU Achieve Its Carbon-Emission Reduction Targets (in an Easier and Cheaper Way)

On May 21, the EU commission released a guideline on curbing the carbon emission from heavy-duty vehicles. The guideline is motivated by the observation that the “heavy-duty vehicles (HDVs) are responsible for around a quarter of CO2 emissions from road transport in the EU” equivalent to “5% of total EU greenhouse gas emissions”, which is an “unsustainable level” if not any action taken. This guideline is also in line with the EU's commitment for reducing its carbon emission for 2020 by 20% compared to 1990’s levels (with an offer of 30% reduction if other major economies agree to “undertake their fair share”). The strategy set suggests a 30% reduction in carbon emission from HDVs, in medium term, by “supporting alternative fuels for HDVs, smarter pricing on infrastructure usage, effective and coherent use of vehicle taxation by Member States and other market-based mechanisms.” Certainly, improving the efficiency of the HDVs and switching to alternative fuels can reduce the emission in the long run (arguably, at a high price of making European businesses less competitive than their counterparts that do not need to keep track of their carbon footprint). However, there is one approach, missing from the commission’s strategy, which needs an immediate attention, with significant potentials and a relatively low price tag. And, that is automated vehicle platooning. When discussing autonomous vehicles, most people, understandably, think of Google self-driving car, which operates, somewhat successfully, without any command or interference from a driver. However, there are many alternative, simpler forms, such as cruise control, that minimize the required attention from the driver. One such example is automated vehicle platooning, a scenario in which a number of vehicles drive very closely to each other (like a platoon in the army). But, why do we want to, or rather ought to, create a platoon of vehicles that drive so closely to each other? The answer is improved fuel efficiency and, subsequently, reduced carbon emission. You have possibly noticed that the trucks, among other heavy-duty vehicles, look less aerodynamic in comparison to their lightweight counterparts. This is due to a host of reasons, such as less wasted space for transporting goods. This design, unfortunately, causes a huge air drag because there is high-pressure air in front of the truck (combined with low-pressure air behind it). Now, imagine that a second truck is following the first truck very closely. In this case, the second truck does not need to put much effort for defeating the air drag force because there is no high-pressure air in front of it, thanks to the first truck. Now, we may add a third truck, a fourth truck, and so on. Doing so, we create a platoon of trucks with an improved efficiency. Why should this platoon be automated? Because to save fuel, the trucks should move very close to each other (technically, the closer they are the better the efficiency is) and, hence, we cannot rely on the drivers to control the trucks (for the same reason that we are not allowed, by law, to drive very close to the next vehicle on a highway). The trucks need not be completely autonomous; they just need an advanced cruise control that keeps a constant distance with the vehicle in front. But is the improved efficiency worth it? A relatively recent experimental study by KTH Royal Institute of Technology, a university in Sweden, and Scania, a truck manufacturing company, shows that we can easily achieve a “reduction of 4.7–7.7%” in fuel consumption “depending on the time gap [between the trucks], at a set speed of 70 km/h” for two trucks. However, other studies claim that the reduction can be increased up to 21%. The benefits are not only limited to fuel consumption. It is estimated that automated vehicle platooning, if widely adopted, can potentially reduce the fatalities on the road by up to 10%. However, there a number of obstacles that we need to overcome first. When driving so close to each other, we might increase the risk of accidents (in unforeseen circumstances). This is mainly because, with the current technology, we need to rely on visual feedback (e.g., brake lights) to realize that there is an obstacle in front of the leading vehicle. This makes the control very challenging. However, there is an easy fix to this, which is becoming more and more common, and that is vehicle-to-vehicle communication. Each vehicle can simply let the other vehicles in the platoon know that there is a problem ahead. The other problem is that, not necessarily, all the trucks are on the road at the same time and in the same place. To increase the chance of forming platoons (and to increase the length of these platoons), some of the vehicles need to reroute and change their departure times. Furthermore, there are perhaps privacy constraints prohibiting the fleet owners to share their information, as some of these vehicles are transporting other peoples’ goods and they might not want to share their information (e.g., business plans, customer lists, etc) publicly. More importantly, currently, there is no one to match the vehicles together for forming efficient platoons (that do not increase the travel-distances of the trucks by much while giving them an opportunity to save fuel). An application for smart phones, for instance, that allows the fleet owners to enter their information and find good matches online is needed, something like a dating application for trucks. To solve these problems, there is a need for both legislative and financial support from the EU. First, the laws should be changed to allow autonomous vehicles on the road. For instance, currently, the police can stop the trucks if they move very close to each other and nothing is worse, in terms of fuel efficiency, for the trucks to stop-and-go. Second, and more importantly, the EU should provide more financial assistance for research and development to universities and industries to create and to test the technology needed for automated vehicle platooning. Some financial support should also be devoted for raising awareness and changing the publics opinion on this issue (certainly, being stuck behind a line of ten trucks on a highway is not a pleasant experience). In short, the EU commission should embrace automated driving, among other new technologies, in their strategy before they send it to the European Parliament and the Council to be endorsed and delivered. References: 1) EU greenhouse gas emissions and targets, http://ec.europa.eu/clima/policies/g-gas/index_en.htm 2) Climate action: Commission sets out strategy to curb CO2 emissions from trucks, buses and coaches, Press Release, http://europa.eu/rapid/press-release_IP-14-576_en.htm 3) A. Alam, A. Gattami, and K.H. Johansson, “An experimental study on the fuel reduction potential of heavy duty vehicle platooning,” in Proceedings of the 13th International IEEE Conference on Intelligent Transportation Systems (ITSC), 2010. 4) C. Bonnet and H. Fritz, “Fuel Consumption Reduction in a Platoon: Experimental Results with Two Electronically Coupled Trucks at Close Spacing,” 2000, SAE Technical Report 2000-01-3056. 5) T. Robinson, E. Chan, and E. Coelingh, “Operating platoons on public motorways: An introduction to the SARTRE platooning programme,” in Proceedings of the 17th World Congress on Intelligent Transport Systems, 2010.

[whatsnewblog]

Structured ModeL reductIon (SiMpLIfy) Toolbox for MATLAB

Martin, a summer student that Henrik and I were supervising, has developed a very efficient toolbox for structured model reduction for MATLAB. I invite you to read more about this toolbox in http://simplifytoolbox.tumblr.com/. For comments, bug reports, encouragement, suggestions, and complaints, please send email to me ([email protected]). If you ended up using SiMpLIfy, the mentionted toolbox, for research or educational purposes, we would be very happy to hear about it and, perhaps, mention it in the reference guide in future.

[whatsnewblog]

When can we trust the outcome of crowd-sourcing estimation?

Nowadays, a high percentage of people have access to handheld connected devices, specially, smart phones. According to a survey1 commissioned by Google, in Sweden (where I currently live), around 63% of the population have smart phones in 2013 from which 74% do not leave home without their devices and 83% access the Internet on a daily basis using their smart phones. Admittedly, Sweden is one of the best connected countries in the world but the data in the US is not that far also (where 56% of the population have smart phones). Another more interesting fact, which is not at all surprising if we look around, is that the percentage of the population that have smart phones is growing very fast. For instance, in the US, the smart phone penetration ratio has risen to 56% in 2013 from 31% in 2011 and 44% in 2012 perhaps thanks to the ever decreasing prices of smart phones2.

This widespread access to smart phones has fueled a frenzy between IT companies, such as Google, Microsoft, and many small start-up companies, to propose innovative ways of improving services. For instance, we can mention the recent movement on developing applications for crowd-sourcing estimation. These applications use the mobile devices, by gathering relevant data from consensual users and their devices, to guess a variable, such as the traffic condition on a road3, the wireless coverage in a neighborhood4, and a noise pollution in various districts of the city5. Examples of such systems are Sensorly4 for generating wireless coverage maps and Waze6 for traffic estimation. Some of these systems rely on the physical sensors that are actually sitting in your smart device (guaranteed that you give the application the permission to use them) and others would like you to report what you see, or perceive, through the application.

The idea of using the information provided by a big group of people to estimate something accurately is very old and extremely common7. We all probably know give-or-take how congressional legislative hearings, for instance, in the US, work. These hearings typically work on the basis of oral testimonies from witnesses with various backgrounds in front of the legislators in the committee responsible for the act. After the legislators hear the testimonies, they debate and decide on an appropriate course of action. The whole point is that the legislators use the crowd (in this case, witnesses) to get an estimate of a variable (in this case, the usefulness of a bill).

A more recent and relatable example is the traffic estimation. Let's say you are trying to launch a crowd-sourcing application in which the public report to you how long it took them to travel along various roads in a city. You gather these times and, then, perform some magic on them (in scientific jargon, filter them) to get accurate estimations of the travel time along each road. Well, at first, everything seems very nice (indeed, why not). If you ask enough people (that is if you manage to enroll enough people in your application and keep them addicted to it), you can theoretically extract a very good estimation of the travel times along the roads. Ultimately, you can even use this estimation (as many available crowd-sourcing applications do) to reroute vehicles and reduce travel time. But, let's assume that a giant shopping center opens in one of the roads. Should the employees of that shopping center actually tell your application the truth (about their travel time in the vicinity of the shopping center)? Perhaps, you can guess that the answer is no! If they intentionally report a shorter travel time, your estimation is always going have bias to under-estimate the state of the traffic (at that neighborhood) since (potentially, many) users are reporting unrealistically shorter travel times. Why is this good for the shopping center, you may ask? The answer is, if your application thinks that road is less congested, it is going to divert more cars there and more cars there means more costumers are going to see the shopping center in their way home and realize that they need milk or bread8. Now, imagine a new school opens in one of the streets. Should the employees of that school tell your application the truth? Perhaps, you can again guess that the answer is no! They should simply say that the road is congested (over-estimate the travel time) to avoid other cars being rerouted to that street in order to effectively improve the safety of the school children. One may only hope that these groups of people cancel each other's biases (but do they?). Interestingly, it turns out that if all the users are thinking strategically, there are cases for which they render the estimator helpless by interfering with each other9. More precisely, the quality of the estimation actually decreases with employing more senders (let's use this term for distinguishing a member of the public that uses the crowd-sourcing application), which is very counter-intuitive. But, are these cases realistic? Or, more interestingly, what sort of insight do we gain from these cases?

First, in these cases, each sender cannot know the messages transmitted by the other senders to the application. Well, this may or may not be a realistic assumption based on the purpose of the application (and its structure). For instance, if someone is using a crowd-sourcing estimation technique to measure the quality of a product (like in Amazon's online review system), people tend to see the estimate (which is the average of all the reports) as well as the individual scores. However, in traffic estimation applications, people do not even see the estimate (as they only use the suggested route in the application), let alone the individual reports.

Second, the senders do not posses any identity (or, if they have, they participate only once). Therefore, we cannot create a reputation system for them. Similarly, this assumption may or may not be realistic based on the purpose of the application. For instance, in the traffic estimation application, the users typically register and the travel time reports can be attached to their online identities. However, to form a fair assessment of the senders or, as it may sounds sexier, to create a reputation system, we may need to deploy actual sensors that measure the travel times along the roads so that we can compare it with the reported value (and realize who is misreporting and who is not). This, in my opinion, defeats the purpose of having a crowd-sourcing estimation application. On the other hand, if you form a crowd-sourcing estimation technique to measure the quality of a product that people tend to buy only once over a very long time horizon, such as the practicality of a car quantitatively, you have no way for using a useful reputation system (since the buyer is not reporting again in a very long time so that you can weight her subsequent reports by her reputation).

Third, we need to assume that all the senders are strategic. This is probably extremely restrictive since it is fairly easy to see that the Internet is filled with well-meaning users that just want to help. Perhaps, not every one is greedy and selfish (just go and see Wikipedia to understand the sheer number of such benevolent users)! Well, in that case, if you can extract the effect of well-meaning players (that is, if you know who you can trust and who you cannot, which is rather difficult, if not impossible, under the second assumption), you can just remove the strategic senders and use the reports from well-meaning senders. This can be only helpful if the strategic agents are not the majority (since otherwise you simply throw away a large quantity of the data). I should wish you the best of luck (for getting well-meaning senders) if you are living in Washington DC and you are trying to get to the truth out of some ``honest'' testimonies in legislative hearings.

Forth, we need to assume that the agents are rational (with probably limit-less computational capacities). Sadly, or happily (based on which groups of people you belong to), humans do not make decisions by solving complicated optimization problems. They use intuition to make their decision-making process much simpler10. They might also imitate others since they are lazy or do not have the knowledge to find their best response. Interestingly, if the senders are herding (that is, they are imitating each other's method of constructing lies), their lies cancel each others perfectly when the number of the participants grows larger and larger9. This actually happens at a very fast rate!

So, to answer the question in the title, crowd-sourcing estimation is a very nice approach for estimating various variables cheaply if the crowd does not consists of completely selfish people or if they act with bounded rationality. To summarize, crowd-sourcing estimation works a lot of times (if not always), but one needs to be probably a bit more careful when constructing the application!

1. See http://www.thinkwithgoogle.com/mobileplanet/en/ for many cool insights on people's habits on using mobile devices in various countries.

2. http://www.idc.com/getdoc.jsp?containerId=prUS24143513

3. http://traffic.berkeley.edu/

4. http://www.sensorly.com/

5. R. K. Rana, et al, ``Ear-phone: An end-to-end participatory urban noise mapping system,'' in Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks, pp. 105--116, 2010.

6. http://www.waze.com/

7. J. Surowiecki, The Wisdom of Crowds: Why the Many Are Smarter Than the Few and How Collective Wisdom Shapes Business, Economies, Societies and Nations. Doubleday, 2004.

8. I don't know how you do your grocery shopping but I typically remember that I need to buy something whenever I see the sign for a shopping center on my way home.

9. F. Farokhi, A. Teixeira, and C. Langbort, ``Gaussian Cheap Talk Game with Quadratic Cost Functions: When Herding Between Strategic Senders is a Virtue,'' To Appear in the Proceedings of the American Control Conference, 2014.

10. D. Kahneman, Thinking, fast and slow. Macmillan, 2011.

[whatsnewblog]

I have no clue what COMSOL is!

This is not just some random factual sentence regarding what I do know and what I don't. I actually want to criticise Linkedin endorsement program. Specifically, they way that some members use it. Recently, I was endorsed for my abilities in COMSOL and machine learning among many other skills. Well, my abilities in the first one is nonexistent and in the second one surely not endorsable. I have not included any of these skills in my profile. Recently, I have noticed that most of the Linkedin members (that I have encountered and, yes, I have heard about this problem from my friends as well) are endorsing each other for some skills that they do not even have or they are not masterful in it. I really don't know that if the managers really care about the number of endorsements when hiring a person or not, but I must say, if they care, they should only consider it as a measure of popularity rather than skillfulness. It has reached a point that members trade endorsements (that is, it is a social convention that when x endorse y for something, y must also endorses x for some set of skills). This is also partly fuelled by the Linkedin policy of asking you randomly about your friends skills when you are doing something else (like updating your profile, checking news bulletins, etc). The other problem is vaguely-define and arbitrary sets of skills in the Linkedin profile like science, physics, mathematics. What does that even mean when a person adds science to his/her profile as a skill? Is science even a set of skills or something higher than that? I could understand it if someone adds, let's say, scientific thinking or reasoning. That could very well be a useful set of skills, that is, the person can in a rigorous manner construct hypothesis based on available data and then verify (or reject) it using masterfully designed experiments. But, what does it mean when someone adds physics as a skill? Does he/she know physics? But, physics so vast, what does that person know specifically? Astrophysics, condensed matter, high energy physics, biological physics, chemical physics, nonlinear dynamics, complex systems? What?

[whatsnewblog]

MATLAB vs. Julia vs. SciPy?

I recently migrated to Mac from using Windows and the first thing that I observed was that I did not have access to MATLAB anymore. I can still get it under my university license since I am still a grad student, however, because I am currently in the US (as a guest student) and not in Sweden (where I study towards my PhD), it proved to be more difficult that what I thought (so I decided to forget about it). This issue also made me realise that since I finish my studies in some months, I probably cannot have MATLAB cheaply in near future (well, if I stay in academia, as I prefer, I still can get MATLAB under my future employer license). In addition, recently, while I was working with a large-scale learning algorithm (to be specific, a joint strategy fictitious play for learning a pure strategy Nash equilibrium for a systems with around 10000 players in a congestion game; see publication C11 in here for more information), I realized that MATLAB is a bit slow when you are not using it for matrix operations (albeit, this is probably motivated by my mediocre programming skills for translating every possible code into some sort of matrix operation). In my quest, for finding a replacement for MATLAB, I checked Julia (self-described as a "high-level high-performance dynamic programming language for technical computing with syntax that is familiar to users of other technical computing environments" such as MATLAB) and SciPy (self-described as a "Python-based ecosystem of open-source software for mathematics, science, and engineering"). Let me start by briefly mentioning what I experienced and read during this time that convinced me to choose SciPy (for my future research):

Performance: Ok, I mentioned that I am not very happy with the performance of MATLAB so it makes sense to search for technical computing environment that is at least moderately faster for most of times (because MATLAB is seriously fast when it comes to matrix operations, beating it in these areas would be very difficult with my programming skills). Let me borrow some numbers from Julia to compare these environments on performance. Table 1 shows the benchmark times relative to that of C (you can find a link for the codes of each program mentioned in Table 1 also inside Julia's webpage). As we expect, when it comes to matrix operations (the last two lines of the table), MATLAB is faster SciPy but for the rest of the cases SciPy seems to be significantly faster than MATLAB. It also seems that Julia is the fastest of these three. However, because of the other reasons (see below), I would not settle for Julia.

Julia SciPy MATLAB fib 1.97 46.03 1587.03 quicksort 1.37 69.20 133.46 mandel 1.45 34.88 74.61 pi_sum 1.00 33.64 1.46 rand_mat_stat 1.95 29.01 7.71 rand_mat_mul 1.00 1.75 1.08

Table 1: The benchmark times relative to that of C (borrowed from Julia's webpage).

Popularity: Most of the times that I am programming something, I am going to make it available on my webpage (or through other means such as arXiv) for other researchers or my colleagues. Therefore, I would like to choose a language (technical computing environment, or whatever you fancy calling these tools) that is popular enough so that a lot of people can understand the code (or, at least, it is easy enough for them to run it). MATLAB is hugely popular between the researchers from my field (i.e., control engineers). SciPy is also catching up with the numerous implementations and toolboxes recently released by a wave of young researchers that appreciate a free and open-source environment rather than an expensive one like MATLAB. Sadly, because Julia is relatively new, it hasn't become popular yet (but I think because of its performance, it will be star in a couple of years).

Price: Well, everyone knows MATLAB is expensive (at the time of writing this post, you should pay $99 for a student version) unless you have access to a license from your university or workplace. On the other hand, both Julia and SciPy are free and open-source. Therefore, a lot of enthusiastic people even if the do not have access to expensive MATLAB can read your code, run it, and even help you with improving its efficiency. I can also put that extra money that I saved (by not paying Mathworks) to pay for my Friday evening beers.

Ease of Installing: Well, sadly, this is a point that my praise of Julia comes to an end (and the main reason that I stopped using it). It is easy to install Julia itself but you probably need some additional packages for regular tasks such as creating plots. Over the weekend, I tried to install Winston (a very useful package for Julia to create plots among many other things). I did it for more than 10 times. Every time, some new error caused a problem (and terminated the installation prematurely). Then, I had to go some amateur blog (or forum) and read something and fix that error and then another one showed up. Finally, I got frustrated and decided to drop installing it. That was truly a form of torture! Both SciPy (because of its longer existence and well made characteristics) and MATLAB are extremely easy to install and use.

Syntax: In my personal opinion, MATLAB's syntax is easy. In addition, Julia is very much similar to MATLAB (so it is not very difficult to express what you want using Julia as well). SciPy is a bit different so it takes some time to get used to it (at least, in my case, you might be faster and better equipped) but it is very intuitive and easy to use as well.

Availability of Packages: There are many available packages for SciPy and MATLAB that are implemented by mathematicians, computer scientists, engineers, physicists, statisticians, etc. They are also (to my experience) very well-made, efficient, and robust. However, Julia is catching up and there are not that many available packages for it (in comparison to SciPy and MATLAB). However, again, because of its performance, probably in a couple of years, Julia will also have a lot of active users that create useful packages.