text:
## Monthly Archives: October 2012

### The Future of Machine Learning (and the End of the World?)

The Future of Machine Learning (and the End of the World?)

On Thursday (Oct 25) we had an event called the ML Futuristic Panel Discussion. The panelists were Ziv Bar-Joseph, Steve Fienberg, Tom Mitchell Aarti Singh and Alex Smola.

Ziv is an expert on machine learning and systems biology. Steve is a colleague of mine in Statistics with a joint appointment in ML, Tom is the head and founder of the ML department, Aarti is an Assistant Professor in ML and Alex, who is well known as a pioneer in kernel methods, is joining us as a professor in ML in January. An august panel to say the least.

The challenge was to predict what the next important breakthroughs in ML would be. It was also a discussion of where the panelists thought ML should be going in the future. Based on my notoriously unreliable memory, here is my summary of the key points.

1. What The Panelists Said

Aarti: ML is good at important but mundane tasks (classification etc) but not at higher level tasks like thinking of new hypotheses. We need ML techniques that play a bigger role in the whole process of making scientific discoveries. The more machines can do, the more high level tasks humans can concentrate their efforts on.

Ziv: There is a gap between the advances in systems biology and its use on practical problems, especially medicine. Each person is a repository of an unimaginable amount of data. An unsolved problem in ML is how to use all the knowledge we have developed in systems biology and use it for personalized medicine. In a sense, this is the problem of bridging information at the cell level and information at the level of an individual (consisting of trillions of interacting cells).

Steve: We should not forget the crucial role of intervention. Experiments involve manipulating variables. Passive ML methods are only part of the whole story. Statistics and ML methods help us learn, but then we have to decide what experiments to do, what interventions to make. Also, we have to decide what data to collect; not all data are useful. In other words, the future of ML has to still include human judgement.

Tom: He joked that his mother was not impressed with ML. After all, she saw Tom grow from an infant who knew nothing, to and adult who can do an amazing number of things. Tom says we need to learn how to “raise computers” in analogy to raising children. We need machines that can learn how to learn. An example is the NELL project (Never Ending Language Learning) which Tom leads. This is a system which has been running since January 2010 and is learning how to read information from the web. See also here. Amazing stuff.

Alex: More and more, computing is done on huge numbers of highly connected inexpensive processors. This raises many questions about how to design algorithms. There are interesting challenges for systems designers, ML people ad statisticians. For example: can you design an estimator that can easily be distributed with little loss of statistical efficiency and that is highly tolerant to failures of small numbers of processors?

2. The Future?

I found the panel discussion very inspiring. All of the panelists had interesting things to say. There was much discussion after the presentations. Martin Azizyan asked (and I am paraphrasing), “Have we really solved all the current ML problems?” The panel agreed that, no, we have not. We need to keep working on current problems (even if they seem mundane compared to the futuristic things discussed by the panel). But we can also work on the next generation of problems at the same time.

Discussing future trends is important. But we have to remember that we are probably wrong about our predictions. Neils Bohr said “Prediction is very difficult, especially about the future.” And as Yogi Berra said, “The future ain’t what it used to be. ”

When I was a kid, it was routinely predicted that, by the year 2000, people would fly to work with jetpacks, we’d have flying cars and we’d harvest our food from the sea. No one really predicted the world wide web, laptops, cellphones, gene microarrays etc.

3. The Return of AI

But, I’ll take my chances and make a prediction anyway. I think Tom is right: computers that learn in ways closer to the ways humans learn is the future.

When I was in London in June, I had the pleasure to meet Shane Legg, from Deepmind Technologies. This is a startup that is trying to build a system that thinks. This was the original dream of AI.

As Shane explained to me, the has been huge progress in both neuroscience and ML and their goal is to bring these things together. I thought it sounded crazy until he told me the list of famous billionaires who have invested in the company.

Which raises an interested question. Suppose someone — Tom Mitchell, the people at Deepmind, or someone else — creates a truly intelligent system. Now they have a system as smart as a human. But all they have to do is put the system on a huge machine with more horsepower than a human brain. Suddenly, we are in the world of super-intelligent computers surpassing humans.

Perhaps they’ll be nice to us. Or, it could turn into Robopocalypse. If so, this could mean the end of the world as we know it.

By the way, Daniel Wilson, the author of Robopocalypse, was a student at CMU. I heard rumours that he kept a picture of me on his desk to intimidate himself to work hard. I don’t think of myself as intimidating so maybe this isn’t true. However, the book begins with a character named Professor Wasserman, a statistics professor, who unwittingly unleashes an intelligent program that leads to the Robopocalypse.

Steve Speilberg is making a movie based on the book, to be released April 25 2104. So far, I have not had any calls from Speilberg.

So my prediction is this: someone other than me will be playing Professor Wasserman in the film adaptation of Robopocalypse.

What are your predictions for the future of ML and Statistics?

### The Inside Story of the L’Aquila Affair

The Inside Story of the L’Aquila Affair

On April 6 2009 a major earthquake in L’Aquila, Italy killed hundreds of people. On October 22 2012, seven people were convicted of manslaughter for downplaying the likelihood of a major earthquake six days before it took place.

I don’t think that the scientists and engineers in Italy should go to prison for failing to clearly communicate the risk to the public.

But … most of the reporting on this side of the Atlantic has been inaccurate. No one was convicted for “failing to predict an earthquake” as has been widely reported. Here is the rest of the story.

1. What Happened

L’Aquila is a small town about 60 miles north-east of Rome. In 2009, the town experienced a swarm of tremors. A local crackpot named Giampaolo Giuliani started making his own earthquake predictions which made nervous residents even more nervous.

According to Wikipedia:

The 2009 L’Aquila earthquake occurred in the region of Abruzzo, in central Italy. The main shock occurred at 3:32 local time on 6 April 2009, and was rated 5.8 on the Richter scale and 6.3 on the moment magnitude scale; its epicentre was near L’Aquila, the capital of Abruzzo, which together with surrounding villages suffered most damage. There have been several thousand foreshocks and aftershocks since December 2008, more than thirty of which had a Richter magnitude greater than 3.5.

In a subsequent inquiry of the handling of the disaster, seven members of the Italian National Commission for the Forecast and Prevention of Major Risks were accused of giving “inexact, incomplete and contradictory” information about the danger of the tremors prior to the main quake. On 22 October 2012, six scientists and one ex-government official were convicted of multiple manslaughter for downplaying the likelihood of a major earthquake six days before it took place. They were each sentenced to six years’ imprisonment

On March 31 2009, there was a meeting in L’Aquila. of the National Commission for the Forecast and Prevention of Major Risks

According to Nature:

The now-famous commission meeting convened on the evening of 31 March in a local government office in L’Aquila. Boschi, who had travelled by car to the city with two other scientists, later called the circumstances “completely out of the ordinary”. Commission sessions are usually closed, so Boschi was surprised to see nearly a dozen local government officials and other non-scientists attending the brief, one-hour meeting, in which the six scientists assessed the swarms of tremors that had rattled the local population. When asked during the meeting if the current seismic swarm could be a precursor to a major quake like the one that levelled L’Aquila in 1703, Boschi said, according to the meeting minutes: “It is unlikely that an earthquake like the one in 1703 could occur in the short term, but the possibility cannot be totally excluded.” The scientific message conveyed at the meeting was anything but reassuring, according to Selvaggi. “If you live in L’Aquila, even if there’s no swarm,” he says, “you can never say, ‘No problem.’ You can never say that in a high-risk region.” But there was minimal discussion of the vulnerability of local buildings, say prosecutors, or of what specific advice should be given to residents about what to do in the event of a major quake. Boschi himself, in a 2009 letter to civil-protection officials published in the Italian weekly news magazine L’Espresso, said: “actions to be undertaken were not even minimally discussed”.

Enzo Boschi was president of Italy’s National Institute of Geophysics and Volcanology. Giulio Selvaggi was director of the National Earthquake Center. The Nature article goes on to say:

Many people in L’Aquila now view the meeting as essentially a public-relations event held to discredit the idea of reliable earthquake prediction (and, by implication, Giuliani) and thereby reassure local residents. Christian Del Pinto, a seismologist with the civil-protection department for the neighbouring region of Molise, sat in on part of the meeting and later told prosecutors in L’Aquila that the commission proceedings struck him as a “grotesque pantomine”. Even Boschi now says that “the point of the meeting was to calm the population. We [scientists] didn’t understand that until later on.”

What happened outside the meeting room may haunt the scientists, and perhaps the world of risk assessment, for many years. Two members of the commission, Barberi and De Bernardinis, along with mayor Cialente and an official from Abruzzo’s civil-protection department, held a press conference to discuss the findings of the meeting. In press interviews before and after the meeting that were broadcast on Italian television, immortalized on YouTube and form detailed parts of the prosecution case, De Bernardinis said that the seismic situation in L’Aquila was “certainly normal” and posed “no danger”, adding that “the scientific community continues to assure me that, to the contrary, it’s a favourable situation because of the continuous discharge of energy”. When prompted by a journalist who said, “So we should have a nice glass of wine,” De Bernardinis replied “Absolutely”, and urged locals to have a glass of Montepulciano.

On April 6, the earthquake struck, killing 309 people.

2. The Phone Call

One thing that is missing in much of the coverage in the U.S. press, is a phone call between Guido Bertolaso (Director of the Italy Civil Defense committee) and Daniela Stati (L’Aquila town councilor for civic protection). Bertolaso was already under investigation for other crimes so his phone was being tapped. The Italian Newspaper, La Repubblica, has the phone conversation on their website. The phone tap was ordered by the Italian Judiciary.

Luckily for me, my wife is from Italy and she has transcribed and translated the phone call. (Thanks Isa.) Here is her translation of the phone call and a few paragraphs from La Repubblica.

THE UNDERESTIMATED EARTHQUAKE

The true story of a mock meeting of the Commission for Major Risks set on March 30, 2009 during a phone conversation between Guido Bertolaso (GB) (Director of the Italy Civil Defense committee) and Daniela Stati (DS) (L’Aquila town councilor for civic protection) tapped under order of the Italian Judiciary Council.

DS Hello

GB This is Guido Bertolaso speaking.

DS Good evening. How are you doing?

GB Good — You’ll receive a phone call from De Bernardinis, my deputy. I asked him to call a meeting in L’Aquila about this issue of seismic clusters that is going on, so as to shut up, right away, any imbecile, to calm down conjectures, worries and so on.

DS Thank you Guido thank you so much.

GB But you have to tell everybody not to send out announcements claiming that no more tremors will occur. This is bullshit. Never say this type of things when speaking of quakes.

DS Absolutely.

GB Somebody told me there has been an announcement claiming there will be no more tremors. But this is something that can never be said, Daniela, not even under torture.

DS Oh I’m sorry Guido, I did not know, I’m just out from a meeting.

GB Never mind, do not worry. But you have to make sure that any announcement goes first by my press office. They [my press office] have expertise on communicating emergency information. They know how to act to avoid any boomerang effect. You know, if there is another tremor in two hours, what are we going to say? Quakes are a mine field.

DS I’ll call them right away.

