Information Processing

Wednesday, June 30, 2021

Six Ways From Sunday: Tucker vs NSA

Chuck Schumer: You take on the intelligence community, they have six ways from Sunday to get back at you.

Tucker Carlson has potential as a politician -- there is at least a small chance that someday he'll be POTUS. The intelligence services are, I am sure, very interested in any kompromat they can acquire on him for future use. You mean foreign intel services? No, I mean our intel services :-(

Clarification, from comments:

The post is not primarily about Tucker. It's about intel services spying on American citizens.

Most importantly, Tucker's story is credible: some whistleblower saw intercepted Tucker emails and contacted him to let him know he is under surveillance. But as anyone paying attention knows, we are ALL under surveillance due to "bulk collection" revealed many years ago, e.g., by Snowden. The Rogers saga and FISC report show that this bulk-collected data is not very well protected from intel agency types who want to have a peek at it...

Re: bulk collection, non-denial denials ("not an intelligence target of the Agency" ha ha), see

Wikipedia: According to a report in The Washington Post in July 2014, relying on information furnished by Snowden, 90% of those placed under surveillance in the U.S. are ordinary Americans, and are not the intended targets. The newspaper said it had examined documents including emails, message texts, and online accounts, that support the claim.

See Twilight Struggles in a Wilderness of Mirrors: Admiral Mike Rogers, the NSA, and Obama-era Political Spying.

Below is a Rogers timeline covering illegal spying using NSA data. This illegal use of data is a matter of record -- undisputed, but also largely unreported. The FISC (FISA court) report on this illegal use of data appeared in April 2017; the author is Rosemary Collyer, the head FISA judge. The report was originally classified Top Secret but was later declassified and released with redactions. Collyer uses the phrase "institutional lack of candor" when referring to behavior of federal agencies in their dealings with FISC over this issue. ...

The court learned in October 2016 that analysts ... were conducting prohibited database searches “with much greater frequency than had previously been disclosed to the court.” The forbidden queries were searches of Upstream Data using US-person identifiers. The report makes clear that as of early 2017 NSA Inspector General did not even have a good handle on all the ways that improper queries could be made to the system. ...

March 2016 – NSA Director Rogers becomes aware of improper access to raw FISA data.

April 2016 – Rogers orders the NSA compliance officer to run a full audit on 702 NSA compliance.

April 18 2016 – Rogers shuts down FBI/NSD contractor access to the FISA Search System.

Mid-October 2016 – DNI Clapper submits a recommendation to the White House that Director Rogers be removed from the NSA.

October 20 2016 – Rogers is briefed by the NSA compliance officer on the Section 702 NSA compliance audit and “About” query violations.

October 21 2016 – Rogers shuts down all “About" query activity. Rogers reports the activity to DOJ and prepares to go before the FISA Court.

October 21 2016 – DOJ & FBI seek and receive a Title I FISA probable cause order authorizing electronic surveillance on Carter Page from the FISC. At this point, the FISA Court is unaware of the Section 702 violations.

October 24 2016 – Rogers verbally informs the FISA Court of Section 702(17) violations.

October 26 2016 – Rogers formally informs the FISA Court of 702(17) violations in writing.

November 17 2016 (morning) – Rogers travels to meet President-Elect Trump and his Transition Team in Trump Tower. Rogers does not inform DNI James Clapper.

November 17 2016 (evening) – Trump Transition Team announces they are moving all transition activity to Trump National Golf Club in New Jersey.

I was recently in a Zoom meeting on geopolitics that included Admiral Rogers. I wanted to ask him privately about the above. Perhaps someday I'll get the chance.

Caption: NSA Director Rogers describes to Congress how little privacy Americans have from government surveillance.

Alternate Caption: NSA Director Rogers tells Congress how much legal oversight remains over the activities of intel services.

Tuesday, June 29, 2021

Machine Learning Prediction of Biomarkers from SNPs and of Disease Risk from Biomarkers in the UK Biobank (published version)

This is the published version of our MedRxiv preprint discussed back in April 2021. It is in the special issue Application of Genomic Technology in Disease Outcome Prediction of the journal Genes.

There is a lot in this paper: genomic prediction of important biomarkers (e.g., lipoprotein A, mean platelet (thrombocyte) volume, bilirubin, platelet count), prediction of important disease risks from biomarkers (novel ML in a ~65 dimensional space) with potential clinical applications. As is typical, genomic predictors trained in a European ancestry population perform less well in distant populations (e.g., S. Asians, E. Asians, Africans). This is probably due to different SNP LD (correlation) structure across populations. However predictors of disease risk using directly measured biomarkers do not show this behavior -- they can be applied even to distant ancestry groups.

The referees did not like our conditional probability notation:

( biomarkers | SNPs ) and ( disease risk | biomarkers )

So we ended up with lots of acronyms to refer to the various predictors.

Some of the biomarkers identified by ML as important for predicting specific disease risk are not familiar to practitioners and have not been previously discussed (as far as we could tell from the literature) as relevant to that specific disease. One medical school professor and practitioner, upon seeing our results, said he would in future add several new biomarkers to routine blood tests ordered for his patients.

Machine Learning Prediction of Biomarkers from SNPs and of Disease Risk from Biomarkers in the UK Biobank

Erik Widen 1,*,Timothy G. Raben 1, Louis Lello 1,2,* and Stephen D. H. Hsu 1,2

1 Department of Physics and Astronomy, Michigan State University, 567 Wilson Rd, East Lansing, MI 48824, USA

