text:
# The Resolving Power Of A Microscope And Telescope

## What is Diffraction Limit?

When a point object is imaged using a circular opening (or aperture) like a lens or the iris of our eye, the image formed is not a point but a diffraction pattern. This is true, particularly when the size of the object is comparable to the wavelength of light.

Just as in single slit diffraction, a circular aperture produces a diffraction pattern of concentric rings that grow fainter as we move away from the center. These are known as Airy’s discs.

Airy’s discs

Because of this point sources close to one another can overlap and produce a blurred image. The half-angle θ subtended by the first minimum at the source is given by the relation:

$$sin \theta$$ ≈ $$1.22~ \frac {\lambda}{d}$$

To obtain a good image, point sources must be resolved i.e., the point sources must be imaged such that their images are sufficiently far apart that their diffraction patterns do not overlap. For this, the minimum distance between images must be such that the central maximum of the first image lies on the first minimum of the second and vice versa. Such an image is said to be just resolved. This is the famous Rayleigh criterion.

The criterion is given by the above formula as:

$$sin~\theta_R$$ ≈ $$\theta_R$$$$1.22~\frac {\lambda}{d}$$

Resolving Power

### Resolving Power:

It is defined as the inverse of the distance or angular separation between two objects which can be just resolved when viewed through the optical instrument.

### Resolving Power of Telescope:

In telescopes, very close objects such as binary stars or individual stars of galaxies subtend very small angles on the telescope. To resolve them we need very large apertures. We can use Rayleigh’s to determine the resolving power. The angular separation between two objects must be

$$\triangle \theta$$ = $$1.22~\frac{\lambda}{d}$$

Resolving power = $$\frac {1}{\triangle \theta}$$ = $$\frac {d}{1.22~\lambda}$$

Thus, the higher the diameter d, the better the resolution. The best astronomical optical telescopes have mirror diameters as large as 10 m to achieve the best resolution. Also, larger wavelengths reduce the resolving power, and consequently, radio and microwave telescopes need larger mirrors.

### Resolving Power of Microscope:

For microscopes, the resolving power is the inverse of the distance between two objects that can be just resolved. This is given by the famous Abbe’s criterion given by Ernst Abbe in 1873 as

$$\triangle~d$$ = $$\frac {\lambda}{2~n~sin~\theta}$$

Resolving power = $$\frac {1}{\triangle~d}$$ = $$\frac {2n~sin~\theta}{\lambda}$$

Where n is the refractive index of the medium separating object and aperture. Note that to achieve high-resolution n sin θ must be large. This is known as the Numerical aperture.

Thus, for good resolution:

1. sin θ must be large. To achieve this, the objective lens is kept as close to the specimen as possible.
2. A higher refractive index (n) medium must be used. Oil immersion microscopes use oil to increase the refractive index. Typically, for use in biology studies, this is limited to 1.6 to match the refractive index of glass slides used. (This limits reflection from slides). Thus, the numerical aperture is limited to just 1.4-1.6. Thus, optical microscopes (if you do the math) can only image to about 0.1 microns. This means that usually organelles, viruses, and proteins cannot be imaged.
3. Decreasing the wavelength by using X-rays and gamma rays. While these techniques are used to study inorganic crystals, biological samples are usually damaged by x-rays and hence are not used.

The limit set by Abbe’s criterion for optical microscopy cannot be avoided. However, using different fluorescence microscopy techniques the, Abbe’s limit can be circumvented. Stefan Hell used a technique called Stimulated Emission Depletion (STED) and the duo Eric Betzig and W.E. Moerner used superimposed images using green fluorescent proteins to bypass the resolution limit and obtain optical images in never before seen resolution. All three were awarded the 2014 Nobel Prize in Chemistry for their pioneering work.

Test Your Knowledge On Resolving Power Of Microscopes And Telescopes!

format: plain


text:
# Convert equation from cartesian to spherical

 Math Emeritus Sci Advisor Thanks PF Gold P: 39,568 in other words, "y= x" in spherical coordinates reduces to the set of points where t= $\theta= \pi/4$, r= $\phi$ and p= $\rho$ can be anything. Do you see that that is, in fact, the same as the plane y= x?


text:
Set PGFplots coordinate label using ifnum

I can't overcome this little nasty issue. Using \ifnum I set labels position around the coordinates in my pgfplot. This works fine but :

I am only able to test if variable \coordindex is greater or smaller than a certain value. I want to be able to test if the index is equal to a number. Tex gives me this error, in case I use \ifnum\coordindex=0 at first.

Missing = inserted for \ifnum. \end{axis}

\documentclass{standalone}

\usepackage{pgfplots}
\pgfplotsset{compat=1.10}

\pgfplotsset{
name nodes near coords/.style={
every node near coord/.append style={
anchor=center,                      %
name=#1\coordindex,                 % naming of npdes with running index
alias=#1last,
},
},
name nodes near coords/.default=coordnode
}

\begin{document}
\begin{tikzpicture}
\begin{axis}[%
width=\textwidth,
height=.3\textheight,
scale mode = scale uniformly,
scale only axis,
xmin=-200,
xmax= 250,
ymin=- 50,
ymax= 400,
axis x line = middle,
axis y line = left,
grid = none,
xtick = {-200, -100, ...,300},
ytick = {-100, 0, ...,400},
minor tick num = 1,
ytick align = outside,
extra x ticks={0},
extra x tick style={grid=major},
xlabel={x / mm},
ylabel={y / mm},
]

color=orange,
ultra thick,
shape=circle,
nodes near coords={},
every node near coord/.append style={
label={
[black!80, label distance=-1ex]
\ifnum\coordindex<1
5
\else
%                      \ifnum\coordindex=3
%                          -135
%                      \else
180-\coordindex*45
%                      \fi
\fi
:$p_{\coordindex}$
}
},
name nodes near coords=p
]
table{%
0           0
-79.9393    236.8749
143.0014    350.0007
143.0014    300.0000
200.0008    300.0000
};
\end{axis}
\end{tikzpicture}
\end{document}

I also tried with the ifthen package but had no luck. Please does anybody have a quick solution to this? What am I doing wrong? According to the document this shouldn't arise.

Maybe one of you also has a hint on how to print the ylabel the same way the xlabel is set; just at the top of and/or beside the y label.

• I'd say that \newcommand\equals{=} in the preamble and \ifnum\coordindex\equals 0 should work. At least no error is raised. See tex.stackexchange.com/questions/214995/… – egreg Dec 18 '14 at 14:10
• You have to do the math somewhere else not where TikZ is looking for an anchor to place the label. – percusse Dec 18 '14 at 14:13
• @egreg This does it. ThumbsUp. Thanks so much for the wuick hint and the link, which explains what i actually going on. Didn't know about this. – goeck Dec 18 '14 at 14:21

This is similar to Why does \ifnum not work inside of TikZ style definitions?, but the situation is different.

When processing label={...}, PGF looks for =; a workaround is thus hiding it:

        every node near coord/.append style={
label={
[black!80, label distance=-1ex]
\ifnum\coordindex<1
5
\else
\ifnum\coordindex\equals 3
-135
\else
180-\coordindex*45
\fi
\fi
:$p_{\coordindex}$
}
},

where \equals is defined in the preamble by

\newcommand{\equals}{=}

Another possibility:

        every node near coord/.append style={
label={
[black!80, label distance=-1ex]
\numbercompare{\coordindex<1}
{5}
{\numbercompare{\coordindex=3}{-135}{180-\coordindex*45}}%
:$p_{\coordindex}$
}
},

which requires

\usepackage{expl3}

\ExplSyntaxOn
\cs_set_eq:NN \numbercompare \int_compare:nTF
\ExplSyntaxOff

• Maybe there is even a more elegant way to handle the discrimination than in this manner. The solution of the error is simple and elegant though! :-) – goeck Dec 18 '14 at 14:32


text:
Accueil du site > Publications récentes > Nuclear jets in heavy-ion collisions

## Nuclear jets in heavy-ion collisions

P.Napolitani, M.Colonna

Head-on collisions between nuclei of different size at Fermi energies may give rise to extremely deformed dynamical regimes and patterns.
Those latter, may suddenly turn into a stream of nuclear clusters, resembling collimated jets.
This mechanism, which could be easily addressed in experiments, is simulated in the framework of stochastic one-body approaches.
We employ the Boltzmann-Langevin equation to specifically address out-of-equilibrium conditions and handle dynamical fluctuations.
An interesting interplay between surface and volume instabilities is discussed for the first time, leading to the appearing of stable and rather regular patterns of streaming clusters.

Six movies available in the "extras"

Voir en ligne : Physics Letters B Volume 797, 10 October 2019, 134833

 Institut de Physique Nucléaire Orsay - 15 rue Georges CLEMENCEAU - 91406 ORSAY (FRANCE) UMR 8608 - CNRS/IN2P3 | Connexion SPIP | Fil RSS du site | Crédits et mentions légales | Nous contacter | Ce site est optimisé pour les navigateurs suivants Firefox, Chrome, Internet explore 9


text:
WeBWorK Main Forum

Attempts to browse problem libraries produce errors

by Alasdair McAndrew -
Number of replies: 2
I have just installed WeBWorK on my Ubuntu 14.04 machine using the webwork_install.sh script. It seemed to do a fine job, and presented me with a webwork admin page running of localhost. My trouble is that whenever I attempt to view problem sets from the libraries, I have this error:

WeBWorK error

An error occured while processing your request. For help, please send mail to this site's webmaster (webmaster@localhost), including all of the following information as well as what what you were doing when the error occured.

Thu Jul 03 12:32:22 2014

Error messages

Undefined subroutine &WeBWorK::PG::Translator::fileFromPath called at /opt/webwork/pg/lib/WeBWorK/PG/Translator.pm line 543.

Call stack

The information below can help locate the source of the problem.

• in WeBWorK::PG::Local::new called at line 50 of /opt/webwork/webwork2/lib/WeBWorK/PG.pm
• in WeBWorK::PG::new called at line 312 of /opt/webwork/webwork2/lib/WeBWorK/Utils/Tasks.pm
• in WeBWorK::Utils::Tasks::renderProblems called at line 1590 of /opt/webwork/webwork2/lib/WeBWorK/ContentGenerator/Instructor/SetMaker.pm
• in WeBWorK::ContentGenerator::Instructor::SetMaker::body called at line 155 of /opt/webwork/webwork2/lib/WeBWorK/Template.pm
• in WeBWorK::Template::template called at line 530 of /opt/webwork/webwork2/lib/WeBWorK/ContentGenerator.pm
• in WeBWorK::ContentGenerator::content called at line 202 of /opt/webwork/webwork2/lib/WeBWorK/ContentGenerator.pm
• in WeBWorK::ContentGenerator::go called at line 380 of /opt/webwork/webwork2/lib/WeBWorK.pm