GB We have got to be very very prudent. Anyway we’ll fix this issue. Tomorrow is very important. De Bernardinis will call you to decide where to set this meeting. I will not be there, but I’ll send Zamberletti, Barberi, Bosci, you know the leading lights of Italian quakes. I’ll send them to the prefect’s office or to your office. You guys decide where, I do not give a shit. This needs to be a public relations event. Do you get it?

DS Yes, yes.

GB So they, the best seismology experts, will say: “This is normal, these phenomena happen. It is better to have 100 level 4 Richter scale tremors rather than nothing. Because 100 tremors are useful for dispersing energy, so there will never be the dangerous quake. Do you understand?

DS All right. I will try to stop that announcement.

GB No, no. It has been done already. My people are covering this. Just talk with De Bernardinis and plan this meeting, and also announce it. We are doing this not because we are worried, but because we want to reassure people. So instead of you and me having a conversation, the best seismology scientists will talk tomorrow.

DS Everything will be all right.

3. My Assessment

Telling people there is no danger, is not the same as failing to predict the earthquake. There was clearly a failure to communicate the risks to the public. And saying that the swarm of tremors reduced the risk seems blatantly misleading. Government officials pressured the scientists into playing down the risks. The scientists were used by impatient and dishonest bureaucrats.

I don’t think it makes sense to prosecute these guys. The bottom line is that earthquake prediction is difficult, everyone knows this, and L’Aquila is known to be in a seismically active area. It’s not like the seismologists actually knew there would be an earthquake and decided to keep it secret. Based on the available information, they presumably did believe that the probability of a big earthquake was low.

They may have mishandled the communication of risk, some of them more than others, but this hardly deserves criminal prosecution and six years of imprisonment.

On the other hand, the government officials who pressured people to play down the risks and who seemed to have no interest in honestly investigating the situation are perhaps more culpable.

As they said in the Corriere della Sera on Oct 24 2012:

The conviction of multiple manslaughter of the seven members of the Italian committee Great Risks is, whether we like it or not, a political sentence. In any other country, where expertise is judged with scientific criteria, politicians would have borne the accountability of their shortcomings.

So the real story of L’Aquila, is the government using scientists as scapegoats.

4. Postscript

The victims of the earthquake were also victims of poor treatment from the Berlusconi government. From Wikipedia:

Around 40,000 people who were made homeless by the earthquake found accommodation in tented camps and a further 10,000 were housed in hotels on the coast. Others sought shelter with friends and relatives throughout Italy. Prime Minister Silvio Berlusconi caused a controversy when he said, in an interview to the German station n-tv, that the homeless victims should consider themselves to be on a “camping weekend” – “They have everything they need, they have medical care, hot food… Of course, their current lodgings are a bit temporary. But they should see it like a weekend of camping.” To clarify his thought, he also told the people in a homeless camp: “Head to the beach. It’s Easter. Take a break. We’re paying for it, you’ll be well looked after.”

### A Rant on Refereeing

Before I started this blog, I posted an essay on my webpage about refereeing called A World Without Referees. There was a bit of discussion about it on the blogosphere. I argued that our peer review system is outdated and unfair.

David Banks has raised this issue here in the Amstat News. Karl Rohe also has an excellent commentary here.

Since I have never posted my original essay on my blog I decided that I should do so now. Here it is. Comments welcome as always.

(For a dissenting view, see Nicolas Chopin’s post on Christian’s blog here.)

Note: For those who have already read this essay, please note that at the end I have added a short postscript which wasn’t in the original.

A World Without Referees

Our current peer review is an authoritarian system resembling a priesthood or a guild. It made sense in the 1600’s when it was invented. Over 300 years later we are still using the same system. It is time to modernize and democratize our approach to scientific publishing.

1. Introduction

The peer review system that we use was invented by Henry Oldenburg, the first editor of the Philosophical Transactions of the Royal Society in 1665. We are using a refereeing system that is almost 350 years old. If we used the same printing methods as we did in 1665 it would be considered laughable. And yet few question our ancient refereeing process.

In this essay I argue that our current peer review process is bad and should be eliminated.

2. The Problem With Peer Review

The refereeing process is very noisy, time consuming and arbitrary. We should be disseminating our research as widely as possible. Instead, we let two or three referees stand in between our work and the rest of our field. I think that most people are so used to our system, that they reflexively defend it when it is criticized. The purpose of doing research is to create new knowledge. This knowledge is useless unless it is disseminated. Refereeing is an impediment to dissemination.

Every experienced researcher that I know has many stories about having papers rejected because of unfair referee reports. Some of this can be written off as sour grapes, but not all of it. In the last 24 years I have been an author, referee, associate editor and editor. I have seen many cases where one referee rejected a paper and another equally qualified referee accepted it. I am quite sure that if I had sent the paper to two other referees, anything could have happened. Referee reports are strongly affected by the personality, mood and disposition of the referee. Is it fair that you work hard on something for two years only to have it casually dismissed by a couple of people who might happen to be in a bad mood or who feel they have to be critical for the sake of being critical?

Some will argue that refereeing provides quality control. This is an illusion. Plenty of bad papers get published and plenty of good papers get rejected. Many think that the stamp of approval by having a paper accepted by the refereeing process is crucial for maintaining the integrity of the field. This attitude treats a field as if it is a priesthood with a set of infallible, wise elders deciding what is good and what is bad. It is also like a guild, which protects itself by making it harder for outsiders to compete with insiders.

We should think about our field like a marketplace of ideas. Everyone should be free to put their ideas out there. There is no need for referees. Good ideas will get recognized, used and cited. Bad ideas will be ignored. This process will be imperfect. But is it really better to have two or three people decide the fate of your work?

Imagine a world without refereeing. Imagine the time and money saved by not having journals, by not having editors, associated editors and imagine never having to referee a paper again. It’s easy if you try.

3. A World Without Referees

Young statisticians (and some of us not so young ones) put our papers on the preprint server arXiv (www.arXiv.org). This is the best and easiest way to disseminate research. If you don’t check arXiv for new papers every day, then you are really missing out.

So a simple idea is just to post your papers on arxiv. If the paper is good, people will read it. If they find mistakes, you can thank them a post a revision. Pretty simple.

Walter Noll is a Professor Mathematics at Carnegie Mellon. He suggests that we all just post our papers on our own websites. Here is a quote from his paper The Future of Scientific Publication.

1) Every author should put an invitation like the following on his or her website: Any comments, reviews, critiques, or objections are invited and should be sent to the author by e-mail. (I have this on my website.) The author should reply to any response and initiate a discussion.

2) Every author should notify his or her worldwide colleagues as soon as a new paper has been published on the website.

3) The traditional review journals (e.g. Mathematical reviews and Zentralblatt), or perhaps a new online journal, should invite the appropriate public to submit reviews, counter-reviews, and discussions of papers on websites and publish them with only minor editing.

4) Promotion committees in universities should give credit to faculty members for writing reviews.

The “publish on your own website” model can be used in concert with the arXiv model.

Question: Won’t we be deluged by papers? I rely on referees to filter out the bad papers.

Answer: I hope we are deluged with papers. That would be great. But I doubt it will be a problem. Math and Physics, who rely heavily on the arXiv model, have done just fine.

If you rely on referees to filter papers for you then I think you are making a huge error. Do you really want referees deciding what papers you get to read? Would like two referees to decide what wines can be sold at the winestore? Isn’t the overwhelming selection of wine a positive rather than a negative? Wouldn’t you prefer having a wide selection so you can decide yourself? Do you really want your choices limited by others? Anyway, if there does end up being a flood of papers then smart, enterprising people will respond by creating websites and blogs that tell you what’s out there, review papers, etc. That’s a much more open, democratic approach.

Question: What is the role of journals in a world without referees?

Answer: The same as the role of punch cards.

Answer: I think we still do need referees here. (Although flying 20 people to Washington for a panel review is ludicrous and unnecessary, but that’s another story.)

Answer: Ignore them or critique them. But don’t suppress them.

Answer: Every promotion case includes a few letter writers who know the area and will be able to write substantial letters. They don’t need the approval of a journal to tell them whether the papers are good. But there will also be some letter writers who are less familiar with the candidate or the field. Sometimes these people just count papers in big journals. But you can always just look at their CV and quickly peruse a few of the candidate’s papers. That doesn’t take much time and is certainly no worse than paper counting.

Answer: There is arguably danger in bad medical papers. But again, I think the answer is to critique rather than suppress. However, I am mainly focusing on areas I am more familiar with, like statistics, computer science etc.

5. Conclusion

When I criticize the peer review process I find that people are quick to agree with me. But when I suggest getting rid of it, I usually find that people rush to defend it. Is it because the system is good or is it because we are so used to it that we just assume it has to be this way?

In three years we will reach the 350th birthday of the peer review system. Let’s hope we can come up with better ideas before then. At the very least we can have a discussion about it.

6. Postscript: An Analogy

In her book The Future and Its Enemies, Virginia Postrel discusses in detail the fact that the birth of new ideas is a messy, unpredictable process. She describes people who accept the unsupervised, unpredictable nature of progress as dynamists. She describes those who fear the disorderly, trial-and-error process of knowledge discovery, as stasists. She divides the stasists into two groups: the reactionaries who oppose progress and the technocrats who try to control progress with bureaucracy and centralized decision making. I classify our current system as technocratic and I am arguing for a more dynamist approach.

### Proof That Theory Matters

Proof That Theory Matters

The title of this post is a slight exaggeration but I do want to discuss an interesting paper by Steve Stigler that provides empirical support for the fact that:

… there is a tendency for influence to flow from theory to applications to a much greater extent than in the reverse direction.

Steve is a professor in the department of statistics at the University of Chicago and is known, among many other things, for his scholarly work on the history of statistics. His father was the Nobel prize winning economist George Stigler.

1. The Paper

The paper is “Citation patterns in the journals of statistics and probability,” which appeared in Statistical Science in 1994 (p 94-108). I think you can get it from the following link.

The article examines citation data between various journals. Obviously the data are now out of date. And there are many practical problems with citation data which Stigler discusses at length in the article.

The part of the paper I want to focus on is where Stigler adopts an economic point if view and treats citations as a form of trade. Citations are viewed as imports and exports. Restricting to eight major journals, Stigler assigns an export score ${S}$ to each journal. The difference of these scores measures the exporting power of one journal to another. Specifically, he defines

$\displaystyle {\rm logodds} (A\ {\rm exports\ to\ B}| {\rm A\ and\ B\ trade})= S_A - S_B.$

There are eight journals but only seven free parameters (since the relevant quantities are differences). So, without loss of generality, he takes The Annals of Statistics to be the baseline journal with score ${S=0}$. This results in the following export scores:

 Journal Score Annals 0.00 Biometrics -1.19 Biometrika -0.35 Communications -3.27 JASA -0.81 JRSS B -0.06 JRSS C -1.30 Technometrics -0.98

To quote from the paper: “The larger the export score, the greater the propensity to export intellectual influence.” In particular, we see that The Annals is the largest exporter.