2 Genomic Prediction, Inc., 675 US Highway One, North Brunswick, NJ 08902, USA

*Authors to whom correspondence should be addressed.

Academic Editor: Sulev Koks

Genes 2021, 12(7), 991; https://doi.org/10.3390/genes12070991 (registering DOI)

Received: 30 March 2021 / Revised: 22 June 2021 / Accepted: 23 June 2021 / Published: 29 June 2021

(This article belongs to the Special Issue Application of Genomic Technology in Disease Outcome Prediction)

Abstract

We use UK Biobank data to train predictors for 65 blood and urine markers such as HDL, LDL, lipoprotein A, glycated haemoglobin, etc. from SNP genotype. For example, our Polygenic Score (PGS) predictor correlates ∼0.76 with lipoprotein A level, which is highly heritable and an independent risk factor for heart disease. This may be the most accurate genomic prediction of a quantitative trait that has yet been produced (specifically, for European ancestry groups). We also train predictors of common disease risk using blood and urine biomarkers alone (no DNA information); we call these predictors biomarker risk scores, BMRS. Individuals who are at high risk (e.g., odds ratio of >5× population average) can be identified for conditions such as coronary artery disease (AUC∼0.75), diabetes (AUC∼0.95), hypertension, liver and kidney problems, and cancer using biomarkers alone. Our atherosclerotic cardiovascular disease (ASCVD) predictor uses ∼10 biomarkers and performs in UKB evaluation as well as or better than the American College of Cardiology ASCVD Risk Estimator, which uses quite different inputs (age, diagnostic history, BMI, smoking status, statin usage, etc.). We compare polygenic risk scores (risk conditional on genotype: PRS) for common diseases to the risk predictors which result from the concatenation of learned functions BMRS and PGS, i.e., applying the BMRS predictors to the PGS output.

Figure 11. The ASCVD BMRS and the ASCVD Risk Estimator both make accurate risk predictions but with partially complementary information. (Upper left): Predicted risk by BMRS, the ASCVD Risk Estimator and a PRS predictor were binned and compared to the actual disease prevalence within each bin. The gray 1:1 line indicates perfect prediction. ... The ASCVD Risk Estimator was applied to 340k UKB samples while the others were applied to an evaluation set of 28k samples, all of European ancestry. (Upper right) shows a scatter plot and distributions of the risk predicted by BMRS versus the risk predicted by the ASCVD Risk Estimator for the 28k Europeans in the evaluation set. The BMRS distribution has a longer tail of high predicted risk, providing the tighter confidence interval in this region. The left plot y-axis is the actual prevalence within the horizontal and vertical cross-sections, as illustrated with the shaded bands corresponding to the hollow squares to the left. Notably, both predictors perform well despite the differences in assigned stratification. The hexagons are an overlay of the (lower center) heat map of actual risk within each bin (numbers are bin sizes). Both high risk edges have varying actual prevalence but with a very strong enrichment when the two predictors agree.

Sunday, June 27, 2021

Othram CEO David Mittelman interview with Razib Khan

Razib Khan interviews Othram CEO David Mittelman.

See Othram: the future of DNA forensics for some lab photos and analysis of relative identification via DNA database, the legal status of large databases (23andMe, Ancestry), etc.

Fun fact: David is a serious powerlifter :-)

I've done a lot of things in science, but I get a unique kind of personal satisfaction every time Othram solves a case! Of course, this is happening so often now that I can barely keep track.

Saturday, June 19, 2021

LEO SAR, hypersonics, and the death of the naval surface ship

Duh... Let's spend ~$10B each for new aircraft carriers that can be easily monitored from space and attacked using hypersonic missiles.

Sure, in a real war with a peer competitor we'll have to hide them far from the conflict zone. But they're great for intimidating small countries...

Monday, June 14, 2021

Japan and The Quad (Red Line geostrategy podcast)

I recommend this episode of The Red Line geostrategy podcast: Japan and The Quad.

Serious analysts from the Asia-Pacific region (e.g., Australia, India, Japan, etc.) are often much better than their US counterparts. US analysts tend to misperceive local political and economic realities, and can be captives of Washington DC groupthink (e.g., about weapons systems like aircraft carriers or the F35 or missile defense).

For example, Australian analysts acknowledged the vulnerability of US aircraft carriers to PRC ASBM and cruise missiles well before it became common for US analysts to openly admit the problem. The earliest technical analysis I could find of PRC satellite capability to track US surface ships in the Pacific came from an Indian military think tank (see maps below), at a time when many US "experts" denied that it was possible.

In this podcast Japan's reliance on sea lanes for energy, food, and raw materials is given proper emphasis. Japan imports ~60% of its food calories and essentially all of its oil. The stituation is similar for S. Korea and Taiwan. It is important to note that blocking sea transport to Taiwan and Japan does not require PLAN blue water dominance. ASBM and cruise missiles which threaten aircraft carriers can also hold oil tankers and global shipping at risk from launch sites which are on or near the Asian mainland. Missile + drone + AI/ML technology completely alters the nature of sea blockade, but most strategic planners do not yet realize this. Serious conflict in this region would likely wreak havoc on the economies of Taiwan, S. Korea, and Japan.

Red Line: ... In seeking to counter an ever-expanding China, Tokyo is turning abroad in search of allies. Key to this is the recent revival of "The Quad", a strategic dialogue between the US, Australia, Japan and India. Will it be enough to counter their rising neighbour across the East China Sea? Is this the first step to creating an "Asian NATO", and how will China respond?

Guests:

Owen Swift