Does anybody know what's going on - and how to fix it?

Thanks,
Alasdair


text:
# Is my statistician friend right/wrong on metric spaces and norms?

I was talking to a statistician friend of mine who said that instead of minimizing this function $\sum_{i,j}W_{ij}d_{ij}^2(X)$ over $X$ it would be better to solve an analogous minimization problem $\sum_{i,j}W_{ij}||f(Y_{i.})-f(Y_{j.})||_\mathcal{H}$ over $f$ instead with the norm being a RKHS(Reproducing Kernel Hilbert Space) norm where the functions $f(.)$ come from a Hilbert space of functions. Both minimizations are under a constraint that $\sum_{i,j}d^2_{i,j}(X)$ or $\sum_{i,j}||f(Y_{i.})-f(Y_{j.})||_\mathcal{H}$ is constrained to a fixed real positive value $\nu$.

Here, $d_{ij}^2(X)$ is the squared Euclidean distance between the rows $i,j$ of the real unknown matrix $X$. $Y$ is a fixed real matrix.

Question: Why would the latter problem under the function space be better!? What does the RKHS norm provide, which is different than the euclidean distance/norm? From this description, why do you think my academic friend has said this-when thought from different mathematical directions? What are we gaining or losing between these two formulations? After all, once the $f(.)$ is solved for, the norms seem to be preserving some sort of notion of distance/dissimilarity or nearness. What is special about the second problem!? I understand that the question is a little open ended. So please feel free to be verbose in expressing your thoughts!

Perspective: I showed him the initial Euclidean problem. He thought about it and posed the other problem as being interesting. Please shed your thoughts.

-
Why is no one answering! But just voting up? ;) I'd rather have more discussion and no votes ;) –  halms Mar 28 '13 at 19:24
My experience is that model builders tend to use Hilbert space norms.This is something I, myself, am still learning about. I'm not sure why this is a better approach. You might take a look at this reference. amazon.com/… –  mtiano Mar 28 '13 at 19:29
An equivalent way to pose your question would be: "What does a Hilbert space buy me that I don't get from my standard Euclidean space?" I have a few ideas as to why, but I'm not really knowledgeable enough to not sound like I'm talking out of my rear-end. –  Arkamis Mar 28 '13 at 19:41
@Arkamis..That is exactly my question, that you have put forth succinctly. I put in a big description just to make sure that I cannot maintain the standard of abstraction required for say a usual problem that i would post in se. Please feel free to putforth some of your thoughts/pointers to material-as I do need a starting point-from some direction or the other! –  halms Mar 28 '13 at 20:12

This is not an answer, per se, but some general observations.

What you're looking to do is similar to a curve fit problem or a regression problem: you have some data, and you'd like to find some function that fits this data in some minimizing sense. Because you're using the difference between observations, it's obviously not quite as straightforward, but there is some similarity here.

Statisticians and data analysts often view data as the effect of some cause. While some are thrilled to model the effect (e.g. obtaining a function that fits the data, and saying "a-ha! The effect looks like this!"), a more interesting problem is to try to infer some structure that underlies the source data -- understanding the mechanics of the cause. Of course, you're not really understanding the cause without some extrinsic information, but that's how we like to think of it. Some measurements $y$ are the result of some physical process $f$ acting on some inputs $x$.

There are many, many ways to do this, many of which are more or less equivalent. As @mtiano mentioned, model builders love Hilbert space norms.

What a Hilbert space norm buys you, in this case, is a notion that you can find some function that models the cause, and then in doing so, you get a model of the effect for free.

In other words, instead of interpolating a bunch of output data, you're finding a function that operates on some fixed input data; once you have that function, you can do all the things you would do with an interpolant, but now you can directly link that interpolant to some independent variables.

Depending on your data analysis approach, there are many ways to approach this problem. Things like neural networks, adaptive parameter estimation algorithms, quasi-Newton search methods, etc. tend to default to $L^2$-minimization. I'd wager that in engineering and statistics papers, $L^2$ is by far the most common "optimization space."

$L^2$, of course, is a Hilbert space. And we like Hilbert spaces because they have inner products, and inner products are things that tend to arise naturally in many of these analyses.

Of course, you don't have to work in $L^2$ if it doesn't suit your application. But all the work that's been done in developing algorithmic and analytical techniques for optimization and data analysis in $L^2$ are going to translate almost immediately to some other Hilbert space.

Not having the inner product means that you might have to do some additional work, and in the end, all you get is an interpolant on some observed data, with no intuition regarding the underlying process that made the data look like it does.

-
One thing to note: I said that many techniques for data analysis are more or less equivalent. In reality, many of them are essentially the same. Neural networks, radial basis function networks, nonlinear regression, fuzzy networks, nonlinear parameter identification, principle component analysis, proper orthogonal decomposition, and so on and so on are all essentially the same thing. –  Arkamis Mar 29 '13 at 3:49
If you do any reading on any of these techniques, the minimization problem usually becomes one of minimizing a residual in an $L^2$ sense. Hence, by working in a Hilbert space for your problem, you're essentially almost transforming your problem to one already solved. Almost. –  Arkamis Mar 29 '13 at 3:50


text:
# Parabolan War (Guide)/Warplan

This calculator will guide you through a Campaign of Parabolan Warfare by deciding the correct options to play at each Stage and values of Advance! and Campaign Morale, based on your character's stats and your own valuation of the different items that might be consumed.

By using this calculator, you are making the decision that you would rather let a spreadsheet play the game for you. You should only use this tool if you already find grinds to be joyless, or a higher EPA is better motivation than gameplay.

This calculator is considered Beta-quality. As far as I can tell it probably works right, but if something seems odd, then send questions or bugs to my Talk page. It also makes the hamster-wheel in the server spin really fast. Know Beta things:

• The tables are not collapsible in this page. They will be collapsible if you output as Wikitext and save to your user page.
• Options that use Advanced Skills are not implemented.

#### Using this Calculator

The first set of inputs is straightforward: your character's stats, and your choice of Campaign and General. The choice of campaign only affects the number of actions spent on narrative after each stage.

The second set of inputs is the Action costs for the various items that can be spent (or gained) via the various actions on the campaign trial. This calculator works by converting all resources into an "action cost" equivalent, so items are valued based on the number of actions to replenish those spent. Ravages of Parabolan Warfare are valued based on the actions to clear them after the campaign. The default values assume all resources can be obtained at 2.5 EPA, and that Ravages take 1 action to clear.

The results of the calculator will show tables of the expected actions to complete the Parabolan Campaign from any given campaign state, as well as the optimal choice at each state. If Airs-dependent actions are worth playing, then the tables will list the best non-Airs choice, as well as all Airs-dependent choices that should be played if available.

In some cases, multiple choices are equally-optimally. Ties are broken by arbitrary implementation details.

By default, the calculator will display your Battle-Plan on this page. Save your Battle-Plan to your own user pages by selecting the output format of "WikiCode" and copy-pasting the resulting Wiki mark-up into your own page.

### Get My Personalized Battle-Plan

 template = :Parabolan War (Guide)/Saver
form = parameters
result = warplan
param = Campaign|Campaign|Yourself|select|Viscountess,Ophidian Gentleman,Second City Priest,The Cats,The Fingerkings,The Chessboard,Yourself|The Cats,The Fingerkings,The Chessboard=General,General_Level
param = General|Chosen General|None|buttonselect|None,Cat,Snake,Chess
param = General_Level|General Level|3|buttonselect|1,2,3
param = Watchful|Watchful|300|int|0-400
param = Dangerous|Dangerous|300|int|0-400
param = Persuasive|Persuasive|300|int|0-400
param = Glasswork|Glasswork|7|int|0-20
param = Toxicology|Kataleptic Toxicology|7|int|0-20
param = Mithridacy|Mithridacy|7|int|0-20
param = Chess|A Player of Chess|7|int|0-20
param = Silverer|Silverer?|no|check|yes,no
param = selects|Item Costs, in Actions to Acquire||group|Cost_Ravage,Cost_Psalm,Cost_Sign,Cost_Self,Cost_Glass,Cost_Wing,Cost_Plaque,Cost_Light,Cost_Solacefruit,Cost_Viric,Cost_Feather,Cost_Claw,Cost_Address,Cost_Palim,Cost_Pawn,Cost_Move,Cost_Nightmare,Cost_Catch
param = Cost_Ravage|Curing Ravages of Parabolan Warfare|1|number|0-10
param = Cost_Nightmare|Curing 1 CP of Nightmares|0.5|number|0-10
param = Cost_Psalm|Apostate's Pslam|1|number|0-10
param = Cost_Sign|London Street Sign|1|number|0-10
param = Cost_Self|Memory of a Much Lesser Self|1|number|0-10
param = Cost_Glass|Glass Gazette|1|number|0-10
param = Cost_Wing|Wing of a Young Terror Bird|1|number|0-10
param = Cost_Plaque|Correspondence Plaque|0.2|number|0-10
param = Cost_Catch|Deep-Zee Catch|0.2|number|0-10
param = Cost_Light|Memory of Light|0.2|number|0-10
param = Cost_Move|Moves in the Great Game|0.2|number|0-10
param = Cost_Palim|Palimpsest Scrap|0.2|number|0-10
param = Cost_Solacefruit|Solacefruit|0.2|number|0-10
param = Cost_Viric|Trace of Viric|0.2|number|0-10
param = Cost_Feather|Royal-Blue Feather|0.2|number|0-10
param = Cost_Claw|Silvered Cat's Claw|0.04|number|0-10
param = Cost_Pawn|Well-Placed Pawns|0.04|number|0-10
param = Format|Output Format|Tables|buttonselect|Tables,WikiCode

### How it Works

This calculator is based on a classical optimization technique called Dynamic Programming. (Despite the similar name, this bears no relation to "dynamic programming languages" like JavaScript or Lua.) The core concept is that results are computed starting from the end of the campaign working backwards rather than from the beginning, calculating actions-to-goal rather than actions-spent. Going in this order means that when considering any given campaign state, the outcomes of the all of the options available from that state have already been calculated, so the arithmetic to choose which is best becomes very simple.