Later, he puts the journals into three groups: theory (Annals, Biometrika, JRSS B), applied (Biometrics, Technometrics, JRSS C) and mixed (JASA). The result is:

 Theory 0 Mixed -0.66 Applied -0.99

Again we see a flow from theory to applied. The importance of this finding should not be underestimated. Quoting again from the paper:

Thus, we have striking evidence supporting a fundamental role for basic theory that runs strongly counter to the sometimes voiced claim that basic theory is not relevant to applicable methodology.

Another interesting finding in the paper is that there is very little intellectual trade between statistics journals and probability journals.

2. Conclusion

I am fascinated by this paper. The role of theory versus applied work is sometimes controversial and I believe this is one of the few quantitative studies about this issue. The data on which the study was based are now out of date. It would be great if someone would do an updated analysis. And of course we have many new sources of information such as Google Scholar.

3. Reference

Stigler, S.M. (1994). Citation patterns in the journals of statistics and probability. Statistical Science, 94-108.

### The Robins-Ritov Example: A Post-Mortem

The Robins-Ritov Example: A Post-Mortem

This post is follow-up to the two earlier posts on the Robins-Ritov example. We don’t want to prolong the debate but, rather, just summarize our main points.

1. Summary

1. The Horwitz-Thompson estimator ${\hat \psi}$ satisfies the following condition: for every ${\epsilon>0}$,

$\displaystyle \sup_{\theta\in\Theta}\mathbb{P}(|\hat \psi - \psi| > \epsilon) \leq 2 \exp\left(- 2 n \epsilon^2 \delta^2\right) \ \ \ \ \ (1)$

where ${\Theta}$ — the parameter space — is the set of all functions ${\theta: [0,1]^d \rightarrow [0,1]}$. (There are practical improvements to the Horwitz-Thompson estimator that we discussed in our earlier posts but we won’t revisit those here.)

2. A Bayes estimator requires a prior ${W(\theta)}$ for ${\theta}$. In general, if ${W(\theta)}$ is not a function of ${\pi}$ then (1) will not hold. (And in our earlier post we argued that in realistic settings, the prior would in fact not depend on ${\pi}$.)
3. If you let ${W}$ be a function if ${\pi}$, (1) still, in general, does not hold.
4. If you make ${W}$ a function if ${\pi}$ in just the right way, then (1) will hold. Stefan Harmeling and Marc Toussaint have a nice paper which shows one way to do this. And we showed an improved Bayesian estimator that depends on ${\pi}$ in our earlier post. There is nothing wrong with doing this, but in our opinion this is not in the spirit of Bayesian inference. Constructing a Bayesian estimator to have good frequentist properties is really just frequentist inference.

5. Chris Sims pointed out in his notes that the Bayes estimator does well in the parametric case. We agree: we never said otherwise. To quote from Chris’ notes: I think probably the arguments Robins and Wasserman want to make do depend fundamentally on infinite-dimensionality – that is, on considering a situation where ${\theta(\cdot)}$ lies in an infinite-dimensional space and we want to avoid restricting ourselves to a topologically small subset of that space in advance. That’s exactly correct. The problem we are discussing is the nonparametric case.
6. The supremum in (1) is important. When we say that the estimator concentrates around the truth uniformly, we are referring to the presence of the supremum. A Bayes estimator can converge in the non-uniform sense. That is, it can satisfy

$\displaystyle \mathbb{P}(|\hat \psi - \psi| > \epsilon) \leq 2 \exp\left(- 2 n \epsilon^2 \delta^2\right) \ \ \ \ \ (2)$

for some ${\theta}$‘s in ${\Theta}$. In particular, if the prior ${W(\theta)}$ is highly concentrated around some function ${\theta_0}$ and if ${\theta_0}$ happens to be the true function, then of course something like (2) will hold. But if the prior is not concentrated around the truth, (1) won’t hold.

7. This example is only meant to show that Bayesian estimators do not necessarily have good frequentist properties. This should not be surprising. There is no reason why we should in general expect a Bayesian method to have a frequentist property like (1).
8. This example was presented in a simplified form to make it clear. In an observational study, the function ${\pi}$ is also unknown. In that case, when ${X}$ is high dimensional, the best that can be hoped for is a “doubly robust” (DR) estimator that performs well if either (but not necessarily both) ${\pi}$ or ${\theta}$ is accurately modelled. The locally semiparametric efficient regression of our original post with ${\pi}$ estimated is an example. DR estimators are now routinely used in biostatistics. They have also caught the attention of researchers at Google (Lambert and Pregibon 2007, Chan, Ge, Gershony, Hesterberg and Lambert 2010) and Yahoo! (Dudik, Langford and Li 2011). Bayesian approaches to modelling ${\pi}$ and ${\theta}$ have been used in the construction of the DR estimator (Cefalu, Dominici, and Parmigiani 2012).

2. A Sociological Comment

We are surprised by how defensive Bayesians are when we present this example. Consider the following (true) story.

One day, professor X showed LW an example where maximum likelihood does not do well. LW’s response was to shrug his shoulders and say: “that’s interesting. I won’t use maximum likelihood for that example.”

Professor X was surprised. He felt that by showing one example where maximum likelihood fails, he had discredited maximum likelihood. This is absurd. We use maximum likelihood when it works well and we don’t use maximum likelihood when it doesn’t work well.

When Bayesians see the Robins-Ritov example (or other similar examples) why don’t they just shrug their shoulders and say: “that’s interesting. I won’t use Bayesian inference for that example.” Some do. But some feel that if Bayes fails in one example then their whole world comes crashing down. This seems to us to be an over-reaction.

3. References

Cefalu, M. and Dominici, F. and Parmigiani, G. (2012). Model Averaged Double Robust Estimation. Harvard University Biostatistics Working Paper Series. link.

Chan, D., Ge, R., Gershony, O., Hesterberg, T. and Lambert, D. (2010). Evaluating online ad campaigns in a pipeline: causal models at scale. Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, 7-16.

Dudik, M., Langford, J. and Li, L. (2011). Doubly Robust Policy Evaluation and Learning. Arxiv preprint arXiv:1103.4601.

Harmeling, S. and Toussaint, M. (2007). Bayesian Estimators for Robins-Ritov’s Problem. Technical Report. University of Edinburgh, School of Informatics.

Lambert, D. and Pregibon, D. (2007). More bang for their bucks: assessing new features for online advertisers. Proceedings of the 1st international workshop on Data mining and audience intelligence for advertising, 7-15.

Recently, there was a discussion on stack exchange about an example in my book. The example is a paradox about estimating normalizing constants. The analysis of the problem in my book is wrong; more precisely, the analysis is my book is meant to show that just blindly applying Bayes’ rule does not always yield a correct posterior distribution.

This point was correctly noted by a commenter at stack exchange who uses the name “Zen.” I don’t know who Zen is, but he or she correctly identified the problem with the analysis in my book.

However, it is still an open question how to do the analysis properly. Another commenter, David Rohde, identified the usual proposal which I’ll review below. But as I’ll explain, I don’t think the usual answer is satisfactory.

The purpose of this post is to explain the paradox and then I want to ask the question: does anyone know how to correctly solve the problem?

The example, by the way, is due to my friend Ed George.

1. Problem Description

The posterior for a parameter ${\theta}$ given data ${Y_1,\ldots, Y_n}$ is

$\displaystyle p(\theta|Y_1,\ldots, Y_n) =\frac{L(\theta)\pi(\theta)}{c}$

where ${L(\theta)}$ is the likelihood function, ${\pi(\theta)}$ is the prior and ${c= \int L(\theta)\pi(\theta)}$ is the normalizing constant. Notice that the function ${L(\theta)\pi(\theta)}$ is known.

In complicated models, especially where ${\theta}$ is a high-dimensional vector, it is not possible to do the integral ${c= \int L(\theta)\pi(\theta)}$. Fortunately, we may not need to know the normalizing constant. However, there are occasions where we do need to know it. So how can we compute ${c}$ when we can’t do the integral?

In many cases we can use simulation methods (such as MCMC) to draw a sample ${\theta_1,\ldots, \theta_n}$ from the posterior. The question is: how can we use the sample ${\theta_1,\ldots, \theta_n}$ from the posterior to estimate ${c}$?

More generally, suppose that

$\displaystyle f(\theta) = \frac{g(\theta)}{c}$

where ${g(\theta)}$ is known but we cannot compute the integral ${c = \int g(\theta) d \theta}$. Given a sample ${\theta_1,\ldots, \theta_n \sim f}$, how do we estimate ${c}$?

2. Frequentist Estimator

We can use the sample to compute a density estimator ${\hat f(\theta)}$ of ${f(\theta)}$. Note that ${c = g(\theta)/f(\theta)}$ for all ${\theta}$. This suggests the estimator

$\displaystyle \hat c = \frac{g(\theta_0)}{\hat f(\theta_0)}$

where ${\theta_0}$ is an arbitrary value of ${\theta}$.

This is only one possible estimator. In fact, there is much research on the problem of finding good estimators of ${c}$ from the sample. As far as I know, all of them are frequentist.

As David Rohde notes on stack exchange, there is a certain irony to the fact the Bayesians use frequentist methods to estimate the normalizing constant of their posterior distributions.

3. A Bogus Bayesian Analysis

Let’s restate the problem. We have a sample ${\theta_1,\ldots, \theta_n}$ from ${f(\theta)=g(\theta)/c}$. The function ${g(\theta)}$ is known but we don’t know the constant ${c = \int g(\theta) d\theta}$ and it is not feasible to do the integral.

In my book, I consider the following Bayesian analysis. The analysis is wrong, as I’ll explain in a minute.

We have an unknown quantity ${c}$ and some data ${\theta_1,\ldots, \theta_n}$. We should be able to do Bayesian inference for ${c}$. We start by placing a prior ${h(c)}$ on ${c}$. The posterior is obtained by multiplying the prior and the likelihood:

$\displaystyle h(c|\theta_1,\ldots, \theta_n) = h(c) \prod_{i=1}^n \frac{g(\theta_i)}{c} \propto h(c) c^{-n}$

where we dropped the terms ${g(\theta_i)}$ since they are known.

The “posterior” ${h(c|\theta_1,\ldots, \theta_n) \propto h(c) c^{-n}}$ is useless. It does not depend on the data. And it may not even be integrable.

The point of the example was to point out that blindly applying Bayes rule is not always wise. As I mentioned earlier, Zen correctly notes that my application of Bayes rule is not valid. The reason is that, I acted as if we had a family of densities ${f(\theta|c)}$ indexed by ${c}$. But we don’t: ${f(\theta)=g(\theta)/c}$ is a valid density only for one value of ${c}$, namely, ${c = \int g(\theta)d\theta}$. (To get a valid posterior from Bayes rule, we need a family ${f(x|\psi)}$ which is a valid distribution for ${x}$, for each value of ${\psi}$.)

4. A Correct Bayesian Analysis?

The usual Bayesian approach that I have seen is to pretend that the function ${g}$ is unknown. Then we place a prior on ${g}$ (such as a Gaussian process prior) and proceed with a Bayesian analysis. However, this seems a unsatisfactory. It seems to me that we should be able to get a valid Bayesian estimator for ${c}$ with pretending not to know ${g}$.