Geopolitics and defence analyst specialising in Australian & East Asian Defence Written with organisations including The Australian Strategic Policy Institute and Monash University. Senior Producer and resident Asia-Pacific expert at The Red Line

John Nilsson-Wright

Senior Lecturer on Japanese Geopolitics and International Relations for Cambridge University. Senior Research Fellow for Northeast Asia for Chatham House. Author of the book Unequal Allies about the post-war relationship between Japan and the United States.

John Coyne

Head of the Northern Australia Strategic Policy Centre at the Australian Strategic Policy Institute (ASPI). Head of Strategic Policing and Law Enforcement at ASPI. One of the most trusted experts when it comes to the dynamics of East Asia for Australia and the United States.

Part 1: The Return from Armageddon (02:52) Owen Swift overviews Japan's place in East Asia and the fundamental geographic challenges that inform its geopolitics. We tackle Japan's inability to domestically provide the resources and food that its population needs, and how it has historically dealt with this insecurity. The consequences of World War 2 wreaked havoc on Japan's economy, political system and territorial holdings. We analyse the short and long term consequences of this, and seek to understand why it was that Japan took a positive view of the US occupation, comparing it to the option of a possible partial USSR occupation. In the 1980s some thought Japan was on a path to overtake the US economically. While that hasn't come to pass, we look at what it was that made Japan's economic miracle, and the effect that US involvement has today. We look at domestic issues in Japan, including the drastic demographic decline, their ongoing 'defensive only' posture, and the policy options on the table for balancing against the rise of China. Finally we overview Japan's involvement in the Asia-Pacific region as a whole, analysing who it has the best relations with. We look at the extensive investments and infrastructure development Japan is undertaking in ASEAN states, and its cooperation with India and Australia in recent years.

Part 2: The Grand Dilemma (17:56) John Nilsson-Wright helps us understand the fundamental shifts in Japanese politics and foreign policy, including Article 9, the tension between the Yoshida doctrine, public opinion and US pressure within Japan, and the country's re-entry into the sphere of great power competition. We examine the extent of Japan's military presence in the Indo-Pacific; looking at its exercises with other powers and the concerns its neighbours have, some of whom still bear significant scars from World War 2. South Korea's relationship with Japan is one that, on the surface, seems like it should be closer than it is. We analyse why it is that despite their mutual interest in countering North Korea and China, their close geography and both being under the US umbrella, the two states have been unable to overcome enormous domestic resentment and historic scars. Japan's constitution has very tight constraints on what it can do militarily. Nilsson-Wright helps us understand the details of these restrictions and their history over the past few decades. We look at how the legal interpretation of the article has changed as Japan's needs have changed. We also look at Japan's expanding concept of national interest, which began as a purely defensive, geographically limited concept, but that has continued to expand in recent years. We contrast that with the difficulty the government has had with domestic views of Japan's role on the global stage. We tackle territorial issues including the Kuril and Sakhalin Islands, and look at Japan's role in a potential Taiwanese conflict.

Part 3: A United Front? (43:48) John Coyne a takes us through the details of the Quad, and the roles that its constituent members play. We look at Japan's re-examination of their supply chains, their development of strategic depth and the recent news that they are considering abolishing the 1% of GDP cap on military spending. Coyne helps us understand what the Quad actually is - It is not and does not seek to be an Asian NATO - just as ASEAN is not an Asian EU. We look at what the limitations are for each of the states involved, particularly India. We look at the actual relationships and cooperation that has been seen between Quad members. With Japan's newfound willingness to be involved in military operations, we examine how closely they will work with Australia, India and the United States, and the extent to which the Quad is more than just symbolic. We then turn to China's response. Is China likely to seek a grouping like the Quad in opposition to it? Can the Quad actually contain China or its navy in any practical sense? What will China do if cooperation tightens? We look at how China has already sought to hit back, targeting Australia in particular with the "14 Grievances", which were delivered as a consequence of the deterioration of their relationship. Australia's membership and participation in the Quad is a key part of this deterioration. Finally we look at how the Quad members have worked to strategically separate from China, such as Japan's work to defeat China's monopoly on the rare earths industry.

The map below appeared in the 2017 blog post On the military balance of power in the Western Pacific.

Here is another map:

Authors: Professor S. Chandrashekar and Professor Soma Perumal

We can state with confidence that the Yaogan satellite constellation and its associated ASBM system provide visible proof of Chinese intentions and capabilities to keep ACG strike groups well away from the Chinese mainland.

Though the immediate purpose of the system is to deter the entry of a hostile aircraft carrier fleet into waters that directly threatens its security interests especially during a possible conflict over Taiwan, the same approach can be adopted to deter entry into other areas of strategic interest.

Viewed from this perspective the Chinese do seem to have in place an operational capability for denying or deterring access into areas which it sees as crucial for preserving its sovereignty and security.

Bonus: This political cartoon about the G7 meeting has been widely shared in the sinosphere. Some of the esoteric meaning may be lost on a US audience, but see here for an explanation. Note the device on the table which turns toilet paper into US dollars. The Japanese dog is serving radioactive water to the co-conspirators. Italy, the BRI participant, refuses the drink. France and Germany seem to be thinking about it carefully. Who is the little frog? (Hint: NTD)

Sunday, June 13, 2021

An Inconvenient Minority: The Attack on Asian American Excellence and the Fight for Meritocracy (Kenny Xu)

Kenny Xu is a brave young man. His new book An Inconvenient Minority: The Attack on Asian American Excellence and the Fight for Meritocracy expertly documents a number of unpleasant facts about American society that most major media outlets, education leaders, and social justice advocates have been obfuscating or outright suppressing for decades.