As an example, consider the table below, showing results for the Writhing River, calculated with default values. Results in the table are computed beginning from the bottom of the table going upwards, and from left to right. The cell highlighted in purple represents the campaign state of 0 x Advance! & 5 x Campaign Morale, and the other highlighted cells indicate the outcome of all the possible actions that a player could choose from that point. The total Actions-to-Complete from each of those states in the Campaign have already been calculated. We can then compute the expected Actions-to-Complete of each of the available options by taking into account its outcomes, success probability, and resource cost. The option with the lowest expected Actions-to-Complete is recommended as the best option, and its Actions-to-Complete is stored as the value for that cell, which will be referenced by other actions that result in that game state.

From these data points, the values of each of the options available can be calculated as in the table below. Based on these, the best option available is to Gain Morale (Launch a naval assault), with an expected Actions-to-Complete of 36.82 from this point forward.

Option Cost to Move Result of Move Total Actions-to-Complete
Spend Morale 1 Action 36.82 on success (100%) 37.82
40.67 on failure (0%)
Gain Morale 1 Action 35.82 36.82
Safe Progress 1 Action
Item worth 1 Action
35.82 37.82
Fast Progress 1.39 Actions
Items worth 0.88 Actions
Ravages worth 0.39 Actions
35.82 38.48

#### Calculations

Some actions (like most Safe Progress options) always produce the same amount of Advance! on success or failure, but have different resource costs. For a given Advance! a and Morale m, the Actions-to-Goal value A(a, m) can be computed as

${\displaystyle A(a,m)=1+A(a+1,m)+p\times c_{s}+(1-p)\times c_{f}}$

where p is the probability of success, and cs and cf are the resource costs of success and failure. The constant 1 is the action spent on playing the option. The value A(a+1, m) is the Actions-to-Goal for one more Advance! and the same Morale; some actions may add more Advance!.

Spending Morale is a slightly different situation, where success & failure both always spend Morale but one only gives Advance!. For this situation, the formula is modified slightly. Note that no Morale options cost resources, so the c terms are ignored.

${\displaystyle A(a,m)=1+p\times A(a+5,m-5)+(1-p)\times A(a,m-5)}$

Most other options work slightly differently, where costs are accrued on failure but neither Advance! nor Morale is modified. If such an option is the best choice, then it should be attempted repeatedly until successful. In these cases, the formula can be derived by observing that with a success probability p, one success will require 1/p attempts and incur ( 1/p - 1) failures.

${\displaystyle A(a,m)={\frac {1}{p}}+A(a+3,m)+c_{s}+({\frac {1}{p}}-1)\times c_{f}}$

As before, the a + 3 term is an example for early-stage Fast Progress options, but other options modify Advance! and Morale in different ways.

#### Airs

The impact of Airs-dependent options are tricky to account for. They cannot always be attempted, which is straightforward to accommodate. The more difficult issue is that on failure, sometimes the option can be re-attempted and sometimes it cannot.

The Actions-to-complete value for an Airs option Aa(a, m) depends in part on the value for the best deterministic option available, Ad(a, m). With a success probability s, and assuming Airs options are available exactly 1/3 of the time, the value Aa(a, m) can be calculated as:

{\displaystyle {\begin{aligned}A_{a}(a,m)={\frac {2}{3}}&\left(A_{d}(a,m)\right)\\+{\frac {1}{3}}&\left[s\times (1+A(a+4,m))+(1-s)\times \left(1+c_{f}+A_{a}(a,m)\right)\right]\end{aligned}}}

This equation defines Aa in terms of itself, which represents re-attempting on failure. The term that does not contain Aa encapsulates the fact that the option is not always available to re-attempt. Solving this recurrence relationship for a closed-form value of Aa yields the following:

${\displaystyle A_{a}(a,m)={\frac {2A_{d}(a,m)+s\times A(a+4,m)+c_{f}\times (1-s)+1}{2+s}}}$