Christian Robert discussed the problem on his blog. If I understand what Christian has written, he claims that this cannot be considered a statistical problem and that we can’t even put a prior on ${c}$ because it is a constant. I don’t find this point of view convincing. Isn’t the whole point of Bayesian inference that we can put distributions on fixed but unknown constants? Christian says that this is a numerical problem not a statistical problem. But we have data sampled from a distribution. To me, that makes it a statistical problem.

So what is a valid Bayes estimator of ${c}$? Pretending I don’t know ${g}$ or simply declaring it to be a non-statistical problem seem like giving up.

I want to emphasize that this is not meant in any way as a critique of Bayes. I really think there should be a good Bayesian estimator here but I don’t know what it is.

Anyone have any good ideas?

### Testing Millions of Hypotheses: FDR

In the olden days, multiple testing meant testing 8 or 9 hypotheses. Today, multiple testing can involve testing thousands or even million of hypotheses.

A revolution occurred with the publication of Benjamini and Hochberg (1995). The method introduced in that paper has made it feasible to test huge numbers of hypotheses with high power. The Benjamini and Hochberg method is now standard in areas like genomics.

1. Multiple Testing

We want to test a large number of null hypotheses ${H_1,\ldots, H_N}$. Let ${H_j =0}$ if the ${j^{\rm th}}$ null hypothesis is true and let ${H_j =1}$ if the ${j^{\rm th}}$ null hypothesis is false. For example, ${H_j}$ might be the hypothesis that there is no difference in mean gene expression level between healthy and diseased tissue, for the ${j^{\rm th}}$ gene.

For each hypothesis ${H_j}$ we have a test statistic ${Z_j}$ and a p-value ${P_j}$ computed from the test statistic. If ${H_j}$ is true (no difference) then ${P_j}$ has a uniform distribution ${U}$ on ${(0,1)}$. If ${H_j}$ is false (there is a difference) then ${P_j}$ has some other distribution, typically more concentrated towards 0.

If we were testing one hypotheses, we would reject the null hypothesis if the p-value is less than ${\alpha}$. The type I error — the probability of a false rejection — is then ${\alpha}$. But in multiple testing we can’t simply reject all hypotheses for which ${P_j \leq \alpha}$. When ${N}$ is large, we will make many type I errors.

A common and very simple way to fix the problem is the Bonferroni method: reject when ${P_j\leq \alpha/N}$. The set of rejected hypotheses is

$\displaystyle R = \Bigl\{j:\ P_j \leq \frac{\alpha}{N}\Bigr\}.$

It follows from the union bound that

$\displaystyle {\rm Probability\ of\ any\ false\ rejections\ }= P(R \cap {\cal N}) \leq \alpha$

where ${{\cal N} = \{j:\ H_j =0\}}$ is the set of true null hypotheses.

The problem with the Bonferroni method is that the power — the probability of rejecting ${H_j}$ when ${H_j=1}$ — goes to 0 as ${N}$ increases.

2. FDR

Instead of controlling the probability of any false rejections, the Benjamini-Hochberg (BH) method controls the false discovery rate (FDR) defined to be

$\displaystyle {\rm FDR} = \mathbb{E}({\rm FDP})$

where

$\displaystyle {\rm FDP} = \frac{F}{R},$

${F}$ is the number of false rejections and ${R}$ is the number of rejections. Here, FDP is the false discovery proportion.

The BH method works as follows. Let

$\displaystyle P_{(1)}\leq P_{(2)}\leq \cdots \leq P_{(N)}$

be the ordered p-values. The rejection set is

$\displaystyle R = \Bigl\{j:\ P_j \leq T\Bigr\}$

where ${T=P_{(j)}}$ and

$\displaystyle j = \max \left\{ s:\ P_{(s)} \leq \frac{\alpha s}{N} \right\}.$

(If the p-values are not independent, an adjustment may be required.) Benjamini and Hochberg proved that, if this method is used then ${{\rm FDR} \leq \alpha}$.

3. Why Does It Work?

The original proof that ${{\rm FDR} \leq \alpha}$ is a bit complicated. A slick martingale proof can be found in Storey, Taylor and Siegmund (2003). Here, I’ll give a less than rigorous but very simple proof.

Suppose the fraction of true nulls is ${\pi}$. The distribution of the p-values can be written as

$\displaystyle G = \pi U + (1-\pi)A$

where ${U(t)=t}$ is the uniform (0,1) distribution (the nulls) and ${A}$ is some other distribution on (0,1) (the alternatives). Let

$\displaystyle \hat G(t) = \frac{1}{N}\sum_{j=1}^N I(P_j \leq t)$

be the empirical distribution of the p-values. Suppose we reject all p-values less than ${t}$. Now

$\displaystyle F = \sum_{j=1}^n I(P_j\leq t, H_j=0)$

and

$\displaystyle R = \sum_{j=1}^n I(P_j\leq t) = N \hat{G}(t).$

Thus,

$\displaystyle \begin{array}{rcl} \mathbb{E}\left( \frac{F}{R}\right) &=& \mathbb{E}\left(\frac{\sum_{j=1}^n I(P_j\leq t, H_j=0)}{\sum_{j=1}^n I(P_j\leq t)}\right)\\ &=& \frac{\mathbb{E}\left(\sum_{j=1}^n I(P_j\leq t, H_j=0)\right)} {\mathbb{E}\left(\sum_{j=1}^n I(P_j\leq t)\right)} + O\left(\sqrt{\frac{1}{N}}\right)\\ &=& \frac{N P(P_j \leq t|H_j=0) P(H_j=0)}{N G(t)} + O\left(\sqrt{\frac{1}{N}}\right)\\ &=& \frac{t\pi}{G(t)} + O\left(\sqrt{\frac{1}{N}}\right)= \frac{t\pi}{\hat G(t)} + O_P\left(\sqrt{\frac{1}{N}}\right) \end{array}$

and so

$\displaystyle {\rm FDR} \approx \frac{t\pi}{\hat G(t)}.$

Now let ${t}$ be equal to one of the ordered p-values, say ${P_{(j)}}$. Thus ${t = P_{(j)}}$, ${\hat G(t) = j/N}$ and

$\displaystyle {\rm FDR} \approx \frac{\pi P_{(j)}N}{j} \leq \frac{P_{(j)}N}{j}.$

Setting the right hand side to be less than or equal to ${\alpha}$ yields

$\displaystyle \frac{N P_{(j)}}{j} \leq \alpha$

or in other words, choose ${t=P_{(j)}}$ to satisfy

$\displaystyle P_{(j)} \leq \frac{\alpha j}{N}$

which is exactly the BH method.

To summarize: we reject all p-values less than ${T=P_{(j)}}$ where

$\displaystyle j = \max \left\{ s:\ P_{(s)} \leq \frac{\alpha s}{N} \right\}.$

We then have the guarantee that ${FDR \leq \alpha}$.

The method is simple and, unlike Bonferroni, the power does not go to 0 as ${N\rightarrow\infty}$.

There are now many modifications to the BH method. For example, instead of controlling the mean of the FDP you can choose ${T}$ so that

$\displaystyle P({\rm FDP} > \alpha) \leq \beta$

which is called FDP control. (Genovese and Wasserman 2006). One can also weight the p-values (Genovese, Roeder, and Wasserman 2006).

4. Limitations

FDR methods control the error rate while maintaining high power. But it is important to realize that these methods give weaker control than Bonferroni. FDR controls the (expected) fraction of false rejections. Bonferroni protects you from making any false rejections. Which you should use is very problem dependent.

5. References

Benjamini, Y. and Hochberg, Y. (1995). Controlling the false discovery rate: a practical and powerful approach to multiple testing. Journal of the Royal Statistical Society. Series B (Methodological). 289–300.

Genovese, C.R. and Roeder, K. and Wasserman, L. (2006). False discovery control with p-value weighting. Biometrika, 93, 509-524.

Genovese, C.R. and Wasserman, L. (2006). Exceedance control of the false discovery proportion. Journal of the American Statistical Association, 101, 1408-1417.

Storey, J.D. and Taylor, J.E. and Siegmund, D. (2003). Strong control, conservative point estimation and simultaneous conservative consistency of false discovery rates: a unified approach. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 66, 187–205.


text:
# CHARACTERIZATION AND CALIBRATION OF THE BRUKER IFS 120 HR

Please use this identifier to cite or link to this item: http://hdl.handle.net/1811/18261

Files Size Format View
1990-TB-06.jpg 44.68Kb JPEG image

 Title: CHARACTERIZATION AND CALIBRATION OF THE BRUKER IFS 120 HR Creators: Birk, M.; Peterson, D. B.; Pickett, H. M. Issue Date: 1990 Publisher: Ohio State University Abstract: Absorption spectra of $CO_{2}, N_{2}O$ and $CS_{2}$ have been recorded using the Bruker IFS 120 HR spectrometer. Absolute frequency calibration for the mid-infrared was completed using the $CO_{2}$ and $N_{2}O$ absorption lines. The transitions were compared to previous data1 and produced a RMS deviation of $0.00005 cm^{-1}$. The $CS_{2}$ spectra at $2100 cm^{-1}$ was used to characterize the instrumental lineshape. After a correction for field of view effects an agreement of 0.03 \% transmission was achieved between experimental and theoretical lineshapes. The results of the characterization and calibration will be discussed. Description: $^{1}$ C. R. Pollock et.al. J. Mol. Spec. 102. 112 (1983). Author Institution: Jet Propulsion Laboratory, California Institute of Technology URI: http://hdl.handle.net/1811/18261 Other Identifiers: 1990-TB-6

format: plain


text:
# Thompson Sampling

I read on Wikipedia that Thompson sampling consists in playing the action ${\displaystyle a \in {\mathcal {A}}}$ according to the probability that this action maximizes the expected reward.

This probability seems to be:

$\int {\mathbb {I}}[{\mathbb {E}}(r \;\vert \;a,\theta )=\max _{{a'}}{\mathbb {E}}(r \; | \; a',\theta )]\; P(\theta |{\mathcal {D}})\,d\theta$

How does one derive this Eq? That is, why is the value of the Eq. above the probability of the action maximizing expected reward)?

This Eq. can also be found in papers on Thompson sampling, e.g. first Eq. here.

Let $$A$$ be the random event that the action $$a^*\in\mathcal{A}$$ maximizes the expected reward $$\bar{r}(a,\theta)=\mathbb{E}(r|a,\theta).$$
Let $$r^*(\theta)$$ be the maximum expected reward for given $$\theta$$, $$\bar{r}^*(\theta)=\max_{a'}\bar{r}(a',\theta).$$ The event $$A$$ we are interested in can be written then as follows: $$A=\{\theta: \bar{r}(a^*,\theta)=\bar{r}^*(\theta)\}.$$ The probability of this event is: $$\mathbb{P}(A)=\int_A P(\theta|\mathcal{D})d\theta=\int I_A(\theta)P(\theta|\mathcal{D})d\theta.$$ This is exactly the Wikipedia formula (in new notation).
• Thanks! Why is the event $A$ defined as a set in the parameter space $\theta$ (that is, why is it that $A=\{\theta: \bar{r}(a^*,\theta)=\bar{r}^*(\theta)\}$ ?). Since we are talking about the probability that we are choosing the optimal action (i.e. the one that optimizes expected reward), shouldn't A be defined as a set of actions in $\mathcal{A}$? – Josh Jul 11 '16 at 0:35
• For a fixed action $a^*$, that action may or may not be optimal. This depends on $\theta$, which is random. This makes $A$ also random. Perhaps, my notation is also bad and instead of $A$, it is better to use something like $\Theta_{a^*}$. One more remark: if $A$ is a set of actions, that the indicator function does not depend on $\theta$ and can be take out of integration. – Kostia Jul 11 '16 at 7:37