1. Asian Americans (not foreign students from Asia, but individuals of Asian heritage who are US citizens or permanent residents) have been discriminated against in admission to elite institutions of higher education for over 30 years.

To put it bluntly, Asian Americans must, on average, outperform all other groups in order to have an equal chance of admission to universities like Harvard or Yale. If one were to replace Asian Americans with Jews in the previous sentence, it would describe the situation in the early 20th century. Looking back, we are rightfully ashamed and outraged at the conduct of elite universities during this period. Future Americans, and observers all over the world, will eventually have the same reaction to how Asian Americans are treated today by these same institutions.

2. Asian American success, e.g., as measured using metrics such as income, wealth, or education, is problematic for simplistic narratives that emphasize race and "white supremacy" over a more realistic and multifaceted analysis of American society.

3. Efforts to guarantee equal outcomes, as opposed to equal opportunities, are anti-meritocratic and corrosive to social cohesion, undermine basic notions of fairness, and handicap the United States in scientific and technological competition with other nations.

The Table of Contents, reproduced below, gives an idea of the important topics covered. Xu had an insider's view of the Students for Fair Admission v. Harvard trial, now awaiting appeal to the Supreme Court. He also describes the successful effort by a grass roots coalition of Asian Americans to defeat CA Proposition 16, which would have reinstated racial preferences in the public sector (including college admissions) which were prohibited by Proposition 209 in 1996.

Over the years I have had many conversations on this topic with well-meaning (but often poorly informed) parents of all ethnic and cultural backgrounds. I cannot help but ask these people

Are you OK with discrimination against your child? What did they do to deserve it?

Are you going to let virtue-signaling administrators at the university devalue the hard work and hard-won accomplishments of your son or daughter? Are you going to do anything about it?

and I cannot help but think

If you won't do anything about it, then f*ck you. Your kids deserve better parents.

Kenny calls it a Fight for Meritocracy. That's what it is -- a fight. Don't forget that Meritocracy is just a fancy word for fairness. It's a fight for your kid, and all kids, to be treated fairly.

I highly recommend the book. These issues are of special concern to Asian Americans, but should be of interest to anyone who wants to know what is really happening in American education today.

Related posts: discrimination against Asian Americans at elite US universities, on meritocracy, and UC faculty report on the use of SAT in admissions.

Thursday, June 03, 2021

Macroscopic Superpositions in Isolated Systems (talk video + slides)

This is video of a talk based on the paper

Macroscopic Superpositions in Isolated Systems

R. Buniy and S. Hsu

arXiv:2011.11661, to appear in Foundations of Physics

For any choice of initial state and weak assumptions about the Hamiltonian, large isolated quantum systems undergoing Schrodinger evolution spend most of their time in macroscopic superposition states. The result follows from von Neumann's 1929 Quantum Ergodic Theorem. As a specific example, we consider a box containing a solid ball and some gas molecules. Regardless of the initial state, the system will evolve into a quantum superposition of states with the ball in macroscopically different positions. Thus, despite their seeming fragility, macroscopic superposition states are ubiquitous consequences of quantum evolution. We discuss the connection to many worlds quantum mechanics.

Slides for the talk.

See this earlier post about the paper:

It may come as a surprise to many physicists that Schrodinger evolution in large isolated quantum systems leads generically to macroscopic superposition states. For example, in the familiar Brownian motion setup of a ball interacting with a gas of particles, after sufficient time the system evolves into a superposition state with the ball in macroscopically different locations. We use von Neumann's 1929 Quantum Ergodic Theorem as a tool to deduce this dynamical result.

The natural state of a complex quantum system is a superposition ("Schrodinger cat state"!), absent mysterious wavefunction collapse, which has yet to be fully defined either in logical terms or explicit dynamics. Indeed wavefunction collapse may not be necessary to explain the phenomenology of quantum mechanics. This is the underappreciated meaning of work on decoherence dating back to Zeh and Everett. See talk slides linked here, or the introduction of this paper.

We also derive some new (sharper) concentration of measure bounds that can be applied to small systems (e.g., fewer than 10 qubits).

Related posts:

Classics on the arxiv: von Neumann and the foundations of quantum statistical mechanics

Pure State Quantum Thermalization: from von Neumann to the Lab

Entanglement and fast thermalization in heavy ion collisions

Wednesday, May 26, 2021

How Dominic Cummings And The Warner Brothers Saved The UK

Photo above shows the white board in the Prime Minister's office which Dominic Cummings and team (including the brothers Marc and Ben Warner) used to convince Boris Johnson to abandon the UK government COVID herd immunity plan and enter lockdown. Date: March 13 2020.

Only now can the full story be told. In early 2020 the UK government had a COVID herd immunity plan in place that would have resulted in disaster. The scientific experts (SAGE) advising the government strongly supported this plan -- there are public, on the record briefings to this effect. These are people who are not particularly good at order of magnitude estimates and first-principles reasoning.

Fortunately Dom was advised by the brothers Marc and Ben Warner (both physics PhDs, now working in AI and data science), DeepMind founder Demis Hassabis, Fields Medalist Tim Gowers, and others. In the testimony (see ~23m, ~35m, ~1h02m, ~1h06m in the video below) he describes the rather dramatic events that led to a switch from the original herd immunity plan to a lockdown Plan B. More details in this tweet thread.

I checked my emails with Dom during February and March, and they confirm his narrative. I wrote the March 9 blog post Covid-19 Notes in part for Dom and his team, and I think it holds up over time. Tim Gowers' document reaches similar conclusions.