The Airs-dependent option should be taken if it has a better Action-to-Goal value than the determenistic options available, when ${\displaystyle A_{a}, i.e. when ${\displaystyle A_{d}-A_{a}>0}$. By substituting terms, we found Airs-dependent actions should be played when the following is true:

${\displaystyle A(a+4,m)

The fraction on the right describes how much better the success result of the Airs option needs to be compared to the best deterministic option in order to be worth playing.

When there are multiple Airs-dependent options available, the same analysis will produce equations which have more terms but are not significantly more complicated. This analysis will slightly under-value Airs-dependent options when the best deterministic option can be re-attempted on failure, because it does not account for the possibility that failures of the deterministic option might allow the Airs option to become available again.


text:
# [texhax] full bleed

Gabrielle Araj gabrielle_araj at yahoo.com
Thu Dec 10 23:58:51 CET 2009

Thanks for your response.
Do you have a *.tex example so I can adapt it to my situation.I use geometry.
\documentclass[12pt,twoside]{book}
\usepackage[paperheight=21.0cm,paperwidth=21.0cm,nomarginpar,hmargin=1in]{geometry}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}

I found this example but unable to understand what to do to have color on the edge of my paper. EXAMPLE:
\documentclass[11pt,a4paper]{memoir}
\setstocksize{52mm}{90mm}
\setpagecc{49mm}{87mm}{*}
\settypeblocksize{43mm}{81mm}{*}
\setulmargins{3mm}{*}{*}
\setlrmargins{3mm}{*}{*}
\checkandfixthelayout[fixed]
\pagestyle{empty}
\usepackage{color}
\begin{document}
\pagecolor[cmyk]{...}
...
\end{document}

________________________________
From: Pierre MacKay <pierre.mackay at comcast.net>
To: Gabrielle Araj <gabrielle_araj at yahoo.com>
Sent: Thu, December 10, 2009 2:54:44 PM
Subject: Re: [texhax] full bleed

On 12/09/2009 03:45 PM, Gabrielle Araj wrote:
>
>I
>would like to put color on the border of my document. Can you help me
>with that.
>
>>Thanks
>
>
It may depend on whether you are doing your own printing from a desktop
printer or using a commercial printer.
If you are using a commercial printer, you need to take account of the
recently developed standards for PDF, such as PDF/X-3
(I have not yet explored PDF/X-5).  The Adobe Acrobat Pro distiller
seems at this time to be the only tool you can use to set the four
page-wide levels of boxing, of which you will need three.  They run
MediaBox, CropBox, BleedBox, and TrimBox, with the defaults being to
have the borders of all four the same.  If you use dvips with the -O
and the -T options, you will effectively be setting the MediaBox to
match the CropBox.  Then distiller will give you the (Advanced
Options) option to set the Bleed Box to the CropBox, and to specify the
offset of the TrimBox boundaries, which must lie inside the Bleed Box.
(The amount favored by the presses I use is 9 Adobe points inside all
four boundaries of the Bleed box.  Unfortunately, Ghostscript seems to
be still at an experimental roll-your-own stage in offering these
details.

This means that your basic colored underlay must be 18 pt wider and 18
pt deeper than your desired trim size, and must be moved into position
so that it extends outside the trim size in all four directions.  I
find it best to size the color underlay as needed and then immediately
declare that it has 0pt width and 0pt depth, so that it will not
complicate the positioning of other elements on the page.

Sorry if this sounds complicated.  It is complicated the first
time through, and you will probably spend some time looking at the PDFs
and fudging dimensions until things come right.  I use a framework of
\vrules that can be turned on and off with an \if \fi construction so
that I can really see where the TrimBox will be aligned.  (The rules
are set into named boxes, and the boxes are given  a declared 0pt width
so that they will not affect the spacing of other elements.  The effect
is a sort of visible \strut.)

If you can get hold of a PDF that has BleedBox and TrimBox set, look at
it in something like emacs, and you will get a good idea of how and
where the values are set in PDF/X-3.

Good luck.  It works very well once you get the hang of it.

Pierre MacKay

__________________________________________________________________


text:
+1 vote
135 views

Which of the following is not true in the function $f(n)=2^{n-4}$?

1. $f(n)$=Θ($2^{n+3}$)
2. $f(n)$=Ω($n^{1000}$)
3. $f(n)$=Ο($2^{n-10}$)
4. $f(n)$=$None$

edited | 135 views
0
Sorry, not A.

Is D correct?
0

$A. f(n)$= Θ($2^{n+3}$)

$f(n) = 2^{n-4} =\Large \frac{2^n}{2^4}$

let $g(n) = 2^{n+3} = 2^{n}.2^3$

$\large \frac{f(n)}{g(n)} = \frac{1}{2^3.2^4}$

this tells us $f(n)$= Θ($2^{n+3}$) is true

$B.$ $f(n)$=Ω($n^{1000}$)

$f(n)$ is exponential and $n^{1000}$ is polynomial so  $f(n)$=Ω($n^{1000}$)  is true

C. $f(n)$=Ο($2^{n-10}$) is also true just like A

So none of them are false

by Boss (36.5k points)
selected by
+1 vote

Option d.

by Boss (36.5k points)
For the first one, we have to show that $2^{n-4} \leq c \times 2^{n-10}$ for all $n \geq n_0$.

This is true for any $c \geq 2^6$ as we get by solving the inequality.

For the second one, we have to prove that $f(n) \geq c \times g(n)$ for all $n \geq n_0$
$\implies 2^{n-4} \geq c \times n^{1000}$.

This is true for all $n_0$ when $n - 1000 \log n > 4$. You can get this inequality by doing using the limit definition while comparing terms.

For the third, we have to show $c_1 \times 2^{n-3} \leq 2^{n-4} \leq c_2 \times 2^{n+3}$.

You can find $c_1, c_2$ according to this condition.

Hence, all three are true.
by Loyal (6.7k points)


text:
StructVAE: Tree-structured Latent Variable Models for Semi-supervised Semantic Parsing

# StructVAE: Tree-structured Latent Variable Models for Semi-supervised Semantic Parsing

## Abstract

Semantic parsing is the task of transducing natural language (NL) utterances into formal meaning representations (MRs), commonly represented as tree structures. Annotating NL utterances with their corresponding MRs is expensive and time-consuming, and thus the limited availability of labeled data often becomes the bottleneck of data-driven, supervised models. We introduce StructVAE, a variational auto-encoding model for semi-supervised semantic parsing, which learns both from limited amounts of parallel data, and readily-available unlabeled NL utterances. StructVAE models latent MRs not observed in the unlabeled data as tree-structured latent variables. Experiments on semantic parsing on the Atis domain and Python code generation show that with extra unlabeled data, StructVAE outperforms strong supervised models.1

\aclfinalcopy

## 1 Introduction

Semantic parsing tackles the task of mapping natural language (NL) utterances into structured formal meaning representations (MRs). This includes parsing to general-purpose logical forms such as -calculus Zettlemoyer and Collins (2005, 2007) and the abstract meaning representation (AMR, \newcitebanarescu13amr,Misra:16neuralccg), as well as parsing to computer-executable programs to solve problems such as question answering Berant et al. (2013); Yih et al. (2015); Liang et al. (2017), or generation of domain-specific (e.g., SQL) or general purpose programming languages (e.g., Python) (Quirk et al., 2015; Yin and Neubig, 2017; Rabinovich et al., 2017).

While these models have a long history (Zelle and Mooney, 1996; Tang and Mooney, 2001), recent advances are largely attributed to the success of neural network models Xiao et al. (2016); Ling et al. (2016); Dong and Lapata (2016); Iyer et al. (2017); Zhong et al. (2017). However, these models are also extremely data hungry: optimization of such models requires large amounts of training data of parallel NL utterances and manually annotated MRs, the creation of which can be expensive, cumbersome, and time-consuming. Therefore, the limited availability of parallel data has become the bottleneck of existing, purely supervised-based models. These data requirements can be alleviated with weakly-supervised learning, where the denotations (e.g., answers in question answering) of MRs (e.g., logical form queries) are used as indirect supervision (\newciteDBLP:conf/conll/ClarkeGCR10,DBLP:conf/acl/LiangJK11,berant2013freebase, inter alia), or data-augmentation techniques that automatically generate pseudo-parallel corpora using hand-crafted or induced grammars Jia and Liang (2016); Wang et al. (2015).

In this work, we focus on semi-supervised learning, aiming to learn from both limited amounts of parallel NL-MR corpora, and unlabeled but readily-available NL utterances. We draw inspiration from recent success in applying variational auto-encoding (VAE) models in semi-supervised sequence-to-sequence learning Miao and Blunsom (2016); Kociský et al. (2016), and propose StructVAE — a principled deep generative approach for semi-supervised learning with tree-structured latent variables (Fig. 1). StructVAE is based on a generative story where the surface NL utterances are generated from tree-structured latent MRs following the standard VAE architecture: (1) an off-the-shelf semantic parser functions as the inference model, parsing an observed NL utterance into latent meaning representations (§ 3.2); (2) a reconstruction model decodes the latent MR into the original observed utterance (§ 3.1). This formulation enables our model to perform both standard supervised learning by optimizing the inference model (i.e., the parser) using parallel corpora, and unsupervised learning by maximizing the variational lower bound of the likelihood of the unlabeled utterances (§ 3.3).

In addition to these contributions to semi-supervised semantic parsing, StructVAE contributes to generative model research as a whole, providing a recipe for training VAEs with structured latent variables. Such a structural latent space is contrast to existing VAE research using flat representations, such as continuous distributed representations Kingma and Welling (2013), discrete symbols Miao and Blunsom (2016), or hybrids of the two Zhou and Neubig (2017).

We apply StructVAE to semantic parsing on the Atis domain and Python code generation. As an auxiliary contribution, we implement a transition-based semantic parser, which uses Abstract Syntax Trees (ASTs, § 3.2) as intermediate MRs and achieves strong results on the two tasks. We then apply this parser as the inference model for semi-supervised learning, and show that with extra unlabeled data, StructVAE outperforms its supervised counterpart. We also demonstrate that StructVAE is compatible with different structured latent representations, applying it to a simple sequence-to-sequence parser which uses -calculus logical forms as MRs.

## 2 Semi-supervised Semantic Parsing

In this section we introduce the objectives for semi-supervised semantic parsing, and present high-level intuition in applying VAEs for this task.

### 2.1 Supervised and Semi-supervised Training

Formally, semantic parsing is the task of mapping utterance to a meaning representation . As noted above, there are many varieties of MRs that can be represented as either graph structures (e.g., AMR) or tree structures (e.g.-calculus and ASTs for programming languages). In this work we specifically focus on tree-structured MRs (see Fig. 2 for a running example Python AST), although application of a similar framework to graph-structured representations is also feasible.

Traditionally, purely supervised semantic parsers train a probabilistic model using parallel data of NL utterances and annotated MRs (i.e., ). As noted in the introduction, one major bottleneck in this approach is the lack of such parallel data. Hence, we turn to semi-supervised learning, where the model additionally has access to a relatively large amount of unlabeled NL utterances . Semi-supervised learning then aims to maximize the log-likelihood of examples in both and :

 J=∑⟨x,z⟩ ∈Llogpϕ(z|x)supervised obj.  Js+α∑x∈Ulogp(x)unsupervised obj.  Ju (1)

The joint objective consists of two terms: (1) a supervised objective that maximizes the conditional likelihood of annotated MRs, as in standard supervised training of semantic parsers; and (2) a unsupervised objective , which maximizes the marginal likelihood of unlabeled NL utterances , controlled by a tuning parameter . Intuitively, if the modeling of and is coupled (e.g., they share parameters), then optimizing the marginal likelihood using the unsupervised objective would help the learning of the semantic parser  (Zhu, 2005). StructVAE uses the variational auto-encoding framework to jointly optimize and , as outlined in § 2.2 and detailed in § 3.

### 2.2 VAEs for Semi-supervised Learning

From Eq. 1, our semi-supervised model must be able to calculate the probability of unlabeled NL utterances. To model , we use VAEs, which provide a principled framework for generative models using neural networks (Kingma and Welling, 2013). As shown in Fig. 1, VAEs define a generative story (bold arrows in Fig. 1, explained in § 3.1) to model , where a latent MR is sampled from a prior, and then passed to the reconstruction model to decode into the surface utterance . There is also an inference model that allows us to infer the most probable latent MR given the input (dashed arrows in Fig. 1, explained in § 3.2). In our case, the inference process is equivalent to the task of semantic parsing if we set . VAEs also provide a framework to compute an approximation of using the inference and reconstruction models, allowing us to effectively optimize the unsupervised and supervised objectives in Eq. 1 in a joint fashion (\newcitekingma2014semi, explained in § 3.3).

## 3 StructVAE: VAEs with Tree-structured Latent Variables

### 3.1 Generative Story

StructVAE follows the standard VAE architecture, and defines a generative story that explains how an NL utterance is generated: a latent meaning representation is sampled from a prior distribution over MRs, which encodes the latent semantics of the utterance. A reconstruction model then decodes the sampled MR into the observed NL utterance .

Both the prior and the reconstruction model takes tree-structured MRs as inputs. To model such inputs with rich internal structures, we follow \newcitekonstas2017neural, and model the distribution over a sequential surface representation of , instead. Specifically, we have and 2. For code generation, is simply the surface source code of the AST . For semantic parsing, is the linearized s-expression of the logical form. Linearization allows us to use standard sequence-to-sequence networks to model and . As we will explain in § 4.3, we find these two components perform well with linearization.

Specifically, the prior is parameterized by a Long Short-Term Memory (LSTM) language model over . The reconstruction model is an attentional sequence-to-sequence network (Luong et al., 2015), augmented with a copying mechanism (Gu et al., 2016), allowing an out-of-vocabulary (OOV) entity in to be copied to (e.g., the variable name my_list in Fig. 1 and its AST in Fig. 2). We refer readers to Appendix B for details of the neural network architecture.

### 3.2 Inference Model

StructVAE models the semantic parser as the inference model in VAE (§ 2.2), which maps NL utterances into tree-structured meaning representations . can be any trainable semantic parser, with the corresponding MRs forming the structured latent semantic space. In this work, we primarily use a semantic parser based on the Abstract Syntax Description Language (ASDL) framework (Wang et al., 1997) as the inference model. The parser encodes into ASTs (Fig. 2). ASTs are the native meaning representation scheme of source code in modern programming languages, and can also be adapted to represent other semantic structures, like -calculus logical forms (see § 4.2 for details). We remark that StructVAE works with other semantic parsers with different meaning representations as well (e.g., using -calculus logical forms for semantic parsing on Atis, explained in § 4.3).

Our inference model is a transition-based parser inspired by recent work in neural semantic parsing and code generation. The transition system is an adaptation of Yin and Neubig (2017) (hereafter YN17), which decomposes the generation process of an AST into sequential applications of tree-construction actions following the ASDL grammar, thus ensuring the syntactic well-formedness of generated ASTs. Different from YN17, where ASTs are represented as a Context Free Grammar learned from a parsed corpus, we follow Rabinovich et al. (2017) and use ASTs defined under the ASDL formalism (§ 3.2.1).

#### Generating ASTs with ASDL Grammar

First, we present a brief introduction to ASDL. An AST can be generated by applying typed constructors in an ASDL grammar, such as those in Fig. 3 for the Python ASDL grammar. Each constructor specifies a language construct, and is assigned to a particular composite type. For example, the constructor Call has type expr (expression), and it denotes function calls. Constructors are associated with multiple fields. For instance, the Call constructor and has three fields: func, args and keywords. Like constructors, fields are also strongly typed. For example, the func field of Call has expr type. Fields with composite types are instantiated by constructors of the same type, while fields with primitive types store values (e.g., identifier names or string literals). Each field also has a cardinality (single, optional , and sequential ), specifying the number of values the field has.

Each node in an AST corresponds to a typed field in a constructor (except for the root node). Depending on the cardinality of the field, an AST node can be instantiated with one or multiple constructors. For instance, the func field in the example AST has single cardinality, and is instantiated with a Name constructor; while the args field with sequential cardinality could have multiple constructors (only one shown in this example).

Our parser employs a transition system to generate an AST using three types of actions. Fig. 2 (Right) lists the sequence of actions used to generate the example AST. The generation process starts from an initial derivation with only a root node of type stmt (statement), and proceeds according to the top-down, left-to-right traversal of the AST. At each time step, the parser applies an action to the frontier field of the derivation:

ApplyConstr actions apply a constructor to the frontier composite field, expanding the derivation using the fields of . For fields with single or optional cardinality, an ApplyConstr action instantiates the empty frontier field using the constructor, while for fields with sequential cardinality, it appends the constructor to the frontier field. For example, at the Call constructor is applied to the value field of Expr, and the derivation is expanded using its three child fields.

Reduce actions complete generation of a field with optional or multiple cardinalities. For instance, the args field is instantiated by Name at , and then closed by a Reduce action at .

GenToken actions populate an empty primitive frontier field with token . A primitive field whose value is a single token (e.g., identifier fields) can be populated with a single GenToken action. Fields of string type can be instantiated using multiple such actions, with a final </f> action to terminate the generation of field values.

#### Modeling qϕ(z|x)

The probability of generating an AST is naturally decomposed into the probabilities of the actions used to construct :

 qϕ(z|x)=∏tp(at|a

Following YN17, we parameterize using a sequence-to-sequence network with auxiliary recurrent connections following the topology of the AST. Interested readers are referred to Appendix B and Yin and Neubig (2017) for details of the neural network architecture.

### 3.3 Semi-supervised Learning

In this section we explain how to optimize the semi-supervised learning objective Eq. 1 in StructVAE.

Supervised Learning For the supervised learning objective, we modify , and use the labeled data to optimize both the inference model (the semantic parser) and the reconstruction model:

 Js≜∑(x,z)∈L(logqϕ(z|x)+logpθ(x|z)) (2)

Unsupervised Learning To optimize the unsupervised learning objective in Eq. 1, we maximize the variational lower-bound of :

 logp(x)≥Ez∼qϕ(z|x)(logpθ(x|z))−λ⋅KL[qϕ(z|x)||p(z)]=L (3)

where is the Kullback-Leibler (KL) divergence. Following common practice in optimizing VAEs, we introduce as a tuning parameter of the KL divergence to control the impact of the prior (Miao and Blunsom, 2016; Bowman et al., 2016).

To optimize the parameters of our model in the face of non-differentiable discrete latent variables, we follow Miao and Blunsom (2016), and approximate using the score function estimator (a.k.a. REINFORCE, Williams (1992)):

 \pdvLϕ=\pdvϕEz∼qϕ(z|x)(logpθ(x|z)−λ(logqϕ(z|x)−logp(z)))% learning signal=\pdvϕEz∼qϕ(z|x)l′(x,z)≈1|S(x)|∑zi∈S(x)l′(x,zi)\pdvlogqϕ(zi|x)ϕ (4)

where we approximate the gradient using a set of samples drawn from . To ensure the quality of sampled latent MRs, we follow Guu et al. (2017) and use beam search. The term is defined as the learning signal (Miao and Blunsom, 2016). The learning signal weights the gradient for each latent sample . In REINFORCE, to cope with the high variance of the learning signal, it is common to use a baseline to stabilize learning, and re-define the learning signal as

 l(x,z)≜l′(x,z)−b(x). (5)

Specifically, in StructVAE, we define

 b(x)=a⋅logp(x)+c, (6)

where is a pre-trained LSTM language model. This is motivated by the empirical observation that correlates well with the reconstruction score , hence with .

Finally, for the reconstruction model, its gradient can be easily computed:

 \pdvLθ≈1|S(x)|∑zi∈S(x)\pdvlogpθ(x|zi)θ.

Discussion Perhaps the most intriguing question here is why semi-supervised learning could improve semantic parsing performance. While the underlying theoretical exposition still remains an active research problem Singh et al. (2008), in this paper we try to empirically test some likely hypotheses. In Eq. 4, the gradient received by the inference model from each latent sample is weighed by the learning signal . can be viewed as the reward function in REINFORCE learning. It can also be viewed as weights associated with pseudo-training examples sampled from the inference model. Intuitively, a sample with higher rewards should: (1) have adequately encode the input, leading to high reconstruction score ; and (2) have be succinct and natural, yielding high prior probability. Let denote the gold-standard MR of . Consider the ideal case where and is positive, while is negative for other imperfect samples , . In this ideal case, would serve as a positive training example and other samples would be treated as negative examples. Therefore, the inference model would receive informative gradient updates, and learn to discriminate between gold and imperfect MRs. This intuition is similar in spirit to recent efforts in interpreting gradient update rules in reinforcement learning (Guu et al., 2017). We will present more empirical statistics and observations in § 4.3.

## 4 Experiments

### 4.1 Datasets

In our semi-supervised semantic parsing experiments, it is of interest how StructVAE could further improve upon a supervised parser with extra unlabeled data. We evaluate on two datasets:

Semantic Parsing We use the Atis dataset, a collection of 5,410 telephone inquiries of flight booking (e.g.“Show me flights from ci0 to ci1”). The target MRs are defined using -calculus logical forms (e.g., “lambda $0 e (and (flight$0) (from $ci0) (to$ci1))”). We use the pre-processed dataset released by Dong and Lapata (2016), where entities (e.g., cities) are canonicalized using typed slots (e.g.ci0). To predict -calculus logical forms using our transition-based parser, we use the ASDL grammar defined by Rabinovich et al. (2017) to convert between logical forms and ASTs (see Appendix C for details).

Code Generation The Django dataset Oda et al. (2015) contains 18,805 lines of Python source code extracted from the Django web framework. Each line of code is annotated with an NL utterance. Source code in the Django dataset exhibits a wide variety of real-world use cases of Python, including IO operation, data structure manipulation, class/function definition, etc. We use the pre-processed version released by Yin and Neubig (2017) and use the astor package to convert ASDL ASTs into Python source code.

### 4.2 Setup

Labeled and Unlabeled Data StructVAE requires access to extra unlabeled NL utterances for semi-supervised learning. However, the datasets we use do not accompany with such data. We therefore simulate the semi-supervised learning scenario by randomly sub-sampling examples from the training split of each dataset as the labeled set . To make the most use of the NL utterances in the dataset, we construct the unlabeled set using all NL utterances in the training set34.

Training Procedure Optimizing the unsupervised learning objective Eq. 3 requires sampling structured MRs from the inference model . Due to the complexity of the semantic parsing problem, we cannot expect any valid samples from randomly initialized . We therefore pre-train the inference and reconstruction models using the supervised objective Eq. 2 until convergence, and then optimize using the semi-supervised learning objective Eq. 1. Throughout all experiments we set (Eq. 1) and (Eq. 3) to 0.1. The sample size is 5. We observe that the variance of the learning signal could still be high when low-quality samples are drawn from the inference model . We therefore clip all learning signals lower than . Early-stopping is used to avoid over-fitting. We also pre-train the prior  (§ 3.3) and the baseline function Eq. 6. Readers are referred to Appendix D for more detail of the configurations.

Metric As standard in semantic parsing research, we evaluate by exact-match accuracy.

### 4.3 Main Results

Tab. 1 and Tab. 2 list the results on Atis and Django, resp, with varying amounts of labeled data . We also present results of training the transition-based parser using only the supervised objective (Sup.Eq. 2). We also compare StructVAE with self-training (SelfTrain), a semi-supervised learning baseline which uses the supervised parser to predict MRs for unlabeled utterances in , and adds the predicted examples to the training set to fine-tune the supervised model. Results for StructVAE are averaged over four runs to account for the additional fluctuation caused by REINFORCE training.

Supervised System Comparison First, to highlight the effectiveness of our transition parser based on ASDL grammar (hence the reliability of our supervised baseline), we compare the supervised version of our parser with existing parsing models. On Atis, our supervised parser trained on the full data is competitive with existing neural network based models, surpassing the Seq2Tree model, and on par with the Abstract Syntax Network (ASN) without using extra supervision. On Django, our model significantly outperforms the YN17 system, probably because the transition system used by our parser is defined natively to construct ASDL ASTs, reducing the number of actions for generating each example. On Django, the average number of actions is 14.3, compared with 20.3 reported in YN17.

Semi-supervised Learning Next, we discuss our main comparison between StructVAE with the supervised version of the parser (recall that the supervised parser is used as the inference model in StructVAE§ 3.2). First, comparing our proposed StructVAE with the supervised parser when there are extra unlabeled data (i.e. for Atis and for Django), semi-supervised learning with StructVAE consistently achieves better performance. Notably, on Django, our model registers results as competitive as previous state-of-the-art method (YN17) using only half the training data ( when  v.s. 71.6 for YN17). This demonstrates that StructVAE is capable of learning from unlabeled NL utterances by inferring high quality, structurally rich latent meaning representations, further improving the performance of its supervised counterpart that is already competitive. Second, comparing StructVAE with self-training, we find StructVAE outperforms SelfTrain in eight out of ten settings, while SelfTrain under-performs the supervised parser in four out of ten settings. This shows self-training does not necessarily yield stable gains while StructVAE does. Intuitively, StructVAE would perform better since it benefits from the additional signal of the quality of MRs from the reconstruction model (§ 3.3), for which we present more analysis in our next set of experiments.

For the sake of completeness, we also report the results of StructVAE when is the full training set. Note that in this scenario there is no extra unlabeled data disjoint with the labeled set, and not surprisingly, StructVAE does not outperform the supervised parser. In addition to the supervised objective Eq. 2 used by the supervised parser, StructVAE has the extra unsupervised objective Eq. 3, which uses sampled (probably incorrect) MRs to update the model. When there is no extra unlabeled data, those sampled (incorrect) MRs add noise to the optimization process, causing StructVAE to under-perform.

Study of Learning Signals As discussed in § 3.3, in semi-supervised learning, the gradient received by the inference model from each sampled latent MR is weighted by the learning signal. Empirically, we would expect that on average, the learning signals of gold-standard samples , , are positive, larger than those of other (imperfect) samples , . We therefore study the statistics of and for all utterances , i.e., the set of utterances which are not included in the labeled set.5 The statistics are obtained by performing inference using trained models. Figuresa andb depict the histograms of learning signals on Django and Atis, resp. We observe that the learning signals for gold samples concentrate on positive intervals. We also show the mean and variance of the learning signals. On average, we have being positive and negative. Also note that the distribution of has smaller variance and is more concentrated. Therefore the inference model receives informative gradient updates to discriminate between gold and imperfect samples. Next, we plot the distribution of the rank of , among the learning signals of all samples of , . Results are shown in Fig. 9. We observe that the gold samples have the largest learning signals in around 80% cases. We also find that when has the largest learning signal, its average difference with the learning signal of the highest-scoring incorrect sample is 1.27 and 0.96 on Django and Atis, respectively.

Finally, to study the relative contribution of the reconstruction score and the prior to the learning signal, we present examples of inferred latent MRs during training (Tab. 3). Examples 1&2 show that the reconstruction score serves as an informative quality measure of the latent MR, assigning the correct samples with high , leading to positive learning signals. This is in line with our assumption that a good latent MR should adequately encode the semantics of the utterance. Example 3 shows that the prior is also effective in identifying “unnatural” MRs (e.g., it is rare to add a function and a string literal, as in ). These results also suggest that the prior and the reconstruction model perform well with linearization of MRs. Finally, note that in Examples 2&3 the learning signals for the correct samples are positive even if their inference scores are lower than those of . This result further demonstrates that learning signals provide informative gradient weights for optimizing the inference model.

Generalizing to Other Latent MRs Our main results are obtained using a strong AST-based semantic parser as the inference model, with copy-augmented reconstruction model and an LSTM language model as the prior. However, there are many other ways to represent and infer structure in semantic parsing (Carpenter, 1998; Steedman, 2000), and thus it is of interest whether our basic StructVAE framework generalizes to other semantic representations. To examine this, we test StructVAE using -calculus logical forms as latent MRs for semantic parsing on the Atis domain. We use standard sequence-to-sequence networks with attention (Luong et al., 2015) as inference and reconstruction models. The inference model is trained to construct a tree-structured logical form using the transition actions defined in Cheng et al. (2017). We use a classical tri-gram Kneser-Ney language model as the prior. Tab. 4 lists the results for this StructVAE-Seq model.

We can see that even with this very different model structure StructVAE still provides significant gains, demonstrating its compatibility with different inference/reconstruction networks and priors. Interestingly, compared with the results in Tab. 1, we found that the gains are especially larger with few labeled examples — StructVAE-Seq achieves improvements of 8-10 points when . These results suggest that semi-supervision is especially useful in improving a mediocre parser in low resource settings.

Impact of Baseline Functions In § 3.3 we discussed our design of the baseline function incorporated in the learning signal (Eq. 4) to stabilize learning, which is based on a language model (LM) over utterances (Eq. 6). We compare this baseline with a commonly used one in REINFORCE training: the multi-layer perceptron (MLP). The MLP takes as input the last hidden state of the utterance given by the encoding LSTM of the inference model. Tab. 5 lists the results over sampled settings. We found that although StructVAE with the MLP baseline sometimes registers better performance on Atis, in most settings it is worse than our LM baseline, and could be even worse than the supervised parser. On the other hand, our LM baseline correlates well with the learning signal, yielding stable improvements over the supervised parser. This suggests the importance of using carefully designed baselines in REINFORCE learning, especially when the reward signal has large range (e.g., log-likelihoods).

Impact of the Prior Fig. 10 depicts the performance of StructVAE as a function of the KL term weight in Eq. 3. When StructVAE degenerates to a vanilla auto-encoder without the prior distribution (i.e., ), it under-performs the supervised baseline. This is in line with our observation in Tab. 3 showing that the prior helps identify unnatural samples. The performance of the model also drops when , suggesting that empirically controlling the influence of the prior to the inference model is important.

Impact of Unlabeled Data Size Fig. 11 illustrates the accuracies w.r.t. the size of unlabeled data. StructVAE yields consistent gains as the size of the unlabeled data increases.

## 5 Related Works

Semi-supervised Learning for NLP Semi-supervised learning comes with a long history (Zhu, 2005), with applications in NLP from early work of self-training (Yarowsky, 1995), and graph-based methods (Das and Smith, 2011), to recent advances in auto-encoders (Cheng et al., 2016; Socher et al., 2011; Zhang et al., 2017) and deep generative methods (Xu et al., 2017). Our work follows the line of neural variational inference for text processing (Miao et al., 2016), and resembles Miao and Blunsom (2016), which uses VAEs to model summaries as discrete latent variables for semi-supervised summarization, while we extend the VAE architecture for more complex, tree-structured latent variables.

Semantic Parsing Most existing works alleviate issues of limited parallel data through weakly-supervised learning, using the denotations of MRs as indirect supervision (Reddy et al., 2014; Krishnamurthy et al., 2016; Neelakantan et al., 2016; Pasupat and Liang, 2015; Yin et al., 2016). For semi-supervised learning of semantic parsing, Kate and Mooney (2007) first explore using transductive SVMs to learn from a semantic parser’s predictions. Konstas et al. (2017) apply self-training to bootstrap an existing parser for AMR parsing. Kociský et al. (2016) employ VAEs for semantic parsing, but in contrast to StructVAE’s structured representation of MRs, they model NL utterances as flat latent variables, and learn from unlabeled MR data. There have also been efforts in unsupervised semantic parsing, which exploits external linguistic analysis of utterances (e.g., dependency trees) and the schema of target knowledge bases to infer the latent MRs (Poon and Domingos, 2009; Poon, 2013). Another line of research is domain adaptation, which seeks to transfer a semantic parser learned from a source domain to the target domain of interest, therefore alleviating the need of parallel data from the target domain (Su and Yan, 2017; Fan et al., 2017; Herzig and Berant, 2018).

## 6 Conclusion

We propose StructVAE, a deep generative model with tree-structured latent variables for semi-supervised semantic parsing. We apply StructVAE to semantic parsing and code generation tasks, and show it outperforms a strong supervised parser using extra unlabeled data.

StructVAE: Tree-structured Latent Variable Models for Semi-supervised Semantic Parsing

Supplementary Materials

## Appendix A Generating Samples from StructVAE

StructVAE is a generative model of natural language, and therefore can be used to sample latent MRs and the corresponding NL utterances. This amounts to draw a latent MR from the prior , and sample an NL utterance from the reconstruction model . Since we use the sequential representation in the prior, to guarantee the syntactic well-formedness of sampled MRs from , we use a syntactic checker and reject any syntactically-incorrect samples6. Tab. 6 and Tab. 7 present samples from Django and Atis, respectively. These examples demonstrate that StructVAE is capable of generating syntactically diverse NL utterances.

## Appendix B Neural Network Architecture

### b.1 Prior p(z)

The prior is a standard LSTM language model (Zaremba et al., 2014). We use the sequence representation of , , to model . Specifically, let consisting of tokens, we have

 p(zs)=|zs|∏i=1p(zsi|zs

where denote the sequence of history tokens . At each time step , the probability of predicting given the context is modeled by an LSTM network

 p(zsi|zs

where denote the hidden state of the LSTM at time step , and is an embedding function.

### b.2 Reconstruction Model pθ(x|z)

We implement a standard attentional sequence-to-sequence network (Luong et al., 2015) with copy mechanism as the reconstruction network . Formally, given a utterance of words , the probability of generating a token is marginalized over the probability of generating from a closed-set vocabulary, and that of copying from the MR :

 p(xi|x

where and are computed by . denotes the attentional vector (Luong et al., 2015) at the -th time step:

 ~sci=tanh(Wc[cci;sci]). (7)

Here, is the -th decoder hidden state of the reconstruction model, and the context vector (Bahdanau et al., 2015) obtained by attending to the source encodings. The probability of copying the -th token in , , is given by a pointer network (Vinyals et al., 2015), derived from and the encoding of , .

 p(xi=zsj|copy,x

### b.3 Inference Model pϕ(z|x)

Our inference model (i.e., the semantic parser) is based on the code generation model proposed in Yin and Neubig (2017). As illustrated in Fig. 2 and elaborated in § 3.2, our transition parser constructs an abstract syntax tree specified under the ASDL formalism using a sequence of transition actions. The parser is a neural sequence-to-sequence network, whose recurrent decoder is augmented with auxiliary connections following the topology of ASTs. Specifically, at each decoding time step , an LSTM decoder uses its internal hidden state to keep track of the generation process of a derivation AST

 st=fLSTM([at−1:~st−1:pt],st−1)

where denotes vector concatenation. is the embedding of the previous action. is the input-feeding attentional vector as in Luong et al. (2015). is a vector that captures the information of the parent frontier field in the derivation AST, which is the concatenation of four components: , which is the embedding of the current frontier field on the derivation; , which is the embedding of the type of ; , which is the state of the decoder at which the frontier field was generated by applying its parent constructor to the derivation; , which is the embedding of the parent constructor .

Given the current state of the decoder, , an attentional vector is computed similar as Eq. 7 by attending to input the utterance . The attentional vector is then used as the query vector to compute action probabilities, as elaborated in §4.2.2 of Yin and Neubig (2017).

## Appendix C ASDL Grammar for Atis

We use the ASDL grammar defined in Rabinovich et al. (2017) to deterministically convert between -calculus logical forms and ASDL ASTs:

expr = Variable(var variable)
| Entity(ent entity)
| Number(num number)
| Apply(pred predicate, expr* arguments)
| Argmax(var variable, expr domain, expr body)
| Argmin(var variable, expr domain, expr body)
| Count(var variable, expr body)
| Exists(var variable, expr body)
| Lambda(var variable, var_type type, expr body)
| Max(var variable, expr body)
| Min(var variable, expr body)
| Sum(var variable, expr domain, expr body)
| The(var variable, expr body)
| Not(expr argument)
| And(expr* arguments)
| Or(expr* arguments)
| Compare(cmp_op op, expr left, expr right)
cmp_op = Equal | LessThan | GreaterThan

## Appendix D Model Configuration

Initialize Baselines StructVAE uses baselines to reduce variance in training. For our proposed baseline based on the language model over utterances (Eq. 6), we pre-train a language model using all NL utterances in the datasets. For terms and in Eq. 6, we determine their initial values by first train StructVAE starting from and for a few epochs, and use their optimized values. Finally we initialize to 0.5 and to for Atis, and to 0.9 and to 2.0 for Django. We perform the same procedure to initialize the bias term in the MLP baseline, and have .

Pre-trained Priors StructVAE requires pre-trained priors  (§ 3.3). On Atis, we train a prior for each labeled set of size using the MRs in . For Django, we use all source code in Django that is not included in the annotated dataset.

Hyper-Parameters and Optimization For all experiments we use embeddings of size 128, and LSTM hidden size of 256. For the transition parser, we use the same hyper parameters as Yin and Neubig (2017), except for the node (field) type embedding, which is 64 for Django and 32 for Atis. To avoid over-fitting, we impose dropouts on the LSTM hidden states, with dropout rates validated among . We train the model using Adam (Kingma and Ba, 2014), with a batch size of 10 and 25 for the supervised and unsupervised objectives, resp. We apply early stopping, and reload the best model and halve the learning rate when the performance on the development set does not increase after 5 epochs. We repeat this procedure for 5 times.

## Appendix E Seq2Tree Results on Atis Data Splits

We also present results of Seq2Tree (Dong and Lapata, 2016) trained on the data splits used in Tab. 1, as shown in Tab. 8. Our supervised parser performs consistently better than Seq2Tree. This is probably due to the fact that our transition-based parser encodes the grammar of the target logical form a priori under the ASDL specification, in contrast with Seq2Tree which need to learn the grammar from the data. This would lead to improved performance when the amount of parallel training data is limited.

### Footnotes

1. Code available at http://pcyin.me/struct_vae
2. Linearizion is used by the prior and the reconstruction model only, and not by the inference model.
3. We also tried constructing using the disjoint portion of the NL utterances not presented in the labeled set , but found this yields slightly worse performance, probably due to lacking enough unlabeled data. Interpreting these results would be an interesting avenue for future work.
4. While it might be relatively easy to acquire additional unlabeled utterances in practical settings (e.g., through query logs of a search engine), unfortunately most academic semantic parsing datasets, like the ones used in this work, do not feature large sets of in-domain unlabeled data. We therefore perform simulated experiments instead.
5. We focus on cases where is in the sample set .
6. We found most samples from are syntactically well-formed, with 98.9% and 95.3% well-formed samples out of 100 samples on Atis and Django, respectively.

### References

1. Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015. Neural machine translation by jointly learning to align and translate. In Proceedings of ICLR.
2. Laura Banarescu, Claire Bonial, Shu Cai, Madalina Georgescu, Kira Griffitt, Ulf Hermjakob, Kevin Knight, Philipp Koehn, Martha Palmer, and Nathan Schneider. 2013. Abstract meaning representation for sembanking. In Proceedings of LAW-ID@ACL.
3. Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang. 2013. Semantic parsing on freebase from question-answer pairs. In Proceedings of EMNLP.
4. Samuel R. Bowman, Luke Vilnis, Oriol Vinyals, Andrew M. Dai, Rafal Józefowicz, and Samy Bengio. 2016. Generating sentences from a continuous space. In Proceedings of the SIGNLL.
5. Bob Carpenter. 1998. Type-logical Semantics.
6. Jianpeng Cheng, Siva Reddy, Vijay Saraswat, and Mirella Lapata. 2017. Learning structured natural language representations for semantic parsing. In Proceedings of ACL.
7. Yong Cheng, Wei Xu, Zhongjun He, Wei He, Hua Wu, Maosong Sun, and Yang Liu. 2016. Semi-supervised learning for neural machine translation. In Proceedings of ACL.
8. James Clarke, Dan Goldwasser, Ming-Wei Chang, and Dan Roth. 2010. Driving semantic parsing from the world’s response. In Proceedings of CoNLL.
9. Dipanjan Das and Noah A. Smith. 2011. Semi-supervised frame-semantic parsing for unknown predicates. In Proceedings of HLT.
10. Li Dong and Mirella Lapata. 2016. Language to logical form with neural attention. In Proceedings of ACL.
11. Xing Fan, Emilio Monti, Lambert Mathias, and Markus Dreyer. 2017. Transfer learning for neural semantic parsing. In Proceedings of the 2nd Workshop on Representation Learning for NLP.
12. Jiatao Gu, Zhengdong Lu, Hang Li, and Victor O. K. Li. 2016. Incorporating copying mechanism in sequence-to-sequence learning. In Proceedings of ACL.
13. Kelvin Guu, Panupong Pasupat, Evan Zheran Liu, and Percy Liang. 2017. From language to programs: Bridging reinforcement learning and maximum marginal likelihood. In Proceedings of ACL.
14. Jonathan Herzig and Jonathan Berant. 2018. Decoupling structure and lexicon for zero-shot semantic parsing. arXiv preprint arXiv:1804.07918 .
15. Srinivasan Iyer, Ioannis Konstas, Alvin Cheung, Jayant Krishnamurthy, and Luke Zettlemoyer. 2017. Learning a neural semantic parser from user feedback. In Proceedings of ACL.
16. Robin Jia and Percy Liang. 2016. Data recombination for neural semantic parsing. In Proceedings of ACL.
17. Rohit J. Kate and Raymond J. Mooney. 2007. Semi-supervised learning for semantic parsing using support vector machines. In Proceedings of NAACL-HLT.
18. Diederik P. Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. CoRR abs/1412.6980.
19. Diederik P Kingma, Shakir Mohamed, Danilo Jimenez Rezende, and Max Welling. 2014. Semi-supervised learning with deep generative models. In Proceedings of NIPS.
20. Diederik P Kingma and Max Welling. 2013. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114 .
21. Tomás Kociský, Gábor Melis, Edward Grefenstette, Chris Dyer, Wang Ling, Phil Blunsom, and Karl Moritz Hermann. 2016. Semantic parsing with semi-supervised sequential autoencoders. In Proceedings of EMNLP.
22. Ioannis Konstas, Srinivasan Iyer, Mark Yatskar, Yejin Choi, and Luke Zettlemoyer. 2017. Neural amr: Sequence-to-sequence models for parsing and generation. In Proceedings of ACL.
23. Jayant Krishnamurthy, Oyvind Tafjord, and Aniruddha Kembhavi. 2016. Semantic parsing to probabilistic programs for situated question answering. In Proceedings of EMNLP.
24. Chen Liang, Jonathan Berant, Quoc Le, Kenneth D. Forbus, and Ni Lao. 2017. Neural symbolic machines: Learning semantic parsers on freebase with weak supervision. In Proceedings of ACL.
25. Percy Liang, Michael I. Jordan, and Dan Klein. 2011. Learning dependency-based compositional semantics. In Proceedings of ACL.
26. Wang Ling, Phil Blunsom, Edward Grefenstette, Karl Moritz Hermann, Tomás Kociský, Fumin Wang, and Andrew Senior. 2016. Latent predictor networks for code generation. In Proceedings of ACL.
27. Thang Luong, Hieu Pham, and Christopher D. Manning. 2015. Effective approaches to attention-based neural machine translation. In Proceedings of EMNLP.
28. Yishu Miao and Phil Blunsom. 2016. Language as a latent variable: Discrete generative models for sentence compression. In Proceedings of EMNLP.
29. Yishu Miao, Lei Yu, and Phil Blunsom. 2016. Neural variational inference for text processing. In Proceedings of ICML.
30. Dipendra K. Misra and Yoav Artzi. 2016. Neural shift-reduce CCG semantic parsing. In Proceedings of EMNLP.
31. Arvind Neelakantan, Quoc V. Le, and Ilya Sutskever. 2016. Neural programmer: Inducing latent programs with gradient descent. In Proceedings of ICLR.
32. Yusuke Oda, Hiroyuki Fudaba, Graham Neubig, Hideaki Hata, Sakriani Sakti, Tomoki Toda, and Satoshi Nakamura. 2015. Learning to generate pseudo-code from source code using statistical machine translation (T). In Proceedings of ASE.
33. Panupong Pasupat and Percy Liang. 2015. Compositional semantic parsing on semi-structured tables. In Proceedings of ACL.
34. Hoifung Poon. 2013. Grounded unsupervised semantic parsing. In Proceedings of ACL.
35. Hoifung Poon and Pedro Domingos. 2009. Unsupervised semantic parsing. In Proceedings of EMNLP.
36. Python Software Foundation. 2016. Python abstract grammar. https://docs.python.org/2/library/ast.html.
37. Chris Quirk, Raymond J. Mooney, and Michel Galley. 2015. Language to code: Learning semantic parsers for if-this-then-that recipes. In Proceedings of ACL.
38. Maxim Rabinovich, Mitchell Stern, and Dan Klein. 2017. Abstract syntax networks for code generation and semantic parsing. In Proceedings of ACL.
39. Siva Reddy, Mirella Lapata, and Mark Steedman. 2014. Large-scale semantic parsing without question-answer pairs. Transactions of ACL .
40. Aarti Singh, Robert D. Nowak, and Xiaojin Zhu. 2008. Unlabeled data: Now it helps, now it doesn’t. In Proceedings of NIPS.
41. Richard Socher, Jeffrey Pennington, Eric H. Huang, Andrew Y. Ng, and Christopher D. Manning. 2011. Semi-supervised recursive autoencoders for predicting sentiment distributions. In Proceedings of EMNLP.
42. Mark Steedman. 2000. The Syntactic Process.
43. Yu Su and Xifeng Yan. 2017. Cross-domain semantic parsing via paraphrasing. In Proceedings of EMNLP.
44. Lappoon R. Tang and Raymond J. Mooney. 2001. Using multiple clause constructors in inductive logic programming for semantic parsing. In Proceedings of ECML.
45. Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. 2015. Pointer networks. In Proceedings of NIPS.
46. Adrienne Wang, Tom Kwiatkowski, and Luke Zettlemoyer. 2014. Morpho-syntactic lexical generalization for ccg semantic parsing. In Proceedings of EMNLP.
47. Daniel C. Wang, Andrew W. Appel, Jeffrey L. Korn, and Christopher S. Serra. 1997. The zephyr abstract syntax description language. In Proceedings of DSL.
48. Yushi Wang, Jonathan Berant, and Percy Liang. 2015. Building a semantic parser overnight. In Proceedings of ACL.
49. Ronald J. Williams. 1992. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning .
50. Chunyang Xiao, Marc Dymetman, and Claire Gardent. 2016. Sequence-based structured prediction for semantic parsing. In Proceedings of ACL.
51. Weidi Xu, Haoze Sun, Chao Deng, and Ying Tan. 2017. Variational autoencoder for semi-supervised text classification. In Proceedings of AAAI.
52. David Yarowsky. 1995. Unsupervised word sense disambiguation rivaling supervised methods. In Proceedings of ACL.
53. Wen-tau Yih, Ming-Wei Chang, Xiaodong He, and Jianfeng Gao. 2015. Semantic parsing via staged query graph generation: Question answering with knowledge base. In Proceedings of ACL.
54. Pengcheng Yin, Zhengdong Lu, Hang Li, and Ben Kao. 2016. Neural enquirer: Learning to query tables in natural language. In Proceedings of IJCAI.
55. Pengcheng Yin and Graham Neubig. 2017. A syntactic neural model for general-purpose code generation. In Proceedings of ACL.
56. Wojciech Zaremba, Ilya Sutskever, and Oriol Vinyals. 2014. Recurrent neural network regularization. arXiv preprint arXiv:1409.2329 .
57. John M. Zelle and Raymond J. Mooney. 1996. Learning to parse database queries using inductive logic programming. In Proceedings of AAAI.
58. Luke Zettlemoyer and Michael Collins. 2005. Learning to map sentences to logical form structured classification with probabilistic categorial grammars. In Proceedings of UAI.
59. Luke S. Zettlemoyer and Michael Collins. 2007. Online learning of relaxed ccg grammars for parsing to logical form. In Proceedings of EMNLP-CoNLL.
60. Xiao Zhang, Yong Jiang, Hao Peng, Kewei Tu, and Dan Goldwasser. 2017. Semi-supervised structured prediction with neural crf autoencoder. In Proceedings of EMNLP.
61. Victor Zhong, Caiming Xiong, and Richard Socher. 2017. Seq2sql: Generating structured queries from natural language using reinforcement learning. arXiv preprint arXiv:1709.00103 .
62. Chunting Zhou and Graham Neubig. 2017. Multi-space variational encoder-decoders for semi-supervised labeled sequence transduction. In Proceedings of ACL.
63. Xiaojin Zhu. 2005. Semi-supervised learning literature survey. Technical Report 1530, Computer Sciences, University of Wisconsin-Madison.
You are adding the first comment!
How to quickly get a good reply:
• Give credit where it’s due by listing out the positive aspects of a paper before getting into which changes should be made.
• Be specific in your critique, and provide supporting evidence with appropriate references to substantiate general statements.
• Your comment should inspire ideas to flow and help the author improves the paper.

The better we are at sharing our knowledge with each other, the faster we move forward.
The feedback must be of minimum 40 characters and the title a minimum of 5 characters


text:
# Quantitative Hilbert irreducibility and almost prime values of polynomial discriminants

Recently AndersonGafniLemke OliverLowry-DudaZhang and myself uploaded ”Quantitative Hilbert irreducibility and almost prime values of polynomial discriminants” to the arXiv. Let ${H}$ be a large integer,

$\displaystyle V_n(H) = \{x^n + a_{n_1} x^{n-1} + \cdots + a_0 : a_{n-1} , \ldots , a_0 \in \mathbb{Z} \cap [-H,H]\},$

and

$\displaystyle E_n(H) = \#\{f \in V_n(H) : {\rm Gal}(f) \neq S_n\}.$

A classical principle going back to at least Hilbert is that a typical polynomial should have Galois group ${S_n}$, and this would suggest ${\#E_n(H)}$ is significantly smaller than ${\#V_n(H)}$. Van der Waerden conjectured that ${E_n(H) = o(\#V_n(H) /H)}$. Van der Waerden’s conjecture was almost proved quite recently by Chow and Dietmann (for ${n \neq 7,8,10}$), except they are not able to estimate

$\displaystyle E_n(H , A_n) = \#\{f \in V_n(H) : {\rm Gal}(f) = A_n\}.$

Gallagher showed, using the large sieve, that

We show the following.

${\ }$ Theorem 1: Let ${H}$ be a positive integer. then

$\displaystyle \#E_n(H , A_n) = O\left(\frac{\#V_n(H) H^{O(1/n)}}{H^{2/3}} \right). \ \ \ \spadesuit$${\ }$

We note that Bhargava recently announced a proof of ${E_n(H , A_n) = O(\#V_n(H) / H)}$, which is stronger than Theorem 1. We remark that our techniques also apply to counting polynomials with almost prime discriminants (see Theorem 1.2 and the related 1.3).

We briefly mention some of the ideas used to prove Theorem 1. Classical algebraic number theory reveals that if the Galois group of a polynomial ${f}$ is ${A_n}$, then ${\mu_p(f) = (-1)^{n+1}}$, where ${\mu_p}$ is the Mobius function for ${\mathbb{F}_p[x]}$. Thus we can employ a sieve to estimate ${\#E_n(H , A_n) }$. However, instead of using the large sieve, we use the small sieve (more precisely, the Selberg sieve). Using this naively gives a bound similar to that of Gallagher in (1), as expected. The key advantage of using the small sieve is we can seek improvements if we have good distribution results. After employing Poisson summation our task in then to understand local factors, which turns out to be basically

$\displaystyle \widehat{\mu_p}(\xi_{n-1} , \ldots , \xi_0) =,\ \ \ \ \$

$\displaystyle = \frac{1}{p^{n}}\sum_{a_0 , \ldots , a_{n-1} \in \mathbb{F}_p} \mu(x^n + a_{n-1} x^{n-1} + \ldots + a_0) \psi_p(\xi_{n-1} a_{n-1} + \cdots + a_0 \xi_0),\ \ \ \ \ (2)$

where ${\psi_p : \mathbb{F}_p \rightarrow \mathbb{F}_p}$ is an additive character. This is morally the same problem as estimating  $\displaystyle \sum_{n \leq x} \mu(n) e(nx)$, where ${\mu}$ is the classical Mobius function. Baker and Harman showed that GRH implies that for any ${\epsilon > 0}$

$\displaystyle |\sum_{n \leq x} \mu(n) e(nx)| \ll x^{3/4 + \epsilon}.$

As the Riemann hypothesis is known in the function field setting, such a bound should also hold for (2). Indeed Porritt showed this is the case and this allows us to establish Theorem 1.


text:
Chapter 73

Dislocations of the knee are rare. They are true orthopedic emergencies and have a significant association with soft tissue injuries and neurovascular compromise. A dislocated knee occurs most commonly after a major force is applied to the knee joint from motor vehicle trauma, pedestrian-vehicle collisions, bicycle collisions, or motorcycle collisions. The forces necessary to cause a dislocation of the knee joint often fracture the bones of the leg.

Complete dislocation of the knee joint results in a gross deformity that is confirmed by plain radiographs. Reduction by the Emergency Physician may be reasonable if the Orthopedic Surgeon is not immediately available and/or if the injured extremity shows signs of distal neurologic or vascular compromise.

A careful examination of the distal extremity must be performed and documented. It must include an assessment of the capillary refill, the dorsalis pedis pulse, the posterior tibial pulse, peroneal nerve function, and tibial nerve function.

A knee dislocation is the displacement of the tibiofemoral articulation. It involves the rupture of the anterior cruciate ligament, the posterior cruciate ligament, the joint capsule, and/or the collateral ligaments of the knee. Anterior knee dislocations are the most common type of knee dislocation. This injury is defined as anterior displacement of the tibia relative to the femur. It results from an acute hyperextension injury to the knee joint that ruptures the anterior cruciate ligament completely, the posterior cruciate ligament partially, and the posterior joint capsule, allowing for anterior tibiofemoral displacement. The collateral ligaments usually remain intact. Tibial spine fractures, osteochondral fractures of the tibia or femur, and meniscal injuries are avulsion-type fractures resulting from the rupture of the anterior cruciate ligament. Distal femoral epiphyseal separation, rather than complete dislocation, as a result of a hyperextension injury is more common in children.

An anterior knee dislocation is associated with a popliteal artery injury in 30 to 40 percent of patients.1 The popliteal artery is at particular risk for injury because it is anchored proximally at the adductor hiatus and distally at the soleus arch. The collateral circulation around the knee joint is relatively poor. Therefore disruption of the popliteal artery may result in distal ischemia and limb loss if the reduction is delayed. It is important to note that the presence of distal peripheral pulses and capillary refill does not preclude an arterial injury.

A posterior knee dislocation is defined as the posterior displacement of the tibia relative to the femur. It occurs less commonly than an anterior knee dislocation. It results from a direct force applied to the anterior tibia with the knee slightly flexed, which ruptures the posterior joint capsule and both cruciate ligaments. The collateral ligaments usually remain intact. It is associated with popliteal artery damage and disruption of the extensor mechanism of the knee joint.

A posterolateral knee dislocation is a rare type of knee dislocation that is associated with peroneal nerve injury in ...

Sign in to your MyAccess profile while you are actively authenticated on this site via your institution (you will be able to verify this by looking at the top right corner of the screen - if you see your institution's name, you are authenticated). Once logged in to your MyAccess profile, you will be able to access your institution's subscription for 90 days from any location. You must be logged in while authenticated at least once every 90 days to maintain this remote access.

Ok

## Subscription Options

### AccessEmergency Medicine Full Site: One-Year Subscription

Connect to the full suite of AccessEmergency Medicine content and resources including advanced 8th edition chapters of Tintinalli’s, high-quality procedural videos and images, interactive board review, an integrated drug database, and more.


text:
Find all School-related info fast with the new School-Specific MBA Forum

 It is currently 30 Apr 2016, 05:21

GMAT Club Daily Prep

Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

Events & Promotions

Events & Promotions in June
Open Detailed Calendar

Show Tags

17 Apr 2012, 15:47
thanks so much for all the advice, everyone! after my visits, i decided on wharton! sent in my deposit last night. was lucky enough to successfully negotiate some scholarship money too - not as much as NYU, but enough to make it not hurt as much!
GMAT Club Legend
Affiliations: HHonors Diamond, BGS Honor Society
Joined: 05 Apr 2006
Posts: 5926
Schools: Chicago (Booth) - Class of 2009
GMAT 1: 730 Q45 V45
Followers: 292

Kudos [?]: 1892 [0], given: 7

Show Tags

19 Apr 2012, 06:10
Expert's post
Lovely dude! And I think you made the right choice (plus getting them to cough up a bit more cash always feels good! )
_________________

Jon Frank

If you like the post, give it a KUDOS!

Re: Wharton or Stern w/$$? [#permalink] 19 Apr 2012, 06:10 Go to page Previous 1 2 [ 23 posts ] Similar topics Replies Last post Similar Topics: 4 Columbia () vs. NYU Stern ($$$$) vs. Wharton () 8 14 Apr 2014, 19:06 1 UCLA Anderson Full Ride vs. Wharton w no  6 25 Mar 2014, 20:27 8 MBA Decision: Stern vs. Johnson (w/$$$$) 11 04 Mar 2014, 13:58 32 Wharton w/no  vs. Columbia +$$\$ 24 14 Jan 2013, 17:43
Social impact investing: Kellogg w/ $$, Sloan or Wharton? 14 03 Apr 2012, 05:57 Display posts from previous: Sort by Wharton or Stern w/$$?

 Powered by phpBB © phpBB Group and phpBB SEO Kindly note that the GMAT® test is a registered trademark of the Graduate Management Admission Council®, and this site has neither been reviewed nor endorsed by GMAC®.


text:
# When is direction implied for a Chi Square test?

#### CornyKoala

##### New Member
Hi all,
In a Chi Square goodness of fit test, and also in a Chi Square test of independence, what are the criteria for when direction can/must be stated in the conclusion?

For example, "A boy is interested in whether cricket captains call heads and tails equally at the pre-game toss. A survey of 100 matches shows that heads was called 62 times and tails 38 times. What would you conclude of the captains' calling habits?"

Running a chi square goodness of fit test I have Chi-square(1, n=100) =5.76. At p=.05, critical chi-square= 3.84, so I reject the null hypothesis. My conclusion is that "there appears to be a statistically significant difference between the captains calling heads or tails..."

Can I state in the conclusion that more heads than tails are called? Or is that beyond the power of the goodness of fit test?

Thanks

#### obh

##### Active Member
Hint.

You describe a very specific case of the goodness of fit test when there are only 2 groups.
you can exchange the test (one tail goodness of fit) with proportion test (with 2 tails) based on Z, and I expect you to get the same results...

Now ask yourself the same question over z test, and the answer will be easy.
Now you can change from 2 tails to one tail ...