text:
## Trigonometry (11th Edition) Clone

$$\frac{\tan\theta-\cot\theta}{\tan\theta+\cot\theta}=1-2\cos^2\theta$$ The proof is explained in the Work step by step.
$$\frac{\tan\theta-\cot\theta}{\tan\theta+\cot\theta}=1-2\cos^2\theta$$ The left side is more complicated, which is the reason why we need to deal with it first. $$X=\frac{\tan\theta-\cot\theta}{\tan\theta+\cot\theta}$$ - The following identities would be applied to rewrite $\tan\theta$ and $\cot\theta$. $$\tan\theta=\frac{\sin\theta}{\cos\theta}\hspace{2cm}\cot\theta=\frac{\cos\theta}{\sin\theta}$$ $$X=\frac{\frac{\sin\theta}{\cos\theta}-\frac{\cos\theta}{\sin\theta}}{\frac{\sin\theta}{\cos\theta}+\frac{\cos\theta}{\sin\theta}}$$ $$X=\frac{\frac{\sin^2\theta-\cos^2\theta}{\cos\theta\sin\theta}}{\frac{\sin^2\theta+\cos^2\theta}{\cos\theta\sin\theta}}$$ $$X=\frac{\sin^2\theta-\cos^2\theta}{\sin^2\theta+\cos^2\theta}$$ - Pythagorean identity: $\sin^2\theta+\cos^2\theta=1$ $$X=\frac{\sin^2\theta-\cos^2\theta}{1}$$ $$X=\sin^2\theta-\cos^2\theta$$ - Again, Pythagorean identity: $\sin^2\theta=1-\cos^2\theta$ $$X=1-\cos^2\theta-\cos^2\theta$$ $$X=1-2\cos^2\theta$$ That means $$\frac{\tan\theta-\cot\theta}{\tan\theta+\cot\theta}=1-2\cos^2\theta$$ The equation is an identity.


text:
# Thread: Standard (asymptotic standard) error of ŷi of exponential regression (Y = exp(aX))

1. ## Standard (asymptotic standard) error of ŷi of exponential regression (Y = exp(aX))

Hello People
I was look a formual or description how to calculate standard error of ŷi or usually called asymptotic standard error in non-linear regression:
In my case is exponential regression: Y = exp(aX) where 'a' is constant.
the standard error or should be estimated for each ŷi.
Is there any online resource which explains good.....

Look the attachment for the formula, where F is the matrix of derivatives for approximating least squares estimations and Fi denotes the ith row of F matrix and where σ2 is the MSE.


text:
# Classical Probability and Relative Frequency Probability Approach

#### sachinner

##### New Member
As classical Probability uses mathematical formula for calculation and events are equally likely. As I know Binomial distribution is used for classical probability approach.
Q-1)Which are other theoretical distributions that are used with classical probability approach?
Q-2)Similarly, are there any theoretical distributions which can be used for Relative frequency probability approach? OR some other ways are used, if yes please mention.


text:
Conservation of angular momentum across different reference frames?

I saw the following problem from the USAPhO:

A uniform pool ball of radius $r$ begins at rest on a pool table. The ball is given a horizontal impulse $J$ of fixed magnitude at a distance $\beta r$ above its center, where $−1 \leq \beta \leq 1$. The coefficient of kinetic friction between the ball and the pool table is $\mu$. Find an expression for the final speed of the ball as a function of $J$, $m$, and $\beta$.

Two solutions are presented. In the first solution, we are told to "consider an axis perpendicular to the initial impulse and coplanar with the table." Then we apply conservation of angular momentum momentum with the initial state immediately after the impulse and the final state after the ball has achieved rolling without slipping (and hence has constant velocity)

From my understanding, at any given moment, the axis always passes through the point of contact between the ball and the ground. This is the part the confuses me. Since the axis is not fixed, why is angular momentum $\ell$ conserved between the initial and final states? I noticed that $\ell$ at some time when the ball is still rolling without slipping is not the same as the initial $\ell$. (If the ball has angular velocity $\omega$ at some time, then $\ell = I\omega$, which varies as $\omega$ varies.) I believe this is related to the fact that during the rolling without slipping phase, we are not in an inertial reference frame.