Seven hours of riveting Dominic Cummings testimony from earlier today.

Transcript.

Shorter summary video (Channel 4). Summary live-blog from the Guardian.

This is a second white board used in the March 14 meeting with Boris Johnson:

Saturday, May 22, 2021

Feynman Lectures on the Strong Interactions (Jim Cline notes)

Professor James Cline (McGill University) recently posted a set of lecture notes from Feynman's last Caltech course, on quantum chromodynamics. Cline, then a graduate student, was one of the course TAs and the notes were meant to be assembled into a monograph. Thanks to Tim Raben for pointing these out to me.

The content seems a bit more elementary than in John Preskill's Ph230abc, a special topics course on QCD taught in 1983-4. I still consider John's notes to be one of the best overviews of nonperturbative aspects of QCD, a rather deep subject. However as Cline remarks there is unsurprisingly something special about the lectures: Feynman was an inspiring teacher, presenting everything in an incisive and fascinating way, that obviously had his own mark on it.

The material on QFT in non-integer spacetime dimensions is, as far as I know, original to Feynman. Dimensional regularization of gauge theory was popularized by 't Hooft and Veltman, but the analytic continuation to d = 4 - ε is specifc to the loop integrals (i.e., concrete mathematical expressions) that appear in perturbation theory. Here Feynman is, more ambitiously, exploring whether the quantum gauge theory itself can be meaningfully extended to a non-integer number of spacetime dimensions.

Feynman Lectures on the Strong Interactions

Richard P. Feynman, James M. Cline

These twenty-two lectures, with exercises, comprise the extent of what was meant to be a full-year graduate-level course on the strong interactions and QCD, given at Caltech in 1987-88. The course was cut short by the illness that led to Feynman's death. Several of the lectures were finalized in collaboration with Feynman for an anticipated monograph based on the course. The others, while retaining Feynman's idiosyncrasies, are revised similarly to those he was able to check. His distinctive approach and manner of presentation are manifest throughout. Near the end he suggests a novel, nonperturbative formulation of quantum field theory in D dimensions. Supplementary material is provided in appendices and ancillary files, including verbatim transcriptions of three lectures and the corresponding audiotaped recordings.

The image below is from some of Feynman's handwritten notes (in this case, about the Gribov ambiguity in Fadeev-Popov gauge fixing) that Cline included in the manuscript. There are also links to audio from some of the lectures. As in some earlier notebooks, Feynman sometimes writes "guage" instead of gauge.

Sunday, May 16, 2021

Ditchley Foundation meeting: China Today and Tomorrow

China Today and Tomorrow

20 MAY 2021 - 21 MAY 2021

This Ditchley conference will focus on China, its internal state and sense of self today, its role in the region and world, and how these might evolve in years to come.

There are broadly two current divergent narratives about China. The first is that China’s successful response to the pandemic has accelerated China’s ascent to be the world’s pre-eminent economic power. The Made in China 2025 strategy will also see China take the lead in some technologies beyond 5G, become self-sufficient in silicon chip production and free itself largely of external constraints on growth. China’s internal market will grow, lessening dependence on exports and that continued growth will maintain the bargain between the Chinese people and the Chinese Communist Party through prosperity and stability. Retaining some elements of previous Chinese strategy though, this confidence is combined with a degree of humility: China is concerned with itself and its region, not becoming a global superpower or challenging the US. Economic supremacy is the aim but military strategy remains focused on defence, not increasing international leverage or scope of action.

The second competing narrative is that China’s position is more precarious than it appears. The Belt and Road Initiative will bring diplomatic support from client countries but not real economic gains. Human rights violations will damage China abroad. Internally the pressures on natural resources will prove hard to sustain. Democratic and free-market innovation, combined with a bit more industrial strategy, will outstrip China’s efforts. Careful attention to supply chains in the West will meanwhile reduce critical reliance on China and curb China’s economic expansion. This perceived fragility is often combined though with a sense of heightened Chinese ambition abroad, not just through the Belt and Road Initiative but in challenging the democratic global norms established since 1989 by presenting technologically-enabled and effective authoritarian rule as an alternative model for the world, rather than just a Chinese solution.

What is the evidence today for where we should settle between these narratives? What trends should we watch to determine likely future results? ...

[Suggested background reading at link above.]

Unfortunately this meeting will be virtual. The video below gives some sense of the unique charm of in-person workshops at Ditchley.

See also this 2020 post about an earlier Ditchley meeting I attended: World Order Today

... analysis by German academic Gunnar Heinsohn. Two of his slides appear below.

1. It is possible that by 2050 the highly able STEM workforce in PRC will be ~10x larger than in the US and comparable to or larger than the rest of the world combined. Here "highly able" means roughly top few percentile math ability in developed countries (e.g., EU), as measured by PISA at age 15.

[ It is trivial to obtain this kind of estimate: PRC population is ~4x US population and fraction of university students in STEM is at least ~2x higher. Pool of highly able 15 year olds as estimated by PISA or TIMMS international testing regimes is much larger than in US, even per capita. Heinsohn's estimate is somewhat high because he uses PISA numbers that probably overstate the population fraction of Level 6 kids in PRC. Current PISA studies disproportionately sample from more developed areas of China. At bottom (asterisk) he uses results from Taiwan/Macau that give a smaller ~20x advantage of PRC vs USA. My own ~10x estimate is quite conservative in comparison. ]

2. The trajectory of international patent filings shown below is likely to continue.

Wednesday, May 12, 2021

Neural Tangent Kernels and Theoretical Foundations of Deep Learning

A colleague recommended this paper to me recently. See also earlier post Gradient Descent Models Are Kernel Machines.

Neural Tangent Kernel: Convergence and Generalization in Neural Networks

Arthur Jacot, Franck Gabriel, Clément Hongler

At initialization, artificial neural networks (ANNs) are equivalent to Gaussian processes in the infinite-width limit, thus connecting them to kernel methods. We prove that the evolution of an ANN during training can also be described by a kernel: during gradient descent on the parameters of an ANN, the network function fθ (which maps input vectors to output vectors) follows the kernel gradient of the functional cost (which is convex, in contrast to the parameter cost) w.r.t. a new kernel: the Neural Tangent Kernel (NTK). This kernel is central to describe the generalization features of ANNs. While the NTK is random at initialization and varies during training, in the infinite-width limit it converges to an explicit limiting kernel and it stays constant during training. This makes it possible to study the training of ANNs in function space instead of parameter space. Convergence of the training can then be related to the positive-definiteness of the limiting NTK. We prove the positive-definiteness of the limiting NTK when the data is supported on the sphere and the non-linearity is non-polynomial. We then focus on the setting of least-squares regression and show that in the infinite-width limit, the network function fθ follows a linear differential equation during training. The convergence is fastest along the largest kernel principal components of the input data with respect to the NTK, hence suggesting a theoretical motivation for early stopping. Finally we study the NTK numerically, observe its behavior for wide networks, and compare it to the infinite-width limit.

The results are remarkably well summarized in the wikipedia entry on Neural Tangent Kernels:

For most common neural network architectures, in the limit of large layer width the NTK becomes constant. This enables simple closed form statements to be made about neural network predictions, training dynamics, generalization, and loss surfaces. For example, it guarantees that wide enough ANNs converge to a global minimum when trained to minimize an empirical loss. ...

An Artificial Neural Network (ANN) with scalar output consists in a family of functions $f\left(\cdot ,\theta \right):\mathbb {R} ^{n_{\mathrm {in} }}\to \mathbb {R}$ parametrized by a vector of parameters $\theta \in \mathbb {R} ^{P}$ .
The Neural Tangent Kernel (NTK) is a kernel $\Theta :\mathbb {R} ^{n_{\mathrm {in} }}\times \mathbb {R} ^{n_{\mathrm {in} }}\to \mathbb {R}$ defined by
$\Theta \left(x,y;\theta \right)=\sum _{p=1}^{P}\partial _{\theta _{p}}f\left(x;\theta \right)\partial _{\theta _{p}}f\left(y;\theta \right).$ In the language of kernel methods, the NTK $\Theta$ is the kernel associated with the feature map $\left(x\mapsto \partial _{\theta _{p}}f\left(x;\theta \right)\right)_{p=1,\ldots ,P}$

For a dataset $\left(x_{i}\right)_{i=1,\ldots ,n}\subset \mathbb {R} ^{n_{\mathrm {in} }}$ with scalar labels $\left(z_{i}\right)_{i=1,\ldots ,n}\subset \mathbb {R}$ and a loss function $c:\mathbb {R} \times \mathbb {R} \to \mathbb {R}$ , the associated empirical loss, defined on functions $f:\mathbb {R} ^{n_{\mathrm {in} }}\to \mathbb {R}$ , is given by
${\mathcal {C}}\left(f\right)=\sum _{i=1}^{n}c\left(f\left(x_{i}\right),z_{i}\right).$
When training the ANN $f\left(\cdot ;\theta \right):\mathbb {R} ^{n_{\mathrm {in} }}\to \mathbb {R}$ is trained to fit the dataset (i.e. minimize ${\mathcal {C}}$ ) via continuous-time gradient descent, the parameters $\left(\theta \left(t\right)\right)_{t\geq 0}$ evolve through the ordinary differential equation:
$\partial _{t}\theta \left(t\right)=-\nabla {\mathcal {C}}\left(f\left(\cdot ;\theta \right)\right).$
During training the ANN output function follows an evolution differential equation given in terms of the NTK:
$\partial _{t}f\left(x;\theta \left(t\right)\right)=-\sum _{i=1}^{n}\Theta \left(x,x_{i};\theta \right)\partial _{w}c\left(w,z_{i}\right){\Big |}_{w=f\left(x_{i};\theta \left(t\right)\right)}.$
This equation shows how the NTK drives the dynamics of $f\left(\cdot ;\theta \left(t\right)\right)$ in the space of functions $\mathbb {R} ^{n_{\mathrm {in} }}\to \mathbb {R}$ during training.

This is a very brief (3 minute) summary by the first author:

This 15 minute IAS talk gives a nice overview of the results, and their relation to fundamental questions (both empirical and theoretical) in deep learning. Longer (30m) version: On the Connection between Neural Networks and Kernels: a Modern Perspective.

I hope to find time to explore this in more depth. Large width seems to provide a limiting case (analogous to the large-N limit in gauge theory) in which rigorous results about deep learning can be proved.

Some naive questions:

What is the expansion parameter of the finite width expansion?

What role does concentration of measure play in the results? (See 30m video linked above.)

Simplification seems to be a consequence of overparametrization. But the proof method seems to apply to a regularized (but still convex, e.g., using L1 penalization) loss function that imposes sparsity. It would be interesting to examine this specific case in more detail.

Notes to self:

The overparametrized (width ~ w^2) network starts in a random state and by concentration of measure this initial kernel K is just the expectation, which is the NTK. Because of the large number of parameters the effect of training (i.e., gradient descent) on any individual parameter is 1/w, and the change in the eigenvalue spectrum of K is also 1/w. It can be shown that the eigenvalue spectrum is positive and bounded away from zero, and this property does not change under training. Also, the evolution of f is linear in K up to corrections with are suppressed by 1/w. Hence evolution follows a convex trajectory and can achieve global minimum loss in a finite (polynomial) time.

The parametric 1/w expansion may depend on quantities such as the smallest NTK eigenvalue k: the proof might require k >> 1/w or wk large.

In the large w limit the function space has such high dimensionality that any typical initial f is close (within a ball of radius 1/w?) to an optimal f.

These properties depend on specific choice of loss function.

Saturday, May 08, 2021

Three Thousand Years and 115 Generations of 徐 (Hsu / Xu)

Over the years I have discussed economic historian Greg Clark's groundbreaking work on the persistence of social class. Clark found that intergenerational social mobility was much less than previously thought, and that intergenerational correlations on traits such as education and occupation were consistent with predictions from an additive genetic model with a high degree of assortative mating.

See Genetic correlation of social outcomes between relatives (Fisher 1918) tested using lineage of 400k English individuals, and further links therein. Also recommended: this recent podcast interview Clark did with Razib Khan.

The other day a reader familiar with Clark's work asked me about my family background. Obviously my own family history is not a scientific validation of Clark's work, being only a single (if potentially illustrative) example. Nevertheless it provides an interesting microcosm of the tumult of 20th century China and a window into the deep past...

I described my father's background in the post Hsu Scholarship at Caltech:

Cheng Ting Hsu was born December 1, 1923 in Wenling, Zhejiang province, China. His grandfather, Zan Yao Hsu was a poet and doctor of Chinese medicine. His father, Guang Qiu Hsu graduated from college in the 1920's and was an educator, lawyer and poet.

Cheng Ting was admitted at age 16 to the elite National Southwest Unified University (Lianda), which was created during WWII by merging Tsinghua, Beijing, and Nankai Universities. This university produced numerous famous scientists and scholars such as the physicists C.N. Yang and T.D. Lee.

Cheng Ting studied aerospace engineering (originally part of Tsinghua), graduating in 1944. He became a research assistant at China's Aerospace Research Institute and a lecturer at Sichuan University. He also taught aerodynamics for several years to advanced students at the air force engineering academy.

In 1946 he was awarded one of only two Ministry of Education fellowships in his field to pursue graduate work in the United States. In 1946-1947 he published a three-volume book, co-authored with Professor Li Shoutong, on the structures of thin-walled airplanes.

In January 1948, he left China by ocean liner, crossing the Pacific and arriving in San Francisco. ...

My mother's father was a KMT general, and her family related to Chiang Kai Shek by marriage. Both my grandfather and Chiang attended the military academy Shinbu Gakko in Tokyo. When the KMT lost to the communists, her family fled China and arrived in Taiwan in 1949. My mother's family had been converted to Christianity in the 19th century and became Methodists, like Sun Yat Sen. (I attended Methodist Sunday school while growing up in Ames IA.) My grandfather was a partner of T.V. Soong in the distribution of bibles in China in the early 20th century.

My father's family remained mostly in Zhejiang and suffered through the communist takeover, Great Leap Forward, and Cultural Revolution. My father never returned to China and never saw his parents again.

When I met my uncle (a retired Tsinghua professor) and some of my cousins in Hangzhou in 2010, they gave me a four volume family history that had originally been printed in the 1930s. The Hsu (Xu) lineage began in the 10th century BC and continued to my father, in the 113th generation. His entry is the bottom photo below.

Wikipedia: The State of Xu (Chinese: 徐) (also called Xu Rong (徐戎) or Xu Yi (徐夷)[a] by its enemies)[4][5] was an independent Huaiyi state of the Chinese Bronze Age[6] that was ruled by the Ying family (嬴) and controlled much of the Huai River valley for at least two centuries.[3][7] It was centered in northern Jiangsu and Anhui. ...

Generations 114 and 115:

Four volume history of the Hsu (Xu) family, beginning in the 10th century BC. The first 67 generations are covered rather briefly, only indicating prominent individuals in each generation of the family tree. The books are mostly devoted to generations 68-113 living in Zhejiang. (Earlier I wrote that it was two volumes, but it's actually four. The printing that I have is two thick books.)

Sunday, May 02, 2021

40 Years of Quantum Computation and Quantum Information

This is a great article on the 1981 conference which one could say gave birth to quantum computing / quantum information.

Technology Review: Quantum computing as we know it got its start 40 years ago this spring at the first Physics of Computation Conference, organized at MIT’s Endicott House by MIT and IBM and attended by nearly 50 researchers from computing and physics—two groups that rarely rubbed shoulders.

Twenty years earlier, in 1961, an IBM researcher named Rolf Landauer had found a fundamental link between the two fields: he proved that every time a computer erases a bit of information, a tiny bit of heat is produced, corresponding to the entropy increase in the system. In 1972 Landauer hired the theoretical computer scientist Charlie Bennett, who showed that the increase in entropy can be avoided by a computer that performs its computations in a reversible manner. Curiously, Ed Fredkin, the MIT professor who cosponsored the Endicott Conference with Landauer, had arrived at this same conclusion independently, despite never having earned even an undergraduate degree. Indeed, most retellings of quantum computing’s origin story overlook Fredkin’s pivotal role.

Fredkin’s unusual career began when he enrolled at the California Institute of Technology in 1951. Although brilliant on his entrance exams, he wasn’t interested in homework—and had to work two jobs to pay tuition. Doing poorly in school and running out of money, he withdrew in 1952 and enlisted in the Air Force to avoid being drafted for the Korean War.

A few years later, the Air Force sent Fredkin to MIT Lincoln Laboratory to help test the nascent SAGE air defense system. He learned computer programming and soon became one of the best programmers in the world—a group that probably numbered only around 500 at the time.

Upon leaving the Air Force in 1958, Fredkin worked at Bolt, Beranek, and Newman (BBN), which he convinced to purchase its first two computers and where he got to know MIT professors Marvin Minsky and John McCarthy, who together had pretty much established the field of artificial intelligence. In 1962 he accompanied them to Caltech, where McCarthy was giving a talk. There Minsky and Fredkin met with Richard Feynman ’39, who would win the 1965 Nobel Prize in physics for his work on quantum electrodynamics. Feynman showed them a handwritten notebook filled with computations and challenged them to develop software that could perform symbolic mathematical computations. ...

... in 1974 he headed back to Caltech to spend a year with Feynman. The deal was that Fredkin would teach Feynman computing, and Feynman would teach Fredkin quantum physics. Fredkin came to understand quantum physics, but he didn’t believe it. He thought the fabric of reality couldn’t be based on something that could be described by a continuous measurement. Quantum mechanics holds that quantities like charge and mass are quantized—made up of discrete, countable units that cannot be subdivided—but that things like space, time, and wave equations are fundamentally continuous. Fredkin, in contrast, believed (and still believes) with almost religious conviction that space and time must be quantized as well, and that the fundamental building block of reality is thus computation. Reality must be a computer! In 1978 Fredkin taught a graduate course at MIT called Digital Physics, which explored ways of reworking modern physics along such digital principles.

Feynman, however, remained unconvinced that there were meaningful connections between computing and physics beyond using computers to compute algorithms. So when Fredkin asked his friend to deliver the keynote address at the 1981 conference, he initially refused. When promised that he could speak about whatever he wanted, though, Feynman changed his mind—and laid out his ideas for how to link the two fields in a detailed talk that proposed a way to perform computations using quantum effects themselves.

Feynman explained that computers are poorly equipped to help simulate, and thereby predict, the outcome of experiments in particle physics—something that’s still true today. Modern computers, after all, are deterministic: give them the same problem, and they come up with the same solution. Physics, on the other hand, is probabilistic. So as the number of particles in a simulation increases, it takes exponentially longer to perform the necessary computations on possible outputs. The way to move forward, Feynman asserted, was to build a computer that performed its probabilistic computations using quantum mechanics.

[ Note to reader: the discussion in the last sentences above is a bit garbled. The exponential difficulty that classical computers have with quantum calculations has to do with entangled states which live in Hilbert spaces of exponentially large dimension. Probability is not really the issue; the issue is the huge size of the space of possible states. Indeed quantum computations are strictly deterministic unitary operations acting in this Hilbert space. ]

Feynman hadn’t prepared a formal paper for the conference, but with the help of Norm Margolus, PhD ’87, a graduate student in Fredkin’s group who recorded and transcribed what he said there, his talk was published in the International Journal of Theoretical Physics under the title “Simulating Physics with Computers.” ...

Feynman's 1981 lecture Simulating Physics With Computers.

Fredkin was correct about the (effective) discreteness of spacetime, although he probably did not realize this is a consequence of gravitational effects: see, e.g., Minimum Length From First Principles. In fact, Hilbert Space (the state space of quantum mechanics) itself may be discrete.

The Quantum Simulation Hypothesis

Hedgehogs, Foxes, and Feynman

My paper on the Margolus-Levitin Theorem in light of gravity:

Physical limits on information processing

We derive a fundamental upper bound on the rate at which a device can process information (i.e., the number of logical operations per unit time), arising from quantum mechanics and general relativity. In Planck units a device of volume V can execute no more than the cube root of V operations per unit time. We compare this to the rate of information processing performed by nature in the evolution of physical systems, and find a connection to black hole entropy and the holographic principle.

Participants in the 1981 meeting:

Physics of Computation Conference, Endicott House, MIT, May 6–8, 1981. 1 Freeman Dyson, 2 Gregory Chaitin, 3 James Crutchfield, 4 Norman Packard, 5 Panos Ligomenides, 6 Jerome Rothstein, 7 Carl Hewitt, 8 Norman Hardy, 9 Edward Fredkin, 10 Tom Toffoli, 11 Rolf Landauer, 12 John Wheeler, 13 Frederick Kantor, 14 David Leinweber, 15 Konrad Zuse, 16 Bernard Zeigler, 17 Carl Adam Petri, 18 Anatol Holt, 19 Roland Vollmar, 20 Hans Bremerman, 21 Donald Greenspan, 22 Markus Buettiker, 23 Otto Floberth, 24 Robert Lewis, 25 Robert Suaya, 26 Stand Kugell, 27 Bill Gosper, 28 Lutz Priese, 29 Madhu Gupta, 30 Paul Benioff, 31 Hans Moravec, 32 Ian Richards, 33 Marian Pour-El, 34 Danny Hillis, 35 Arthur Burks, 36 John Cocke, 37 George Michaels, 38 Richard Feynman, 39 Laurie Lingham, 40 P. S. Thiagarajan, 41 Marin Hassner, 42 Gerald Vichnaic, 43 Leonid Levin, 44 Lev Levitin, 45 Peter Gacs, 46 Dan Greenberger. (Photo courtesy Charles Bennett)