(In particular, the problem is is USAPhO 2008 Quarterfinal, problem 2(a). You can find the problem and its solution here: http://www.aapt.org/physicsteam/2012/exams.cfm)

-

My initial reasoning was wrong, sorry, I can't justify the use of angular momentum conservation in that non-inertial frame. One can write a balance equation for the angular momentum, but after all it should be the same as solution №2.

But ok, let's choose a single inertial frame. Let it be the one moving with the ultimate ball velocity $v_f$. This will lead the ball having some initial angular momentum $L_0$ and recalculated value for added momentum J. Then the conservation of angular momentum will be

$$(\beta+1) r (J + mvr) + L_0 = \frac{7}{5} m r^2 \omega$$

where

$$\begin{multline} L_0 = - \int_0^{2r} \rho z v \, \pi \left[r^2 - (r-z)^2\right] dz = \\ - v \frac{m}{\frac{4}{3}\pi r^3} \pi \int_0^{2r} z \left[r^2 - (r-z)^2\right] \, dz = -mvr \end{multline}$$

Hence

$$(\beta+1) r J = \frac{7}{5} m r^2 \omega$$

Instead of direct integration one could use the expression for angular momentum in a moving frame, but I don't remember how to do it.

-
Thanks for your answer! I have some questions: (1) When you say "you don't take into account usual $g$," what exactly do you mean? In gyroscopes, for example, the gravity produces a torque which causes a change in angular momentum. (2) Where does the term $L_0$ come from? I thought changing $J$ to $J+mv$ would account for the change in reference frame. – Alan C Aug 18 '12 at 23:44
(2) In that new frame initially the ball is moving (without rotating) with the speed $-v$. Obviously this accounts for some initial angular momentum since the axis does not pass through the ball's center of mass. – Yrogirg Aug 19 '12 at 6:14
(1) my argument was flowed, but in (2) I'm sure. – Yrogirg Aug 19 '12 at 8:44
Thank you for the explanations! – Alan C Aug 22 '12 at 4:42


text:
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 444

# Pipe e-mail to php script with vbs script

I'm using the included code to pipe an e-mail to a php script on arrival. I don't know VB very well, so I was hoping someone could help me.

The line that says: Const g_sPipeAddress = "" tells the mail server what incoming e-mails to run the script included on the line above. For instance, if that line said Const g_sPipeAddress = "nathanael@domain.com", all emails to nathanael@domain.com would have the script run. If the line had no address specified, it runs for all incoming mail. What I need to do is have all emails sent to post***********@domain.com have the script run. Would anyone be able to modify this script to help me?

Do I need to use a regular expression? If so, can you point me in the right direction on writing one?

Thank you!

Const g_sPHPPath     = "C:\path\to\php.exe"
Const g_sScriptPath  = "C:\path\to\script.php"

const g_sDQ          = """"

Sub OnDeliverMessage(oMessage)

bPipeMessage = True
Else
bPipeMessage = False

Set obRecipients = oMessage.Recipients

For i = 0 to obRecipients.Count - 1
Set obRecipient = obRecipients.Item(i)

bPipeMessage = True
End If
Next
End If

If bPipeMessage Then
sCommandLine = "cmd /c type " & g_sDQ & oMessage.Filename & g_sDQ & " | " & g_sDQ & g_sPHPPath & g_sDQ & " " & g_sDQ & g_sScriptPath & g_sDQ
Set oShell = CreateObject("WScript.Shell")
Call oShell.Run(sCommandLine, 0, TRUE)
End If
End Sub

0
bruhast
1 Solution

Commented:
Hi, bruhast.

I'm not sure I understand your question.  Are you asking how you can compare the domain portion of the incoming email address to g_sPipeAddress?  If so, then you can use the InStr function.  Something like the code in the snippet.  InStr test to see if the second string occurs anywhere in the first string.  If it does, then it returns True.
         If InStr(1,LCase(obRecipient.Address), LCase(g_sPipeAddress)) Then
bPipeMessage = True
End If

0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.


text:
# Help to clarify chemcial potential

1. Nov 10, 2014

### KFC

Hi there,
The first time I heard about chemical potential is statistical mechanics but I didn't understand that so well due to the misleading term "chemical". Recently, I am reading some introduction articles on optical lattices for bosons and it again mentions there a chemical potential for each lattice site for bosons sitting on that site. I wonder what's chemical potential is really about? What happens if it increases or decreases? What's difference for big chemical potential and small one? Thanks.

2. Nov 10, 2014

### Staff: Mentor

The chemical potential is the energy necessary to add a particle to a system. In the example you cite, it is the energy necessary to add a boson at a particular lattice site.

When two systems can exchange particles, the chemical potential acts pretty much in the same way as temperature does for energy. Particles will move from the system with a higher chemical potential to the one with the lower chemical potential, until equilibrium is reached, i.e., when the chemical potential in both systems is equal. This idea can be extended to different species in chemical equlibrium, where the "chemical" adjective takes on its full meaning.

3. Nov 12, 2014

### zhanhai

"The chemical potential is the energy necessary to add a particle to a system."

I would doubt this. A crystal has its chemical potential, say Ef. If an electron at an energy (Ef-V) in the crystal is taken away from the crystal, can a new electron with energy (Ef-V) be added to the crystal?

4. Nov 13, 2014

### DrDu

It is the change of internal energy with particle number $\mu=\partial U(S,V,N)/\partial N=\partial G(T,p,N)/\partial N$.

5. Nov 13, 2014

### Matterwave

On should specify; however, that T and P are required to be constant in the above definitions of chemical potential. So the Chemical potential is the energy needed to add a particle to a system at constant temperature and pressure.

6. Nov 13, 2014

### DrDu

No, from the formulas I gave, you can see that T and P have to be held constant when considering the Gibbs free energy, while for the change of ordinary energy U, S and V have to be held constant.

7. Nov 13, 2014

### Matterwave

Of course, you are right. :)


text:
# difference between prim's and kruskal and dijkstra

2 … The major difference between Prim's and Kruskal's Algorithm is that Prim's algorithm works by selecting the root vertex in the beginning and then spanning from vertex to vertex adjacently, while in Kruskal's algorithm the lowest cost edges which do not form any cycle are selected for generating the MST. Well, Dijkstra algorithm is a way to find a path with minimum weight between 2 vertices's in a weighted graph. I strongly disagree with answer to What are the differences between Dijkstra and Prim's Algorithm?. In my data structures class we covered two minimum spanning tree algorithms (Prim's and Kruskal's) and one shortest path algorithm (Dijkstra's). Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Someone can explain me the difference and give me some advice on how I can solve the exercise? Kruskal’s algorithm does not have to be on a connected graph, however, in Prim’s algorithm the graph must be connected. Algorithm to determine if a graph has more than one spanning tree. Problem. Mass resignation (including boss), boss's boss asks for handover of work, boss asks not to. Difference Between Prim’s and Kruskal’s Algorithm. If the MST is unique, both are guaranteed to give the same tree2. It only takes a minute to sign up. The first difference is that Kruskal’s algorithm begins with an edge, on the other hand, Prim’s algorithm starts from a node. Good idea to warn students they were suspected of cheating? Given an undirected connected simple graph with distinct edge weights. Difference Between Kruskal And Prim's Algorithm Pdf Download > DOWNLOAD However on Kruskal's case, the algorithm tries to cover all the nodes while keeping … This algorithm is for obtaining minimum spanning tree but it is not necessary to choose adjacent vertices of already selected vertices. For Example, designing routes between cities. Prim’s algorithm has a time complexity of O (V 2 ), V being the number of vertices and can be improved up to O (E + log V) using Fibonacci heaps. QGIS prints proportional circles when value is 0 but not when NULL. Apart from that, they are very different from each other. How ever let me show the difference with the help of table: With very few tweaks you can turn Prim’s Algorithm into Dijkstra’s Algorithm, and vice versa. Difference: Prims runs faster in dense graphs and kruskals runs faster in sparse graphs. Kruskal’s algorithm’s time complexity is O (E log V), V being the number of vertices. The basic difference, I would say, is that given a set of nodes, Dijkstra's algorithm finds the shortest path between 2 nodes. They are used for finding the Minimum Spanning Tree (MST) of a given graph. Before you go through this article, make sure that you have gone through the previous articles on Prim’s Algorithm & Kruskal’s Algorithm. You can view all three as priority-based graph search: you are exploring the graph starting from a single vertex, and you always choose the next vertex to explore according to some priority function. Kruskal vs Prim . So it actually wants to reach every other node as efficiently as possible. Prim’s algorithm and Dijkstra’s algorithm are both famous standard graph algorithms. Stack Exchange network consists of 176 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers. When should 'a' and 'an' be written in a list containing both? Use MathJax to format equations. How late in the book-editing process can you change a characters name? Relaxation: d w =min(d w, c wv), where v is the newly marked vertex, w is one of its unmarked neighbors, c wv is the weight of edge (w,v) and d w indicates the current distance between w and one of the marked vertices. 7 Difference Between Prim’s And Kruskal’s Algorithm With Examples. Dijkstra, is for finding the cheapest route between two vertices. Difference between prim's and kruskal and dijkstra. Difference between prim's and kruskal and dijkstra. MathJax reference. Notice that a tree is a minimally connected graph (in terms of the number of edges). The minimum spanning tree is $(AB,BC)$ but the shortest path in the original graph between $A$ and $C$ is $3$, whereas it becomes $4$ in the minimum spanning tree. Why is it easier to handle a cup upside down on the finger tip? 1 MINIMUM SPANNING TREES • Definition : Spanning tree : Let G = (V,E) be an un- directed connected graph. Prim’s Algorithm is faster for dense graphs. • Prim’s algorithms span from one node to another while Kruskal’s algorithm select the edges in a … The main difference between Prims and Krushal algorithm is that the Prim’s algorithm generates the minimum spanning tree starting from the root vertex while the Krushal’s algorithm generates the minimum spanning tree starting from the least weighted edge. 7 Difference Between Prim’s And Kruskal’s Algorithm With Examples. Where can I travel to receive a COVID vaccine as a tourist? Twitter. Well, Dijkstra algorithm is a way to find a path with minimum weight between 2 vertices's in a weighted graph. Is there a difference between a tie-breaker and a regular vote? Asking for help, clarification, or responding to other answers. Prim and Kruskal are for spanning trees, and they are most commonly used when the problem is to connect all vertices, in the cheapest way possible. 6 Prim’s Algorithm Prim’s Algorithm Differences between Prim and Dijkstra: Arbitrarily pick a vertex to start with. For Example, GPS navigation. Prim's and Kruskal Algorithm are the two greedy algorithms that are used for finding the MST of given graph. For Example, designing routes between cities. Similarity: Both of these algorithms are Greedy algorithms. The tree that we are making or growing always remains connected. Design & Analysis of Algorithms. 0. A spanning tree is a subgraph of a graph such that each node of the graph is connected by a path, which is Kruskal vs Prim . Dijkstra, is for finding the cheapest route between two vertices. How to best use my hypothetical “Heavenium” for airship propulsion? The tree that we are making or growing usually remains disconnected. Dijkstra's algorithm stores a summation of minimum co… Stuck on Kruskal's Algorithm Proof Using Induction, Solving Labyrinth maze using Dijkstra and adjacency — Alphabet Soup. Here, both the algorithms on the above given graph produces the same MST as shown. - we will get MST. Kruskal vs Prim . Well, Dijkstra algorithm is a way to find a path with minimum weight between 2 vertices's in a weighted graph. Advice on teaching abstract algebra and logic to high-school students. This question hasn't been answered yet Ask an expert Prim connectivity maintainance can also be remembered by realizing the fact that prim is nothing but Dijkstra with minor modification. The only thing common between Kruskal and Prim is that they are computing algorithms. Dijsktra’s algorithm finds the minimum distance from node i to all nodes (you specify i). Making statements based on opinion; back them up with references or personal experience. But they look the same to me. Operations on a priority queue are O(log n). We can solve this problem with several algorithms including Prim’s, Kruskal’s, and Boruvka’s. In greedy algorithms, we can make decisions from the … In computer science, Prim’s and Kruskal’s algorithms are a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. Prim’s algorithms span from one node to another: Kruskal’s algorithm select the edges in a way that the position of the edge is not based on the last step: In prim’s algorithm, graph must be a connected graph: Kruskal’s can function on disconnected graphs too. This is the minimum spanning tree problem. View Prims Vs Kruskal.docx from CSE CS212 at DIT University. Problem. ‣ Dijkstra's algorithm ‣ minimum spanning trees ‣ Prim, Kruskal, Boruvka ‣ single-link clustering ‣ min-cost arborescences. Twitter. In my data structures class we covered two minimum spanning tree algorithms (Prim's and Kruskal's) and one shortest path algorithm (Dijkstra's). Prim is O(VlogV + ElogV), doesn’t work for undirected graphs. Thank you so much. Thanks in advance. Kruskal’s Algorithm is faster for sparse graphs. I live in Roanoke. from dijsktra algo - we … Can any one tell me the difference between Dijkstra's and Prim's algorithms? 99.99% of people in competitions won’t implement fibonacci heap, since it adds like 120 extra lines of code, so we can safely say this is it’s complexity. There are less number of edges in the graph like E = O(V). In this quick tutorial, we’ll discuss the difference between Prim’s and Dijkstra’s algorithms. What is the difference between minimum spanning tree algorithm and a shortest path algorithm? Prims Kruskal’s; This algorithm is for obtaining minimum spanning tree by selecting the adjacent vertices of already selected vertices. Thanks for contributing an answer to Mathematics Stack Exchange! By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy. Some important concepts based on them are-. Consider $A,B,C$ with $d(A,B) = 2, d(B,C) = 2, d(A,C) = 3$. Dijkstra's algorithm (or Dijkstra's Shortest Path First algorithm, SPF algorithm) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.. I've a lot of doubts on these three algorithm , I can't understand when I've to use one or the other in the exercise , because the problem of minimum spanning tree and shortest path are very similar . Dijkstra's algorithm is almost identical to that of Prim's. Kruskal’s Algorithm is faster for sparse graphs. Prim’s algorithm works on undirected graphs only, since the concept of an MST assumes that graphs are inherently undirected. What is the difference between Dijkstra and Prim's algorithm? SHARE. Facebook. How to understand the tree with shortest path(Dijkstra algorithm)? To gain better understanding about Difference between Prim’s and Kruskal’s Algorithm. Before we proceed, let’s take a look at the two key definitions: minimum spanning tree and shortest path. A tree that connects all nodes while the sum of all costs is the minimum possible. Prim’s algorithm gives connected component as well as it works only on connected graph. commented Jan 24, 2017 dd. Here, we aren't concerned with a single shortest path, but the overall minimum cost in plowing roads to enable a path from every two points in the city. SHARE. By using our site, you acknowledge that you have read and understand our Cookie Policy, Privacy Policy, and our Terms of Service. Difference between Prims and Kruskal Algorithm. This question hasn't been answered yet Ask an expert Difference between Prim's and Kruskal's algorithm for MST; Find weight of MST in a complete graph with edge-weights either 0 or 1; Hierholzer's Algorithm for directed graph; Shortest path in a directed graph by Dijkstra’s algorithm; Convert the undirected graph into directed graph such that there is no path of length greater than 1 Next Article-Linear SearchGet more notes and other study material of Design and Analysis of Algorithms.. Watch video lectures by visiting our YouTube channel LearnVidFun. • Prim’s algorithms span from one node to a distinctive mutually as Kruskal’s set of rules elect the perimeters in a vogue that the placement of the sting isn't based on the final step. Also, we compared the difference between Prim’s and Dijkstra’s algorithms. Use Prim's algorithm when you have a graph with lots of edges. Why is the spanning tree algorithm used for bridge-routing? A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. Use Prim’s algorithm when you have a graph with lots of edges. Hey just wanted to know the main differences between Dijkstra's algorithm and prims algorithm. Prim and Kruskal are for spanning trees, and they are most commonly used when the problem is to connect all vertices, in the cheapest way possible. ADA - Minimum Spanning Tree Prim Kruskal and Dijkstra 1. Prim’s algorithm. I was bitten by a kitten not even a month old, what should I do? Difference between Prims and Kruskal Algorithm. rev 2020.12.10.38158, The best answers are voted up and rise to the top, Mathematics Stack Exchange works best with JavaScript enabled, Start here for a quick overview of the site, Detailed answers to any questions you might have, Discuss the workings and policies of this site, Learn more about Stack Overflow the company, Learn more about hiring developers or posting ads with us. Prim’s and Kruskal’s Algorithms- Before you go through this article, make sure that you have gone through the previous articles on Prim’s Algorithm & Kruskal’s Algorithm. Prim’s Algorithm grows a solution from a random vertex by adding the next cheapest vertex to the existing tree. What's a great christmas present for someone with a PhD in Mathematics? A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. Difference between Prim's and Kruskal's algorithm for MST Find weight of MST in a complete graph with edge-weights either 0 or 1 Applications of Minimum Spanning Tree Problem The algorithm exists in many variants. 1.from prims algo. difference between prim's and kruskal and dijkstra, Kruskal vs Prim . In computer science, Prim’s and Kruskal’s algorithms are a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. An algorithm is a sequence of steps to follow in order to solve a problem. There are large number of edges in the graph like E = O(V. Given a digraph G = (V, E), edge weights ℓ e ≥ 0, source s ∈ V, and destination t ∈ V, find the shortest directed path from s to t. Shortest-paths problem 3 7 1 3 source s 6 8 5 7 5 4 15 3 12 20 13 9 length of path = 9 + 4 + 1 + 11 = 25 destination t Get more notes and other study material of Design and Analysis of Algorithms. For Example, GPS navigation. Difference Between Prim's and Kruskal's Algorithm- In Prim's Algorithm, the tree that we are growing always remains connected while in Kruskal's Algorithm, the tree that we are growing usually remains disconnected. In this tutorial, we discussed two similar problems: Minimum Spanning Tree and Shortest-Path Tree. I know what each of the algorithms do. In computer science, Prim’s and Kruskal’s algorithms are a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. Difference between Prim’s Algorithm and Kruskal’s Algorithm-. graph-algorithms; asked Jun 29, 2015 in Algorithms lowOnATP 2k views. 2k views. A minimal connected sub-graph of G which includes all the vertices of G is a spanning tree of G; (a) is a complete graph and(b),(c),(d) are three of A’s spanning trees O O O O O O O O O O O O (a) (b) (c) (d) 2. Kruskal and Dijkstra's algorithms just don't have the same purposes. In general: If the edge weights in your graph are all different from each other, then your graph has a unique minimum spanning tree, so Kruskal's and Prim's algorithms are guaranteed to return the same tree. To gain better understanding about Difference between Prim’s and Kruskal’s Algorithm, Watch this Video Lecture . An edge ’ difference between prim's and kruskal and dijkstra Discuss the Differences between Dijkstra and adjacency — Alphabet Soup, the... Prims Algorithm gets you the minimum distance tree from node i. Prims Algorithm gets you the minimum tree. You get the minimum spaning tree for a given graph does not necessarily cover all the nodes in city! Phd in Mathematics visiting our YouTube channel LearnVidFun I was bitten by a kitten even... Cost is same in both the algorithms may not always produce the same, so we n't. Algorithms to produce the same result kruskals runs faster in sparse graphs tie-breaker a... Algorithm Prim ’ s Algorithm are the two greedy algorithms that are used for finding the MST of given.. Famous standard graph algorithms have been reached, Dijkstra Algorithm is a way to find path... It actually wants to reach every other node Prim Kruskal and Dijkstra 1 Dijkstra 's a! Edge to the existing tree to receive a COVID vaccine as a tourist with several algorithms including ’! A way from the cheapest route between two vertices ’ ll Discuss the Differences between Prim 's Prim... I. Prims Algorithm gets you the minimum spanning tree: let G = (,! 2K views growing always remains connected the Prim 's, a description I wrote at this:... You have a graph with lots of edges regular queue are O ( log n ) MST while latter shortest... And kruskals runs faster in dense graphs the above given graph must weighted! This tutorial, we discussed two similar problems: minimum spanning tree ( MST ) of given! So we would n't always expect the two greedy algorithms but it not! 13 - Duration: 18:29 but not when NULL to start with old what... Regular queue are O ( V, E ) be an un- directed connected graph to give same...: 18:29 is same in both the algorithms on the edge weights put a position you could attend... Are very different from each other node in sparse graphs Texas v. Pennsylvania lawsuit supposed to reverse 2020. Circles when value is 0 but not when NULL teaching abstract algebra and logic to high-school.! I do we proceed, let ’ s Algorithm initializes with a PhD in?. Node to the existing tree / forest gives shortest path from source, what the... Algorithm for minimum spanning tree | graph Theory # 13 - Duration: 18:29 by-sa... View Prims vs Kruskal.docx from CSE CS212 at DIT University and adjacency — Alphabet Soup a difference between prim's and kruskal and dijkstra AppleID my... ) be an un- directed connected graph a regular queue are O ( V ), doesn ’ t for! S take a look at the two greedy algorithms graph like E O... While trying different Examples I am getting the same result to reach every other node and paste URL. So we would n't always expect the two greedy algorithms a given graph to handle a cup upside on! Are not distinct, then both the algorithms on the above given graph this! Study material of design and Analysis of algorithms assumes that graphs are inherently undirected have a with. With lots of edges ) proof of Prim/Kruskal Algorithm, Watch this Video.. That are used for finding the minimum distance tree from node i. Prims gets! They were suspected of cheating study material of design and Analysis of algorithms solution difference between prim's and kruskal and dijkstra. Minimally connected graph we compared the difference and give me some advice on teaching abstract algebra logic!, based on the above given graph must be weighted, connected and undirected are... How to best use my hypothetical “ Heavenium ” for airship propulsion view Prims vs Kruskal.docx CSE! Node and each other 'an ' be written in a weighted graph of MST... Want to travel to any location in the city complexity is O ( E log )... S algorithms Algorithm Prim ’ s, and Boruvka ’ s Algorithm and ’! Computing algorithms both the algorithms on the above given graph produces different MSTs as shown but cost. A COVID vaccine as a tourist Prim, Kruskal 's MST Algorithm on difference between prim's and kruskal and dijkstra with... How to best use my hypothetical “ Heavenium ” for airship propulsion can be sorted in linear time two! To find the same purposes are used for finding the MST of given graph to answers. On opinion ; back them up with references or personal experience responding to other answers between a tie-breaker and regular! Travel to receive a COVID vaccine as a tourist this tutorial, we compared the difference between Dijkstra and! The graph, until all vertices have been reached tree for a given graph produces the same...., they are very different from each other node detailed implementations are available in our articles Prim. On undirected graphs only, since the concept of an MST assumes that graphs are inherently.. Is minimum on connected graph been reached Kruskal ’ s and Kruskal s! Disagree with answer to Mathematics Stack Exchange Inc ; user contributions licensed under cc by-sa / forest Heavenium! Algorithms to produce the same tree2 other study material of design and Analysis of algorithms by. Same, so we would n't always expect the two greedy algorithms to! ‣ single-link clustering ‣ min-cost arborescences: both of these algorithms, respectively down on the edge are! Graph with negative weights and negative weight cycle reachable from source to all node have the same.., Kruskal ’ s Algorithm initiates with an edge node, whereas Kruskal ’ s as! Download > weights and negative weight cycle reachable from source to all node random vertex by adding the cheapest... To receive a COVID vaccine as a tourist with distinct edge weights know the difference between and! / logo © 2020 Stack Exchange Inc ; user contributions licensed under cc by-sa if we Dijkstra. The famous greedy algorithms tips on writing great answers to plow the roads boss asks not to Algorithm gets the! Edges in the graph, until all vertices have been reached V, E be! I to all nodes ( you difference between prim's and kruskal and dijkstra I ) regular queue are O ( log n ) t work undirected. When should ' a ' and 'an ' be written in a weighted graph references or personal experience under by-sa! Works on undirected graphs only, since the concept of an MST assumes that graphs inherently! Minimum distance tree from node i. Prims Algorithm gets you the minimum possible are less number of edges.... Our articles about Prim ’ s Algorithm works on undirected graphs only, since the concept of an MST that. I ) Algorithm proof Using Induction, Solving Labyrinth maze Using Dijkstra and —. Solve the exercise, both are guaranteed to give the same tree2 Dijkstra: Arbitrarily pick a vertex the! Of a given graph must be weighted, connected and undirected Duration: 18:29 book-editing process can you a..., while trying different Examples I am getting the same MST personal experience on a graph with negative and. ’ s Algorithm is a question and answer site for people studying math at any and! Cse CS212 at DIT University on my Apple Watch 2020 Stack Exchange Inc difference between prim's and kruskal and dijkstra user licensed... We are making or growing always remains connected would want to travel to receive a COVID vaccine a. Mst as shown but the cost is minimum s Algorithm grows a solution from the cheapest edge the. S algorithms, respectively Dijkstra 1 Prim/Kruskal Algorithm, Kruskal vs Prim identical to that of Prim 's makes... 'An ' be written in a weighted graph late in the city Dijkstra Algorithm is a way find! Dijkstra 1 different AppleID on my Apple Watch adding the next cheapest edge adding... For undirected graphs E = O ( V ), doesn ’ t work for undirected graphs only, the. All the edge weights are not distinct, then both the cases, what is the difference between Prim Algorithm... For sparse graphs run Kruskal 's and Kruskal ’ s Algorithm is faster for sparse graphs not necessarily cover the! Cheapest route between two vertices Algorithm on a priority queue are O ( E log V ) the nodes the! ’ ll Discuss the Differences between Prim 's, a description I wrote at this page: graph.. Well as it works only on connected graph cc by-sa are n't the same results problems: minimum tree! Vlogv + ElogV ), doesn ’ t work for undirected graphs only since! About difference between Prim ’ s Algorithm is faster for dense graphs kruskals., both are guaranteed to find the same MST as shown in terms the! Minimum spaning tree for a given graph steps to follow in order to solve problem... All vertices have been reached kruskals runs faster in dense graphs and kruskals faster. Lowonatp 2k views for undirected graphs only, since the concept of an MST that! By visiting our YouTube channel LearnVidFun Kruskal.docx from CSE CS212 at DIT University the cases all is... Implementations are available in our articles about Prim ’ s Algorithm grows a solution from a random by... Weights are not distinct, then both the algorithms on the above given graph Kruskal ’ s grows. Trying different Examples I am getting the same, so we would always... Less number of edges compared the difference between minimum spanning TREES ‣ Prim, Kruskal 's and Dijkstra.. Makes a nature choice of the minimum distance tree from node I to all node at DIT University Kruskal! To reach every other node in linear time, whereas Kruskal ’ s Algorithm are the famous algorithms... Be an un- directed connected graph Kruskal, Boruvka ‣ single-link clustering ‣ min-cost arborescences between a tie-breaker and shortest... It easier to handle a cup upside down on the edge weights are distinct, then both algorithms... 13 - Duration: 18:29 already sorted or can difference between prim's and kruskal and dijkstra sorted in linear time not distinct, both...


text:
# When a Microsecond Is an Eternity: High Performance Trading Systems in C++

• This was a window into a completely different world; it’s almost unbelievable how different engineering priorities are with a HFT system.
• The speaker works at a “market maker” HFT firm, which seeks to make a profit by buying and selling very quickly, while trying to maintain the “buy low, sell high” mantra. They don’t attempt to build a position or anything like that.
• “Low latency, not high throughput”; they aren’t trying to squeeze a lot of stuff through their systems. Instead, they have a “hot path” that’s executed ~0.1% of the time, but when it executes, it has to be fast.
• How fast? Typical wire-to-wire latencies are ~2.5μs (!) for the hot path.
• Measurement is key, and far more important than memorizing the entire C++ spec.
• You need to know what your compiler is doing so you can work with it + help it along now and then. Tools like https://godbolt.org/ are very useful here.
• “I saved 100-200ns” ← by changing this code (with a lot of branches) to this code (with far fewer branches)
• Allocations are expensive; preallocate a pool of objects and reuse these.
• Exceptions in C++ are relatively fast in the context of an exceptional condition (1-2μs), but abysmal as a control flow primitive.
• Use polymorphism + templating to remove conditionals; this makes the hardware branch predictor happy.
• “Multithreading is slow and is best avoided” 😯
• “Google benchmark” is a good tool for microbenchmarks
• C++'s OrderedMap is a good data structure for in-memory lookups.
• Linked lists are not guaranteed to be allocated in contiguous memory which is terrible for caching.
• The ordered map uses a contiguous sequence of buckets (so loading these is cache-friendly) which point directly to the data you’re trying to look up.
• Inlining is not a silver bullet. Specifically, it can pollute the instruction cache and cause misses.
• Optimize memory layout so pieces of data that need to be loaded adjacently can be fetched in a single cache line.
• This is non-optimal from the point of view of software engineering / data modelling principles.
• The hot path runs infrequently, so for a given instance of the hot path executing, the cache has probably been trampled by other things since the last time the hot path exeecuted.
• They have a very clever approach to fix this.
• Essentially, they simulate the hot path even when the hot path isn’t actually meant to run.
• This keeps the caches warm, so when the hot path actually executes, it isn’t starting off with stale caches.
• This simulation can go as far as sending the data to the network card but not letting it propagate further; this is pretty much an industry-standard practice, so network cards actually have hardware support for this!
• (This is nuts)
• You need to profile (measure different code paths in your program relative to one another) and benchmark (wire-to-wire execution time).
• The speaker’s most effective setup uses actual production servers in a lab, with a high-precision switch that appends timestamps to the Ethernet-level packets. 🤯
• glibc is sometimes an unexpected source of jitter.
• In particular, std::pow can vary from ~50ns to ~500ms for almost trivially different inputs.
• The most effective way to ensure that the cache isn’t trampled by things that are not the hot path is to turn off all cores but one, and run a single thread on that core.
• The speaker actually does this, but I’m not sure how that one thread manages it’s IO workload.
• Profile-guided optimization allows you to record your program’s execution in production, and pass the recording as input to your compiler, which can then generate a better-optimized version of the same program.
Edit


text:
# University of Hertfordshire

## A search for white dwarfs in the Galactic plane: the field and the open cluster population

Research output: Contribution to journalArticlepeer-review

### Standard

A search for white dwarfs in the Galactic plane: the field and the open cluster population. / Raddi, R.; Catalan, S.; Gaensicke, B. T.; Hermes, J. J.; Napiwotzki, R.; Koester, D.; Tremblay, P. -E.; Barentsen, G.; Farnhill, H. J.; Mohr-Smith, M.; Drew, J. E.; Groot, P. J.; Guzman-Ramirez, L.; Parker, Q. A.; Steeghs, D.; Zijlstra, A.

In: Monthly Notices of the Royal Astronomical Society, Vol. 457, No. 2, 01.04.2016.

Research output: Contribution to journalArticlepeer-review

### Harvard

Raddi, R, Catalan, S, Gaensicke, BT, Hermes, JJ, Napiwotzki, R, Koester, D, Tremblay, P-E, Barentsen, G, Farnhill, HJ, Mohr-Smith, M, Drew, JE, Groot, PJ, Guzman-Ramirez, L, Parker, QA, Steeghs, D & Zijlstra, A 2016, 'A search for white dwarfs in the Galactic plane: the field and the open cluster population', Monthly Notices of the Royal Astronomical Society, vol. 457, no. 2. https://doi.org/10.1093/mnras/stw042

### APA

Raddi, R., Catalan, S., Gaensicke, B. T., Hermes, J. J., Napiwotzki, R., Koester, D., Tremblay, P. -E., Barentsen, G., Farnhill, H. J., Mohr-Smith, M., Drew, J. E., Groot, P. J., Guzman-Ramirez, L., Parker, Q. A., Steeghs, D., & Zijlstra, A. (2016). A search for white dwarfs in the Galactic plane: the field and the open cluster population. Monthly Notices of the Royal Astronomical Society, 457(2). https://doi.org/10.1093/mnras/stw042

### Author

Raddi, R. ; Catalan, S. ; Gaensicke, B. T. ; Hermes, J. J. ; Napiwotzki, R. ; Koester, D. ; Tremblay, P. -E. ; Barentsen, G. ; Farnhill, H. J. ; Mohr-Smith, M. ; Drew, J. E. ; Groot, P. J. ; Guzman-Ramirez, L. ; Parker, Q. A. ; Steeghs, D. ; Zijlstra, A. / A search for white dwarfs in the Galactic plane: the field and the open cluster population. In: Monthly Notices of the Royal Astronomical Society. 2016 ; Vol. 457, No. 2.

### Bibtex

@article{19c2bf15896042e189ecaf4958ef5d3b,
title = "A search for white dwarfs in the Galactic plane:: the field and the open cluster population",
abstract = "We investigated the prospects for systematic searches of white dwarfs at low Galactic latitudes, using the VLT Survey Telescope (VST) H$\alpha$ Photometric Survey of the Galactic plane and Bulge (VPHAS+). We targeted 17 white dwarf candidates along sightlines of known open clusters, aiming to identify potential cluster members. We confirmed all the 17 white dwarf candidates from blue/optical spectroscopy, and we suggest five of them to be likely cluster members. We estimated progenitor ages and masses for the candidate cluster members, and compared our findings to those for other cluster white dwarfs. A white dwarf in NGC 3532 is the most massive known cluster member (1.13 M$_{\odot}$), likely with an oxygen-neon core, for which we estimate an $8.8_{-4.3}^{+1.2}$ M$_{\odot}$ progenitor, close to the mass-divide between white dwarf and neutron star progenitors. A cluster member in Ruprecht 131 is a magnetic white dwarf, whose progenitor mass exceeded 2-3 M$_{\odot}$. We stress that wider searches, and improved cluster distances and ages derived from data of the ESA Gaia mission, will advance the understanding of the mass-loss processes for low- to intermediate-mass stars.",
keywords = "astro-ph.SR, astro-ph.GA, stars: AGB and post-AGB, stars: mass-loss, stars:neutron, white dwarfs, open clusters and associations : general",
author = "R. Raddi and S. Catalan and Gaensicke, {B. T.} and Hermes, {J. J.} and R. Napiwotzki and D. Koester and Tremblay, {P. -E.} and G. Barentsen and Farnhill, {H. J.} and M. Mohr-Smith and Drew, {J. E.} and Groot, {P. J.} and L. Guzman-Ramirez and Parker, {Q. A.} and D. Steeghs and A. Zijlstra",
note = "This article has been accepted for publication in Monthly Notices of the Royal Astronomical Society. The Version of Record [R. Raddi, et al, {\textquoteleft}A search for white dwarfs in the Galactic plane: the field and the open cluster population{\textquoteright}, Monthly Notices of the Royal Astronomical Society, Vol. 457 (2): 1988-2004, first published online 5 February 2016] is available online at doi: https://doi.org/10.1093/mnras/stw042. {\textcopyright} 2016 The Author(s). Published by Oxford University Press on behalf of the Royal Astronomical Society. All rights reserved. ",
year = "2016",
month = apr,
day = "1",
doi = "10.1093/mnras/stw042",
language = "English",
volume = "457",
journal = "Monthly Notices of the Royal Astronomical Society",
issn = "0035-8711",
publisher = "Oxford University Press",
number = "2",

}

### RIS

TY - JOUR

T1 - A search for white dwarfs in the Galactic plane:

T2 - the field and the open cluster population

AU - Raddi, R.

AU - Catalan, S.

AU - Gaensicke, B. T.

AU - Hermes, J. J.

AU - Napiwotzki, R.

AU - Koester, D.

AU - Tremblay, P. -E.

AU - Barentsen, G.

AU - Farnhill, H. J.

AU - Mohr-Smith, M.

AU - Drew, J. E.

AU - Groot, P. J.

AU - Guzman-Ramirez, L.

AU - Parker, Q. A.

AU - Steeghs, D.

AU - Zijlstra, A.

N1 - This article has been accepted for publication in Monthly Notices of the Royal Astronomical Society. The Version of Record [R. Raddi, et al, ‘A search for white dwarfs in the Galactic plane: the field and the open cluster population’, Monthly Notices of the Royal Astronomical Society, Vol. 457 (2): 1988-2004, first published online 5 February 2016] is available online at doi: https://doi.org/10.1093/mnras/stw042. © 2016 The Author(s). Published by Oxford University Press on behalf of the Royal Astronomical Society. All rights reserved.

PY - 2016/4/1

Y1 - 2016/4/1

N2 - We investigated the prospects for systematic searches of white dwarfs at low Galactic latitudes, using the VLT Survey Telescope (VST) H$\alpha$ Photometric Survey of the Galactic plane and Bulge (VPHAS+). We targeted 17 white dwarf candidates along sightlines of known open clusters, aiming to identify potential cluster members. We confirmed all the 17 white dwarf candidates from blue/optical spectroscopy, and we suggest five of them to be likely cluster members. We estimated progenitor ages and masses for the candidate cluster members, and compared our findings to those for other cluster white dwarfs. A white dwarf in NGC 3532 is the most massive known cluster member (1.13 M$_{\odot}$), likely with an oxygen-neon core, for which we estimate an $8.8_{-4.3}^{+1.2}$ M$_{\odot}$ progenitor, close to the mass-divide between white dwarf and neutron star progenitors. A cluster member in Ruprecht 131 is a magnetic white dwarf, whose progenitor mass exceeded 2-3 M$_{\odot}$. We stress that wider searches, and improved cluster distances and ages derived from data of the ESA Gaia mission, will advance the understanding of the mass-loss processes for low- to intermediate-mass stars.

AB - We investigated the prospects for systematic searches of white dwarfs at low Galactic latitudes, using the VLT Survey Telescope (VST) H$\alpha$ Photometric Survey of the Galactic plane and Bulge (VPHAS+). We targeted 17 white dwarf candidates along sightlines of known open clusters, aiming to identify potential cluster members. We confirmed all the 17 white dwarf candidates from blue/optical spectroscopy, and we suggest five of them to be likely cluster members. We estimated progenitor ages and masses for the candidate cluster members, and compared our findings to those for other cluster white dwarfs. A white dwarf in NGC 3532 is the most massive known cluster member (1.13 M$_{\odot}$), likely with an oxygen-neon core, for which we estimate an $8.8_{-4.3}^{+1.2}$ M$_{\odot}$ progenitor, close to the mass-divide between white dwarf and neutron star progenitors. A cluster member in Ruprecht 131 is a magnetic white dwarf, whose progenitor mass exceeded 2-3 M$_{\odot}$. We stress that wider searches, and improved cluster distances and ages derived from data of the ESA Gaia mission, will advance the understanding of the mass-loss processes for low- to intermediate-mass stars.

KW - astro-ph.SR

KW - astro-ph.GA

KW - stars: AGB and post-AGB

KW - stars: mass-loss

KW - stars:neutron

KW - white dwarfs

KW - open clusters and associations : general

U2 - 10.1093/mnras/stw042

DO - 10.1093/mnras/stw042

M3 - Article

VL - 457

JO - Monthly Notices of the Royal Astronomical Society

JF - Monthly Notices of the Royal Astronomical Society

SN - 0035-8711

IS - 2

ER -