# On Turán inequality for ultraspherical polynomials

Ilia Krasikov  Department of Mathematical Sciences, Brunel University,
Uxbridge UB8 3PH United Kingdom<EMAIL_ADDRESS>
###### Abstract.

We show that the normalised ultraspherical polynomials,
$G_{n}^{(\lambda)}(x)=C_{n}^{(\lambda)}(x)/C_{n}^{(\lambda)}(1)$, satisfy the
following stronger version of Turán inequality,

$|x|^{\theta}\left(G_{n}^{(\lambda)}(x)\right)^{2}-G_{n-1}^{(\lambda)}(x)G_{n+1}^{(\lambda)}(x)\geq
0,\;\;\;|x|\leq 1,$

where $\theta=4/(2-\lambda)$ if $-1/2<\lambda\leq 0$, and
$\theta=2/(1+2\lambda)$ if $\lambda\geq 0$. We also provide a similar
generalisation of Turán inequalities for some symmetric orthogonal polynomials
with a finite or infinite support defined by a three term recurrence.

Keywords: Orthogonal polynomials, Turán inequality, ultraspherical
polynomials, Gegenbauer polynomials, three term recurrence.

_2010 Mathematics Subject Classification 33C45_

##  1\. Introduction

Let

$y_{n}(x)=G_{n}^{(\lambda)}(x)=\dfrac{C_{n}^{(\lambda)}(x)}{C_{n}^{(\lambda)}(1)}$

be the normalised ultraspherical polynomials, $G_{n}^{(\lambda)}(1)=1$. The
classical Turán inequality states [4] that

(1) $y_{n}^{2}(x)-y_{n-1}(x)y_{n+1}(x)\geq 0,\;\;\lambda\geq 0,\;\;|x|\leq 1.$

Gerhold and Kauers [2] gave a computer proof of the following stronger result
in the special case $\lambda=\frac{1}{2}$ of Legendre polynomials $P_{n}(x)$,

(2) $|x|P_{n}^{2}(x)-P_{n-1}(x)P_{n+1}(x)\geq 0,\;\;\;|x|\leq 1.$

In turn, this was extended by Nikolov and Pillwein to the ultraspherical case
[3],

(3) $|x|y_{n}^{2}(x)-y_{n-1}(x)y_{n+1}(x)\geq 0,\;\;\;-1/2<\lambda\leq
1/2,\;\;|x|\leq 1.$

In this paper we use an elementary geometric approach which, in particular,
leads to the following sharper generalization of (3):

######  Theorem 1.

For $\lambda>-1/2$ and $|x|\leq 1$ the following Turán type inequality holds,

(4)
$\Delta_{n}=\Delta_{n}^{(\lambda)}(x)=|x|^{\theta}y_{n}^{2}(x)-y_{n-1}(x)y_{n+1}(x)\geq
0,$

where

$\theta=\left\\{\begin{array}[]{cc}\dfrac{4}{2-\lambda}\,,&-1/2<\lambda\leq
0;\\\ &\\\ \dfrac{2}{1+2\lambda}\,,&\lambda\geq 0.\end{array}\right.$

Moreover, for $\lambda\geq 0$ the above value of $\theta$ is the best possible
for all $n\geq 1$.

For $-1/2<\lambda<0$ the obtained result $\theta=\dfrac{4}{2-\lambda}$ is not
sharp and, in fact, the maximal possible value of $\theta$ depends on $n$.
Note also that generally one must have $\theta\leq 2$ for all results of this
type. This is so because for any family of orthogonal polynomials defined by
the general three term recurrence

$p_{n+1}(x)=(b_{n}x+c_{n})p_{n}(x)-a_{n}p_{n-1}(x),$

the following easy to check identity holds for all $x\in\mathbb{R}$:

(5)
$\frac{(xb_{n}+c_{n})^{2}}{4a_{n}}\,p_{n}^{2}(x)-p_{n-1}(x)p_{n+1}(x)=\frac{(p_{n+1}(x)-a_{n}p_{n-1}(x))^{2}}{4a_{n}}\geq
0.$

Thus, all local maxima of the ratio
$\dfrac{p_{n-1}(x)p_{n+1}(x)}{p_{n}^{2}(x)}$ lie on the curve
$\dfrac{(xb_{n}+c_{n})^{2}}{4a_{n}}\,$. In particular, (5) is sharp in the
orthogonality interval.

For the normalised ultraspherical polynomials, which are defined by the
recurrence

(6) $(n+2\lambda)y_{n+1}=2(n+\lambda)xy_{n}-ny_{n-1},$

identity (5) yields

(7)
$\left(1+\dfrac{\lambda^{2}}{n(n+2\lambda)}\right)x^{2}y_{n}^{2}-y_{n-1}y_{n+1}\geq
0,\;\;\;x\in\mathbb{R}.$

Thus, the inequality

$x^{2}y_{n}^{2}-y_{n-1}y_{n+1}\geq 0,\;\;x\in[-1,1],$

is possible only for $\lambda=0$, that is, for Chebyshev $T_{n}$ polynomials.

Our proof of Theorem 1 can be extended to some other families of orthogonal
polynomials. In particular, we provide the following generalisation of the
case $\lambda<0$ of Theorem 1. Consider a family of symmetric polynomials
$p_{n}(x)$ orthogonal on $[-1,1]$ and normalised by $p_{n}(1)=1$. Let
$p_{-1}=0,\;p_{0}=1$ and $a_{0}=0$, then such polynomials are defined by the
following the three term recurrence,

(8) $(1-a_{n})p_{n+1}(x)=xp_{n}(x)-a_{n}p_{n-1}(x),\;\;\;0<a_{n}<1.$

######  Theorem 2.

Suppose that the sequence $a_{n}$ in (8) is decreasing and
$\frac{1}{2}<a_{n}<1$. Then the following Turán type inequality holds,

$\Delta_{n}=|x|^{\theta}p_{n}^{2}(x)-p_{n-1}(x)p_{n+1}(x)\geq 0,\;\;\;|x|\leq
1,$

where

(9) $\theta=\inf\limits_{n\geq
1}\dfrac{2\log\dfrac{(1-a_{n})\,a_{n+1}}{(1-a_{n+1})\,a_{n}}}{\log\dfrac{4(1-a_{n})\,a_{n+1}^{2}}{a_{n}}}.$

In the ultraspherical case and $-\frac{1}{2}<\lambda\leq 0$, this gives the
same value for $\theta$ as Theorem 1.

We will also consider orthogonal polynomials with (possibly) unbounded
support, the family which includes Hermite polynomials as a special case. It
was observed in [1] that the Turán inequality

(10) $p_{n}^{2}(x)-p_{n-1}(x)p_{n+1}(x)\geq 0$

holds for any family of monic symmetric orthogonal polynomials $p_{n}(x)$
defined by the three term recurrence

(11)
$p_{n+1}(x)=xp_{n}(x)-a_{n}p_{n-1}(x),\;\;p_{-1}=0,\;p_{0}=1,\;\;\;a_{n}>0,$

with the increasing coefficients $a_{n}$. We will show that (10) can also be
strengthened in the spirit of Theorem 1. Note that in the case of an unbounded
support, that is, $a_{n}\rightarrow\infty$ in (11), any inequality of the form

$\phi(x)p_{n}^{2}(x)-p_{n-1}(x)p_{n+1}(x)\geq 0,$

must satisfy $\lim\limits_{x\rightarrow\infty}\phi(x)=1$, as

$\lim\limits_{x\rightarrow\infty}\frac{p_{n-1}(x)p_{n+1}(x)}{p_{n}^{2}(x)}=1,$

and possibly even stronger restrictions due to the asymptotic behaviour of
$p_{n}(x)$.

######  Theorem 3.

Let $p_{n}(x)$ be a family of monic symmetric orthogonal polynomials
satisfying (11) with an increasing sequence $a_{n},\;n=1,2,...\,$. Then the
following Turán type inequality holds,

(12)
$\Delta_{n}(x)=\frac{x^{2}}{x^{2}+a_{n}-a_{n-1}}\,p_{n}^{2}(x)-p_{n-1}(x)p_{n+1}(x)\geq
0,\;\;\;x\in\mathbb{R}.$

In particular, for the Hermite polynomials in the monic or standard
normalisation [5] we have

(13) $\frac{x^{2}}{x^{2}+\frac{1}{2}}H_{n}^{2}(x)-H_{n-1}(x)H_{n+1}(x)\geq 0.$

It would be interesting to obtain similar inequalities for Laguerre type
polynomials orthogonal on $[0,\infty)$.

Our approach is based on the following observation. Setting

(14) $t=t_{n}(x)=\frac{p_{n+1}(x)}{p_{n}(x)}$

and using the corresponding three term recurrence, one can rewrite a Turán
type inequality as a quadratic form $Q(x)=A(x)t^{2}+B(x)t+C(x)$ in $t$, where
we have to assume that $A(x)>0$, since otherwise the form attains negative
values in the oscillatory region, where $t$ runs over all real values. Suppose
now that one wants to prove that
$Q_{n+1}(x)=A_{n+1}(x)t^{2}+B_{n+1}(x)t+C_{n+1}(x)\geq 0$, using that
$Q_{n}(x)=A_{n}(x)t^{2}+B_{n}(x)t+C_{n}(x)\geq 0$. Consider the corresponding
curves defined by the equalities

$\mathcal{T}_{n}(x)=A_{n}(x)\tau^{2}+B_{n}(x)\tau+C_{n}(x)=0,$

and

$\mathcal{T}_{n+1}(x)=A_{n+1}(x)\tau^{2}+B_{n+1}(x)\tau+C_{n+1}(x)=0.$

First, one checks that $\mathcal{T}_{n}(x)$ and $\mathcal{T}_{n+1}(x)$ do not
intersect by, say, showing that the resultant of the curves in $\tau$ does not
vanish. Next, since $Q_{n}(x)\geq 0$, quadratic $Q_{n+1}(x)$ could be negative
only inside the region enclosed by $\mathcal{T}_{n}(x)$. Therefore, it is
enough to check that the curves are nested with $\mathcal{T}_{n+1}(x)$ lying
inside $\mathcal{T}_{n}(x)$. Fig.1 illustrates the above arguments for the
ultraspherical case.

Figure 1. The black line is $t_{4}$; the blue and red lines show
$\mathcal{T}_{4}$ and $\mathcal{T}_{5}$, respectively, for three different
values of $\lambda$.

##  2\. Proof of Theorem 1

We will proceed by the induction on $n\geq 1$. Without loss of generality we
assume that $\theta<2$ and $x\in[0,1]$. Furthermore, when it is convenient, we
may restrict the value of $x$ to open interval $(0,1)$ treating the endpoints
$x=0,1$ as the limiting case.

Assume first that $-\frac{1}{2}<\lambda<0$ and check that $\Delta_{1}>0$. In
this case already the assumption $\theta<2$ will suffice. We have

$(1+2\lambda)\Delta_{1}=1-2(1+\lambda)x^{2}+(1+2\lambda)x^{2+\theta}\geq
1-2(1+\lambda)x^{2}+(1+2\lambda)x^{4}=$
$(1-x^{2})\left(1-(1+2\lambda)x^{2}\right)>0.$

For $\lambda>0$ and $\theta=\frac{2}{1+2\lambda}$, noticing that

$(1+2\lambda)\frac{d\Delta_{1}}{dx}=-4(1+\lambda)(1-x^{\theta})x\leq 0,$

one finds

$\Delta_{1}(x)>\Delta_{1}(1)=0.$

Note that for $n=1$ the chosen value $\theta=\frac{2}{1+2\lambda}$ is the best
possible because the expansion of $\Delta_{1}$ into the Taylor series around
$x=1$ is

$(1+2\lambda)\Delta_{1}(x)=\left(2-(1+2\lambda)\theta\right)(1-x)+O((1-x)^{2}).$

More work is needed for the induction step in order to show that
$\Delta_{n}>0$ implies $\Delta_{n+1}>0$. We split the proof into a few lemmas.

As in (14), for fixed $n$ and $\lambda$ using we introduce the function

$t=t_{n}^{(\lambda)}(x)=\dfrac{G_{n+1}^{(\lambda)}(x)}{G_{n}^{(\lambda)}(x)}\,.$

Using (6), we can rewrite $\Delta_{n}$ and $\Delta_{n+1}$ as follows,

(15)
$\frac{n\Delta_{n}}{\left(G_{n}^{(\lambda)}(x)\right)^{2}}=(n+2\lambda)t^{2}-2(n+\lambda)xt+nx^{\theta},$

(16)
$\frac{(n+2\lambda+1)\Delta_{n+1}}{\left(G_{n}^{(\lambda)}(x)\right)^{2}}=(n+2\lambda+1)x^{\theta}t^{2}-2(n+\lambda+1)xt+n+1.$

Now consider the corresponding curves

$\mathcal{T}_{n}=(n+2\lambda)\tau_{n}^{2}-2(n+\lambda)x\tau_{n}+nx^{\theta}=0,$

and

$\mathcal{T}_{n+1}=(n+2\lambda+1)x^{\theta}\tau_{n+1}^{2}-2(n+\lambda+1)x\tau_{n+1}+n+1=0,$

or explicitly,

(17)
$\tau_{n}=\frac{(n+\lambda)x\pm\sqrt{(n+\lambda)^{2}x^{2}-n(n+2\lambda)x^{\theta}}}{n+2\lambda}\,,$
(18)
$\tau_{n+1}=\frac{(n+\lambda+1)x\pm\sqrt{(n+\lambda+1)^{2}x^{2}-(n+1)(n+2\lambda+1)x^{\theta}}}{(n+2\lambda+1)x^{\theta}}\,,$

where $0\leq x\leq 1$. Both curves have a single component and are
simultaneously real for

(19) $x\geq
x_{0}=\left(\frac{(n+1)(n+2\lambda+1)}{(n+\lambda+1)^{2}}\right)^{1/(2-\theta)}\,,$

where $x_{0}$ is just the vertex of $\mathcal{T}_{n+1}$. Thus, for $x\leq
x_{0}$ both functions $\Delta_{n}$ and $\Delta_{n+1}$ are nonnegative, the
first one by the induction hypothesis. So (as it will be necessary for
$\lambda<0$), we may restrict the proof to $x>x_{0}$.

To show that $\mathcal{T}_{n}$ and $\mathcal{T}_{n+1}$ do not intersect, we
calculate resultant $R_{n}(x,\theta)$ of $\mathcal{T}_{n}(x)$ and
$\mathcal{T}_{n+1}(x)$ in $t$ and check that it does not vanish.

######  Lemma 4.

Let $0<x<1$, $\lambda>-1/2$, and $\theta$ is defined in Theorem 1, then
$R_{n}(x,\theta)>0$.

###### Proof.

The resultant of $\mathcal{T}_{n}(x)$ and $\mathcal{T}_{n+1}(x)$ in $\tau$ can
be written as

$R_{n}(x,\theta)=A^{2}-4x^{2}BC,$

where

$A=n(n+2\lambda+1)x^{2\theta}-(n+1)(n+2\lambda),$
$B=n(n+\lambda+1)x^{\theta}-(n+1)(n+\lambda),$
$C=(n+\lambda)(n+2\lambda+1)x^{\theta}-(n+\lambda+1)(n+2\lambda).$

We shall consider two cases.

Case 1. $\lambda>0$. First, we observe that $R_{0}(x,\theta)>0$ for
$\theta=\frac{2}{1+2\lambda}$ and $x<1$. Indeed,

$\frac{1}{4\lambda^{2}}\,R_{0}(x,\theta)=1-2(1+\lambda)x^{2}+(1+2\lambda)x^{2+\frac{2}{1+2\lambda}}>0,$

since

$\frac{\partial}{\partial\lambda}\left(\frac{1}{4\lambda^{2}}\,R_{0}(x,\theta)\right)=4(1+\lambda)(x^{\theta}-1)x<0,$

and

$\lim_{\lambda\rightarrow
0}\frac{1}{4\lambda^{2}}\,R_{0}(x,\theta)=(1-x^{2})^{2}>0.$

Hence, it will be enough to prove the following inequality,

$\frac{R_{n}(x,\theta)-R_{0}(x,\theta)}{n(n+2\lambda+1)(1-x^{\theta})}=n(n+2\lambda+1)(1-x^{\theta})(1-2x+x^{\theta})(1+2x+x^{\theta})\,+$
$4\lambda\left(1-(3+\lambda)x^{2}+(1+x^{2}+\lambda x^{2})x^{\theta}\right)>0.$

This is indeed the case, as the first summand is positive by $\theta<2$. The
second one is positive for any $0<\theta<2$ as well, since

$\frac{\partial}{\partial\lambda}\left(1-(3+\lambda)x^{2}+(1+x^{2}+\lambda
x^{2})x^{\theta}\right)=x^{2}(x^{\theta}-1)<0,$

and for $\lambda=0$ we have

$1-(3+\lambda)x^{2}+(1+x^{2}+\lambda
x^{2})x^{\theta}=1-3x^{2}+x^{\theta}+x^{2+\theta}>(1-x^{2})^{2}>0.$

Case 2. $-1/2<\lambda<0$. To show that $R_{n}(x,\theta)>0$, we may assume that
$BC>0$, otherwise there is nothing to prove. By $\theta<2$ we have

$R_{n}(x,\theta)=A^{2}-4x^{2}BC\geq A^{2}-4x^{\theta}BC=$
$z(nz+2\lambda)\left((n+2\lambda+1)z-2\lambda\right)\left((n+2\lambda+1)nz-2\lambda\right),\;\;\;z=1-x^{\theta}.$

This implies that $R_{n}(x,\theta)>0$ for
$\dfrac{(n+1)(n+2\lambda)}{n(n+2\lambda+1)}<x<1$.

We have to show that $R_{n}(x,\theta)\geq 0$ only for $x_{0}<x<1$, where
$x_{0}$ is defined by (19). Hence, it is enough to check that for
$\theta=4/(2-\lambda)$,

$x_{0}^{\theta}>\dfrac{(n+1)(n+2\lambda)}{n(n+2\lambda+1)}\,,$

or, equivalently,

$g(n,\lambda)=2\ln\frac{(n+1)(n+2\lambda+1)}{(n+\lambda+1)^{2}}-\lambda\ln\frac{n(n+2\lambda+1)}{(n+1)(n+2\lambda)}>0.$

Since

$\frac{\partial g(n,\lambda)}{\partial
n}=-\frac{2\lambda^{2}(3n+2\lambda^{2}+3\lambda+1)}{n(n+1)(n+\lambda+1)(n+2\lambda)(n+2\lambda+1))}<0,$

we have

$g(n,\lambda)>\lim_{n\rightarrow\infty}g(n,\lambda)=0.$

This completes the proof.

∎

######  Lemma 5.

Let $0<x<1$, $\lambda>-1/2$, then the curves $\mathcal{T}_{n}$ and
$\mathcal{T}_{n+1}$ are nested, and $\mathcal{T}_{n+1}$ lies inside
$\mathcal{T}_{n}$.

###### Proof.

For $\lambda>0$, using an obvious notation for the branches of the roots in
(17) and (18), we obtain at $x=1$

$\left(\tau_{n}^{(+)},\tau_{n}^{(-)}\right)=\left(1,\frac{n}{n+2\lambda}\,\right),\;\;\;\left(\tau_{n+1}^{(+)},\tau_{n+1}^{(-)}\right)=\left(1,\frac{n+1}{n+2\lambda+1}\,\right).$

Similarly, for $\lambda<0$, we obtain

$\left(\tau_{n}^{(+)},\tau_{n}^{(-)}\right)=\left(\frac{n}{n+2\lambda}\,,1\right),\;\;\;\left(\tau_{n+1}^{(+)},\tau_{n+1}^{(-)}\right)=\left(\frac{n+1}{n+2\lambda+1}\,,1\right).$

Since the curves do not intersect for $x<1$, it follows that
$\mathcal{T}_{n+1}$ is enclosed inside $\mathcal{T}_{n}$. This completes the
proof of inequality (4).

∎

It is left to show that for $\lambda\geq 0$ the value $\theta=2/(2\lambda+1)$
is sharp for all $n\geq 1$. The following lemma completes the proof of Theorem
1.

######  Lemma 6.

Let $\lambda\geq 0$, then for any $n\geq 1$ inequality (4) does not hold with
$\theta>\frac{2}{1+2\lambda}$ for $x$ less than and sufficiently close to one.

###### Proof.

Expanding $\Delta_{n}$ into Taylor series around $x=1$ (we used Mathematica),
one gets

${n+2\lambda-1\choose
n}^{2}\Delta_{n}=\frac{(2-\theta-2\lambda\theta)\Gamma^{2}(n+2\lambda)}{(1+2\lambda)\Gamma^{2}(2\lambda)\,n!^{2}}\,(1-x)+O((1-x)^{2}).$

Hence, $\Delta_{n}<0$ in a vicinity of $x=1$ if
$\theta>\frac{2}{1+2\lambda}\,.$ Note that the main term of the expansion for
$\theta=\frac{2}{1+2\lambda}$ is

$\frac{16\lambda^{2}(3n^{2}+6\lambda
n+2\lambda^{2}-\lambda)\Gamma^{2}(n+2\lambda)}{(3+2\lambda)\Gamma^{2}(2\lambda+2)n!^{2}}\,(1-x)^{2},$

which is still positive. ∎

Since the vertex of $\mathcal{T}_{n}$ is situated at

$\tilde{x}=\left(\frac{n(n+2\lambda)}{(n+\lambda)^{2}}\right)^{1/(2-\theta)},\;\;\;\text{where}\;\;\;\frac{1}{2-\theta}=\left\\{\begin{array}[]{cc}\frac{1}{2}-\frac{1}{\lambda}\,,&-\frac{1}{2}<\lambda<0,\\\
&\\\ \frac{1}{2}+\frac{1}{4\lambda}\,,&\lambda\geq 0,\end{array}\right.$

the inequalities of Theorem 1 are non-trivial only in the intervals
$(\tilde{x},1)$ and $(-1,-\tilde{x})$. Outside these regions $\Delta_{n}>0$
just as a positive definite quadratic in $t_{n}$. In particular, for a fixed
$\lambda$ the length of these intervals shrinks to $O(n^{-2})$.

Using that $\Delta_{n}$ must be positive definite in the oscillatory region,
where $t_{n}$ runs through all real values, we can provide more information
about the location of vertex $\tilde{x}$ of $\mathcal{T}_{n}$ with respect to
the zeros of $C_{n+1}^{(\lambda)}(x)$.

######  Claim 1.

Let $x_{1}>x_{2}>\ldots>x_{n+1}$, be the zeros of $C_{n+1}^{(\lambda)}(x)$.
Then

$\tilde{x}>\left\\{\begin{array}[]{cc}x_{2},&-1/2<\lambda<0,\\\ &\\\
x_{1},&\lambda\geq 0.\end{array}\right.$

###### Proof.

First notice that $|x_{i}|<1$. If $\lambda=0$ the situation is trivial as
$\tilde{x}=1$. Assuming that $\lambda\neq 0$, we observe that $\Delta_{n}>0$
means that $t_{n}$ does not intersect $\mathcal{T}_{n}$. Notice also that
$t_{i}$ is an increasing function of $x$ for any $i$, as

$y_{n}^{2}(x)\frac{dt_{i}}{dx}=y^{\prime}_{n+1}(x)y_{n}(x)-y^{\prime}_{n}(x)y_{n+1}(x)>0$

is just the Christoffel-Darboux kernel. It is also easy to check that
$\mathcal{T}_{n}^{(-)}(x)$, the lower branch of $\mathcal{T}_{n}$, is positive
and decreasing in $x$. The situation when $x_{2}\geq\tilde{x}$ is impossible,
as then $t_{n}$ running through the whole interval $[0,\infty)$ intersects
$\mathcal{T}_{n}^{(-)}(x)$ at some point between $x_{2}$ and $x_{1}$. The same
is true regarding the interval $[x_{1},1]$, provided the intersection occurs
before $x=1$. For $x\in(x_{1},1]$, $t_{n}(x)$ increases from zero to one.
However $\tau_{n}^{(-)}(1)=\frac{n+\lambda-|\lambda|}{n+2\lambda}<1$ for
$\lambda>0$, where $\tau_{n}^{(\pm)}$ are defined by (17). Therefore the case
$x_{1}\geq\tilde{x}$ is impossible for $\lambda>0$, as otherwise $t$ and
$\mathcal{T}_{n}^{(-)}(x)$ would intersect inside the interval $(x_{1},1)$. ∎

The different situations appearing in the proof of Lemma 1 are illustrated in
Fig.1 for $n=4$ and three values of $\lambda$. Here $x_{2}<\tilde{x}<x_{1}$
for $\lambda=-\frac{1}{3}$, and $x_{1}<\tilde{x}$ for $\lambda=-\frac{1}{4}$
and $\lambda=1$. In general, the difference between cases $\lambda<0$ and
$\lambda>0$ in Lemma 1 occurs since $t$ passes below $\mathcal{T}_{n}$ for
$\lambda<0$ and above it for $\lambda>0$. For $\lambda<0$ we have
$\tau_{n}^{(-)}(1)=1$, and both situations, $x_{2}<\tilde{x}<x_{1}$ and
$x_{1}<\tilde{x}\leq 1$, may occur depending on the values of $\lambda$ and
$n$.

######  Remark 1.

It seems difficult to find the exact value of $\theta$ for
$-\frac{1}{2}<\lambda<0$. Let us note that for $\theta>\frac{8}{4-\lambda}$
the resultant changes the sign for sufficiently large $n$. Thus the curves
intersect and our arguments fail. Indeed, for $\theta>\frac{8}{4-\lambda}$, in
the notation of Lemma 5, the Taylor series expansion around $n=\infty$ at
$\hat{x}=\frac{3x_{0}+1}{4}$ yields,

$\tau_{n}^{(+)}(\hat{x})-\tau_{n+1}^{(+)}(\hat{x})=\frac{3\lambda\left((4-\lambda)\theta-8\right))}{4(2-\theta)n^{2}}+O(n^{-3})<0,$
$\tau_{n+1}^{(-)}(\hat{x})-\tau_{n}^{(-)}(\hat{x})=\frac{\lambda\left((4+3\lambda)\theta-8\right)}{4(2-\theta)n^{2}}+O(n^{-3})>0.$

For $\theta=\frac{8}{4-\lambda}$ the curves probably do not intersect as

$R_{n}(\hat{x},\,\frac{8}{4-\lambda})=\frac{9}{2}\,(8+\lambda^{2})\lambda^{4}n^{-4}+O(n^{-5})>0.$

##  3\. Proof of Theorem 2

###### Proof.

It is enough to consider the case $0<x<1$, as in Theorem 1. We may assume that
coefficients $a_{n}$ are strictly decreasing treating the general situation as
the limiting case. By the assumption $\theta<2$, we get

$\Delta_{1}=x^{2\theta}-\frac{x^{2}-a_{1}}{1-a_{1}}>\frac{1-x^{2}}{1-a_{1}}(2a_{1}-1)>0.$

Note also that if the Turán inequality of the theorem holds for some
$\theta_{0}$, it also holds for any $\theta<\theta_{0}$.

The proof is by the induction on $n$ and is similar to that of Theorem 1. To
show that $\Delta_{n+1}\geq 0$ we consider the following two expressions,

$\dfrac{a_{n}\Delta_{n}}{p_{n}^{2}(x)}\;\;\;\mbox{and}\;\;\;\dfrac{(1-a_{n+1})\Delta_{n+1}}{p_{n}^{2}(x)}\,,$

set $t=p_{n+1}(x)/p_{n}(x),$ and define the corresponding curves

$\mathcal{T}_{n}(x)=(1-a_{n})\tau^{2}-x\tau+a_{n}\tau^{\theta}=0,$
$\mathcal{T}_{n+1}(x)=(1-a_{n+1)}x^{\theta}\tau^{2}-x\tau+a_{n+1}=0,$

with the vertices

$\left(4a_{n}-4a_{n}^{2}\right)^{1/(2-\theta)}\;\text{and}\;\left(4a_{n+1}-4a_{n+1}^{2}\right)^{1/(2-\theta)},$

respectively. The both curves have a single component and are simultaneously
real for

$x\geq x_{0}=\left(4a_{n+1}-4a_{n+1}^{2}\right)^{1/(2-\theta)}.$

First, we have to show that $\mathcal{T}_{n}$ and $\mathcal{T}_{n+1}$ do not
intersect on $(0,1)$. The resultant of $\mathcal{T}_{n}$ and
$\mathcal{T}_{n+1}$ in $\tau$ is given by

(20) $R_{n}(x,\theta)=A^{2}-x^{2}BC,$

where

$A=a_{n}(1-a_{n+1})t^{2\theta}-(1-a_{n})a_{n+1},$ $B=a_{n+1}-a_{n}x^{\theta},$
$C=1-a_{n}-(1-a_{n+1})x^{\theta}.$

If $BC\leq 0$ there is nothing to prove. Otherwise, using $x^{2}<x^{\theta}$,
we get

$R_{n}(x,\theta)>A^{2}-x^{\theta}BC=$
$(1-x^{\theta})\left(1-a_{n}-a_{n}x^{\theta}\right)\left(a_{n+1}-(1-a_{n+1})x^{\theta}\right)\left(a_{n+1}(1-a_{n})-a_{n}(1-a_{n+1})x^{\theta}\right).$

Thus, $R_{n}(x,\theta)>0$ for

$\frac{a_{n+1}(1-a_{n})}{a_{n}(1-a_{n+1})}<x^{\theta}<1.$

Hence, the curves do not intersect on $(x_{0},1)$ if

$x_{0}^{\theta}>\frac{a_{n+1}(1-a_{n})}{a_{n}(1-a_{n+1})}\,.$

This yields inequality (9).

It is left to check that $\mathcal{T}_{n+1}(x)$ lies inside
$\mathcal{T}_{n}(x)$. For $x=1$, one finds

$\mathcal{T}^{(+)}_{n}(1)=\frac{a_{n}}{1-a_{n}}>\mathcal{T}_{n+1}^{(+)}(1)=\frac{a_{n+1}}{1-a_{n+1}}\,,\;\;\;\mathcal{T}_{n}^{(-)}(1)=\mathcal{T}_{n+1}^{(-)}(1)=1.$

Hence, the curves are nested with $\mathcal{T}_{n+1}$ lying inside
$\mathcal{T}_{n}$. ∎

######  Remark 2.

It is easy to show that for ultraspherical polynomials and $\lambda<0$,
Theorem 2 leads to the same result as Theorem 1. Indeed, for the
ultraspherical case, $a_{n}=\frac{n}{2(n+\lambda)}$, and

$F(n)=\dfrac{2\log\dfrac{(1-a_{n})\,a_{n+1}}{(1-a_{n+1})\,a_{n}}}{\log\dfrac{4(1-a_{n})\,a_{n+1}^{2}}{a_{n}}}=\dfrac{2\log\dfrac{(n+1)(n+2\lambda)}{n(n+2\lambda+1)}}{\log\dfrac{(n+1)^{2}(n+2\lambda)}{n(n+\lambda+1)^{2}}}\,.$

One finds $\frac{dF(n)}{dn}<0$, hence,

$\inf F(n)=\lim_{n\rightarrow\infty}F(n)=\frac{4}{2-\lambda}\,.$

On the other hand, an attempt to generalise the case $\lambda>0$, would
require to work with recurrence (8) for a growing sequence $a_{n}$, where
$a_{n}<1/2$. It is unclear how to extract $\theta$ from the inequality
$R_{n}(x,\theta)>0$ in that case.

##  4\. Proof of Theorem 3

###### Proof.

The proof is by the induction on $n$. Without loss of generality, we assume
that the sequence $a_{i}$ is strictly increasing and that $x>0$. It will be
convenient to set $a_{0}=0$, then $\Delta_{1}(x)=a_{1}^{2}/(x^{2}+a_{1})>0$.
Rewriting $\Delta_{n}$ and $\Delta_{n+1}$ in terms of
$t=\frac{p_{n+1}(x)}{p_{n}(x)}$, and setting $d_{i}=a_{i}-a_{i-1}>0$, we
consider $a_{n}(x^{2}+d_{n})\dfrac{\Delta_{n}(x)}{p_{n}^{2}(x)}$ and
$(x^{2}+d_{n+1})\dfrac{\Delta_{n+1}(x)}{p_{n}^{2}(x)}$. Then the corresponding
curves are

$\mathcal{T}_{n}(x)=(x^{2}+d_{n})\tau^{2}-(x^{2}+d_{n})x\tau+a_{n}x^{2}=0,$
$\mathcal{T}_{n+1}(x)=x^{2}\tau^{2}-(x^{2}+d_{n+1})x\tau+a_{n+1}(x^{2}+d_{n+1})=0.$

To show that $\mathcal{T}_{n}$ and $\mathcal{T}_{n+1}$ do not intersect, we
calculate the resultant in $\tau$. This yields a rather long expression of the
form

$\sum_{i=0}^{3}b_{i}\,x^{2i},$

where all $b_{i}$ are positive as they are composed of positive monomials.
Therefore the resultant does not vanish. We omit the details.

It is left to verify that the curves are nested and $\tau_{n+1}$ lies inside
$\tau_{n}$. For, it is enough to check that the value of $\mathcal{T}_{n}$ at
the vertex of $\mathcal{T}_{n+1}$ with coordinates

$\left(\sqrt{3a_{n+1}+a_{n}}\,,\dfrac{2a_{n+1}}{\sqrt{3a_{n+1}+a_{n}}}\right)$

is negative. Indeed, one calculates that it is

$-\frac{6d_{n+1}^{3}+(17a_{n}+2d_{n})d_{n+1}^{2}+6a_{n}(2a_{n}+d_{n})d_{n+1}+4a_{n}^{2}d_{n}}{3a_{n+1}+a_{n}}<0.$

Hence, $\Delta_{n+1}(x)>0$, provided $\Delta_{n}(x)>0$. This completes the
proof of (12).

Finally, let $H_{n}(x)$ and $\mathcal{H}_{n}(x)$ be the Hermite polynomials in
the standard and monic normalisation, respectively,
$\mathcal{H}_{n}(x)=2^{-n}H_{n}(x).$ Now (13) follows by $a_{n}=n/2$ in the
monic case.

∎

## References

  * [1] R. Askey, _Linearization of the Product of Orthogonal Polynomials_ , in _Problems in Analysis: A Symposium in Honor of Salomon Bochner (PMS-31), ed. Robert C. Gunning,_ Princeton University Press, (1970) 131–138.
  * [2] Stefan Gerhold and Manuel Kauers, _A computer proof of Turán’s inequality_ , J. Ineq. Pure Appl. Math. Vol. 7(2), #42, (2006).
  * [3] G. Nikolov, V. Pillwein, _An extension of Turán’s inequality for ultraspherical polynomials_ , Math. Inequal. Appl. 18(1) (2015), 321–335.
  * [4] O. Szász. _Inequalities concerning ultraspherical polynomials and Bessel functions_. Proc. Amer. Math. Soc. 1 (1950), 256–267.
  * [5] G. Szegö, Orthogonal Polynomials, Amer. Math. Soc. Colloq. Publ., v.23, Providence, RI, 1975.


# Toward Semi-Automatic Misconception Discovery Using Code Embeddings

Yang Shi<EMAIL_ADDRESS>North Carolina State UniversityRaleighNorth
CarolinaUSA27601 ,  Krupal Shah<EMAIL_ADDRESS>North Carolina State
UniversityRaleighNorth CarolinaUSA27601 ,  Wengran Wang<EMAIL_ADDRESS>North Carolina State UniversityRaleighNorth CarolinaUSA27601 ,  Samiha Marwan
<EMAIL_ADDRESS>North Carolina State UniversityRaleighNorth CarolinaUSA27601
,  Poorvaja Penmetsa<EMAIL_ADDRESS>North Carolina State
UniversityRaleighNorth CarolinaUSA27601 and  Thomas W. Price<EMAIL_ADDRESS>North Carolina State UniversityRaleighNorth CarolinaUSA27601

(2021)

###### Abstract.

Understanding students’ misconceptions is important for effective teaching and
assessment. However, discovering such misconceptions manually can be time-
consuming and laborious. Automated misconception discovery can address these
challenges by highlighting patterns in student data, which domain experts can
then inspect to identify misconceptions. In this work, we present a novel
method for the semi-automated discovery of problem-specific misconceptions
from students’ program code in computing courses, using a state-of-the-art
code classification model. We trained the model on a block-based programming
dataset and used the learned embedding to cluster incorrect student
submissions. We found these clusters correspond to specific misconceptions
about the problem and would not have been easily discovered with existing
approaches. We also discuss potential applications of our approach and how
these misconceptions inform domain-specific insights into students’ learning
processes.

Neural Network, Code Analysis, Automatic Assessment, Learning Representation

††journalyear: 2021††copyright: acmlicensed††conference: LAK21: 11th
International Learning Analytics and Knowledge Conference; April 12–16, 2021;
Irvine, CA, USA††booktitle: LAK21: 11th International Learning Analytics and
Knowledge Conference (LAK21), April 12–16, 2021, Irvine, CA, USA††price:
15.00††doi: 10.1145/3448139.3448205††isbn: 978-1-4503-8935-8/21/04††ccs:
Computing methodologies Learning latent representations††ccs: Applied
computing Education

##  1\. Introduction

An accurate understanding of students’ misconceptions on a given problem is
important for effective teaching and assessment of student knowledge.
Researchers can improve the performance of student models by explicitly
representing misconceptions (Liu et al., 2016). Students can benefit from
feedback on specific misconceptions, especially if those misconceptions are
detected automatically (e.g. in (Michalenko et al., 2017)). Moreover,
instructors can improve their lectures by explicitly addressing
misconceptions, and better assess student knowledge by incorporating them into
assignment rubrics. However, all of these applications first require
researchers to discover what misconceptions exist in a given domain, or on a
specific problem. For example, while instructors may already have rubrics to
assess performance, these rubrics’ items may focus on qualities of the
products created by students, rather than detecting specific misconceptions in
student knowledge. Discovering such misconceptions is time-consuming and
laborious, requiring experts to analyze traces of student work (Kurvinen et
al., 2016; Sirkiä and Sorva, 2012) or interviews (Caceffo et al., 2016). Such
high cost of analysis makes it difficult to discover these problem-specific
misconceptions.

Semi-automated misconception discovery can address these challenges by
highlighting patterns in student data, which domain experts then inspect to
identify misconceptions. However, existing discovery methods have focused on
simple association rules (Elmadani et al., 2012; Guzmán et al., 2010), rather
than state-of-the-art deep learning methods. Deep learning methods have
already been used to accurately assess student performance on complex tasks
(e.g. essay writing (Kuzi et al., 2019)). In doing so, they also learn to
represent students’ submissions as vectors, which makes it easier to visualize
and cluster submissions and find meaningful patterns that correspond to
students’ performance. This suggests that deep learning methods may be able to
go beyond assessment and support the discovery of misconceptions.

In this work, we present a novel method for the semi-automated discovery of
problem-specific misconceptions from students’ program code in computing
courses, using a state-of-the-art, deep learning code classification model
called code2vec (Alon et al., 2019). Our approach trains code2vec to predict
students’ success on a given problem, and then domain experts can use the
visualizations produced using code2vec, along with students’ scores on a
grading rubric, to quickly identify clusters of students who made similar
mistakes on the problem. We applied this technique to one block-based
programming problem from an introductory CS course for non-majors. We find
these clusters: 1) Correspond to specific misconceptions about the problem,
which could be addressed with targeted feedback, and 2) Identify groups of
students’ misconceptions that would not have been discovered from the rubric
alone, or with standard code clustering approaches. Additionally, while
code2vec has proven highly accurate at classifying code on large datasets, in
this paper we investigate its effectiveness at the novel task of assessing
student code on a much smaller dataset. We discuss potential applications of
our approach (e.g. refining rubrics, informing instruction and feedback), and
how these misconceptions inform domain-specific insights into students’
learning processes in a computing course. The primary contributions of this
work are: (1) a novel semi-automated method for identifying problem-specific
misconceptions (2) an evaluation of this method on one assignment in a
introductory computer science (CS0) course, revealing insights into students’
specific learning processes and challenges, and (3) an evaluation of code2vec
for automated code assessment, showing that it outperforms baseline models.

##  2\. Related Work

Misconceptions and Misconception Discovery: Misconceptions in computing
education refer to an incorrect understanding of a concept or a set of
concepts, which lead to making mistakes in writing or reading programs (Swidan
et al., 2018). They are commonplace among novice learners but are many times
invisible to experts and instructors (Sorva, 2013) – a phenomenon explained in
part by the “expert blind spot” (Nathan and Petrosino, 2003). Understanding
misconceptions helps instructors to be more informed, and provides raw
material for student modeling (Liu, 2016). Prior work has explored ways to
automatically detect students’ misconceptions (Michalenko et al., 2017),
however, these detectors required experts to label a training set with the
presence of misconceptions to train the model, which only works if we already
know what misconceptions to look for. In CS education, misconceptions have
been elicited through laborious manual analysis of students’ program code
(Paul and Vahrenhold, 2013) or interviews (Kaczmarczyk et al., 2010). In
addition, manual construction of “bug libraries” can be a difficult and time
consuming task for experts (Baffles, 1994). Nevertheless, such manual
analysis, especially on a sequence of program snapshots, has been shown to
provide more insightful information on students’ misconceptions. For example,
Davies et al. manually analysed students’ programming trace data to discover
misconceptions, and found that trace data revealed more knowledge gaps than
what has been shown in their final submissions (Davies et al., 2015). Other
work focused on data-driven discovery of misconceptions. For example, Guzman
et al. (Guzmán et al., 2010) used association rule mining to semi-
automatically elicit misconceptions from multiple-choice questions in a CS
practice test, and then allowed instructors to filter and verify meaningful
misconceptions. However, such semi-automated detection of misconceptions also
requires domain experts to analyze their rules to label them as constraints,
and is only focused on closed-ended multiple choice questions (MCQs), rather
than open-ended programming problems.

Automated Programming Code Assessment: Our approach builds on automated
assessment technologies to detect misconceptions. Automated assessments help
reduce instructor burden and enhance students’ learning. Much of the work on
automated assessment using learning algorithms has been implemented in complex
domains, such as open-ended learning environments (Segedy et al., 2011) and
essay grading (Kuzi et al., 2019). However, most of the work in CS education
domain has been limited to using test-cases for assessment (e.g. in (Edwards
and Murali, 2017)), rather than adapting these more advanced learning
approaches. These test-driven assessment frameworks run a student’s code with
hand-authored inputs, which requires additional instructor authoring effort
and is difficult to apply to some problems (e.g. those with complex input, or
graphical output). Some recent work has used machine learning algorithms to
predict students’ learning outcomes by extracting more information for
generalized and more complex problems (Mao et al., 2019; Azcona et al., 2019).
Building on this work, we leverage the code2vec model (Alon et al., 2019) to
extract structural information for automated program assessment, which in turn
forms the basis for our misconception discovery approach.

Assessment isn’t just about accuracy, it’s also about giving the student
actionable feedback. Rubrics help us do this. Automated approaches have also
been used to automatically extract rubrics. Clear rubrics provide
interpretable justification of why students succeeded or failed an assessment
(Diana et al., 2018). Prior work has explored automatic discovery of rubrics.
For example, Zhi et al. (Zhi et al., 2018) and Diana et al. (Diana et al.,
2018) automatically generated rubrics from students’ submissions by
identifying common features of correct solutions. Dimopoulos et al.
(Dimopoulos et al., 2013) created a Learning Management Systems plugin that
enhanced rubrics with additional info about students’ interaction data (e.g.
forum activity). However, none of these methods address how to improve rubrics
by highlighting specific student misconceptions.

Code Analysis and Representation: Recent advances in deep learning models for
code classification (Alon et al., 2019) suggest their potential for
applications in education. One problem that these models solve is that neither
code nor text representations can be directly translated into vector
representations to be processed by machine learning algorithms. One way that
natural language research solves this challenge is by using a trainable
embedding matrix to represent different text contents (Mikolov et al., 2013).
Recent approaches represent the unstructured program code in a structured
format that models can use as input. Among them, the most straightforward
approach is to represent code as a sequence of one-hot encoders, which does
not capture any of the structural information in code (Allamanis et al.,
2016). In CS education, Piech et al. (Piech et al., 2015) used a neural
network to learn student code embeddings – an abstract vector representation
of code – to identify which students would benefit from specific instructor
feedback. However, this model considers only the output of code and ignores
important structural information. They build their model based on the input
and outputs of the code to extract the code embeddings, which does not
leverage the important structural information for code itself. In this paper
we focus on a particular approach, code2vec (Alon et al., 2019), which
proposed expressive representations extracted from abstract syntax trees
(ASTs), which greatly outperform prior work on code classification tasks.
Recent work suggests that the embeddings produced by this approach may be
particularly useful for finding patterns in student code (Azcona et al.,
2019). In our work, we discover student misconceptions on a similar embedding
matrix to represent code contents.

##  3\. Method

Figure 1. Code2vec model. The input is represented as a set of paths
$(b_{0},...,b_{r})$, and the model outputs the grade distribution $\bm{p}$. We
extract the circled $\bm{E}$ as the embeddings for misconception discovery.
The embeddings are passed through the attention layer and used for generating
the prediction of students’ scores on the rubric.

The code2vec model learns a code embedding during training (highlighted in
Figure 1), which extracts relevant structural information from students’ code
with respect to their success on the problem. Using this embedding, we can
transform any student’s code submission into a vector, which can be compared
to other students’ vectors. We hypothesize that this vector representation may
be useful for identifying groups of students with similar misconceptions, more
so than overall syntactic similarity. Embeddings are similarly used in NLP
tasks (Mikolov et al., 2013) such as sentiment classification or translation
tasks. However, this vector space is sparse and large, and student submissions
are embedded non-linearly in the space. We therefore leverage t-SNE (Maaten
and Hinton, 2008) to perform non-linear dimensionality reduction, which allows
us to perform clustering and visualization more effectively.

We perform misconception discovery only on students who unsuccessfully
completed a given assignment. If a multi-item rubric is available, we can use
this to make misconception discovery more effective, by discovering
misconceptions among students who were unsuccessful at each individual rubric
item. Since a misconception may lead students to make a specific error on an
assignment, we hypothesize that students who performed poorly on a given
rubric are more likely to share a misconception. To discover these
misconception groups, we use the DBSCAN algorithm (Ester et al., 1996) to
cluster unsuccessful students into groups, which we hypothesize correspond to
misconceptions. Not all students will have a misconception who fail a rubric
item, so we use DBSCAN which can detect and remove noise point. The result is
a set of clusters, which an expert can view and interpret to identify a common
misconception among the submissions in each cluster.

##  4\. Experiment

We set out to answer the following research questions: RQ1: How accurately can
a state-of-the-art code classification method assess students’ performance on
a programming exercise? RQ2: How well does the code embedding from such a
model capture meaningful similarities among students submissions, and do these
reflect shared misconceptions?

###  4.1. Dataset and Rubric

Our data come from an entry-level (CS0) computer science class for non-majors
at a research university, spanning four consecutive semesters (Spring 2016
through Fall 2017). Students programmed in Snap, a block-based programming
environment, designed for novices (Garcia et al., 2015). For this experiment,
we chose to analyze one assignment from the course that required the use of
loops, variables and procedures to draw a spiral shape, which proved
particularly difficult for students (as it has a lowest average score among
all assignments). We collected $207$ submissions, which had each been graded
using a rubric with 6 pass/fail items:

  * •

Procedure with 1 Parameter: Create a procedure to draw the shape with one
parameter that controls its size.

  * •

Pen Down: Use the “pen down” block in the procedure to start drawing.

  * •

Variable Init: Initialize a variable and use it to control the length of each
side of the shape.

  * •

Repeat Rotations: Use a “repeat” block (i.e. a loop) to draw a spiral shape
with the given size.

  * •

Forward + Turn: Draw a square-like shape using the “forward” and “turn” blocks
inside a loop.

  * •

Variable Increment: Increment the side length variable after each iteration.

###  4.2. Creating and Validating Code2Vec Embeddings

Our goal is to use code2vec to create a meaningful embedding, which can be
used to detect misconceptions. For consistency, we trained the code2vec model
to predict whether a student got all rubric items correct (which 38% of
students did). For a given training set, this yielded a single embedding,
which we hypothesized would reflect learned code patterns indicating success
on each rubric item. However, this embedding would only be meaningful if the
model itself can accurately predict student success.

To evaluate the model’s performance, we compared code2vec to three baseline
models: 1) a naive majority class basline, 2) a support vector machine (SVM)
(with a linear kernel, which outperformed Gaussian and Polynomial kernels),
and 3) a fully connected neural network (NN). To convert student’s code into a
vector of numeric features to use in the baseline models, we applied term
frequency–inverse document frequency (TF-IDF) to each student’s code. This is
similar to the Bag of Words approach used in prior learning analytics work
(Azcona et al., 2019) for code feature extraction. When evaluating all models’
performance, we split the Snap dataset into an $80\%$ training dataset, and a
$20\%$ testing dataset. To ensure the robustness of our results in lieu of
cross-validation, we re-sampled and re-trained the model $50$ times and report
the average performance.

Hyperparameters: In training both neural network models, we set the maximum
training epochs as $10,000$, with the patience of early stopping set to $400$.
We used a manual grid-search to select the learning rate ($0.1$ to $10^{-6}$),
number of linear layer dimensions ($100$, $200$, $300$) and batch size ($32$,
$64$, $128$, full set), and found little difference across a hyper-parameters
range. We thus selected the following parameters for both neural network
models. The learning rate was set to $0.0002$, linear layer dimensions were
set to $100$, and the batch size was set to the full set. The weights were
learned during training using the Adam optimizer (Kingma and Ba, 2014) for all
these three models. On code2vec, we used $100$-dimensional vectors for both
nodes and paths. We applied the default values from the code2vec model, since
changing these numbers within a range did not meaningfully change the results.
We padded the number of paths to be the same length ($100$) over the student
code dataset.

###  4.3. Clustering Incorrect Submissions to Feed Misconception Detection

We randomly selected a single code2vec model from the 50 runs and extracted
its embeddings from the input of the attention layer, as shown in Fig. 1. When
detecting misconceptions, we applied t-SNE to visualize the entire dataset of
incorrect submissions (training and validation), since our intended use case
is post hoc analytics, not predicting the misconceptions of future students.
We used DBSCAN to cluster incorrect submissions for each rubric item
individually (leading to 6 sets of clusters). For DBSCAN, we set the minimum
number cluster points (minpts) at $3$, assuming that this is the smallest
number of submissions an instructor or researcher might be interested in
examining. We used the DMDBSCAN method (Elbatta and Ashour, 2013) to determine
an optimal $\epsilon$, and set $\epsilon=11$. For each cluster, we calculated
the average distance between each item in each cluster, and normalized this
number by the average distance of all points to the overall centroid. We
selected up to 4 of the densest clusters for each rubric item to inspect
(those with the smallest mean intra-cluster distance), which are presented in
Section 5.2.

##  5\. Results

Table 1. Grading accuracy, precision, recall, area under ROC curve (AUC), F-1 Score for code2vec. Metric | Majority | SVM | NN | code2vec
---|---|---|---|---
Accuracy | 63.95% | 69.67% | 71.71% | 75.66%
Precision | 0 | 61.68% | 62.74% | 67.06%
Recall | 0 | 42.21% | 58.30% | 72.66%
AUC | 0.5 | 0.650 | 0.689 | 0.814
F1 | 0 | 0.460 | 0.593 | 0.6895

###  5.1. Model Validation: Predicting Student Performance

Table 1 shows the mean performance of all models for predicting students’
performance on the task (all correct or not). The code2vec model outperforms
all baselines on all metrics. Specifically, code2vec model achieves 0.125
higher AUC, and 0.096 higher F1 score than the best among other baseline
models, which is a substantial improvement. These results address RQ1,
suggesting that code2vec can achieve improved assessment accuracy by
extracting more meaningful features from students’ code. With an accuracy of
75.7%, this semi-automated assessment certainly cannot replace manual grading,
but could reasonably assist instructors by providing a list of likely correct
submissions to be verified, or by providing formative feedback to students,
warning them before submitting a potentially erroneous solution. More
importantly, these results show that the structural information, encoded in
code2vec embedding, is a useful predictor of student performance, more than
the count information given by TF-IDF features used in the baselines. This
suggests that our use of the embedding to detect meaningful patterns among
student submissions is a reasonable approach.

###  5.2. Embedding Interpretation

Table 2. Top-4 clusters Embedding Distance (ED) and Tree Edit Distance (TED), and the Interpretations of the clusters Rubric | Name and Description | Size (# of students) | Outliers | TED | ED
---|---|---|---|---|---
R0 - Procedure with 1 Param. | Fixed Shape | 7 | 0 | 0.2912 | 0.1884
Large Move/Turn | 11 | 1 | 1.9551 | 0.1657
Not testing a custom block | 3 | 0 | 0.2868 | 0.0813
Rotations not from Input | 3 | 0 | 0.4666 | 0.0788
R1 - Initialize Variable | Large Move/Turn | 10 | 0 | 1.9599 | 0.1680
Medium Move/Turn | 4 | 0 | 0.5730 | 0.1254
Fail to initialize | 3 | 1 | 0.6041 | 0.0890
R2 - Move and Turn | Large Move/Turn | 6 | 1 | 2.0339 | 0.1377
Medium Move/Turn | 4 | 1 | 0.4207 | 0.1515
R3 - Repeat | Repeat sides not rotations | 6 | 0 | 0.4566 | 0.1357
Mixed incorrect repeat | 11 | 0 | 0.4719 | 0.2494
Mixed incorrect repeat | 4 | 0 | 0.9894 | 0.1342
Fixed shape | 4 | 1 | 0.0891 | 0.0428
R4 - Pen down | Mixed incorrect custom block | 5 | 0 | 0.5115 | 0.1436
Mixed incorrect custom block | 4 | 0 | 0.5449 | 0.1265
R5 - Increment | Large Move/turn | 9 | 0 | 1.9781 | 0.1680
Medium Move/turn | 5 | 1 | 0.5947 | 0.1481

Figure 2. Code Embedding visualized clusters from the Procedure with 1 Input
rubric item. We colored three clusters Rotations not from input (Brown), Fixed
Shape (Orange) and Move/Turn (Green) for discussion in Subsection 5.3.

Figure 3. Pseudocode examples from student code dataset for the three
clustered circled in Fig.3. Code related with misconceptions are highlighted
with specific colors.

We introduce the interpretations of embeddings to address RQ2 in this
subsection, and include a case study in the next subsection. Table 2 shows the
4 densest clusters discovered for each rubric item (or as many as were
discovered). Recall that the primary goal of our proposed method is to
discover meaningful clusters (groups of students) who are demonstrating a
similar misconception and would benefit from similar feedback. To verify this,
one author, who is an instructor for the course, inspected each cluster and
evaluated whether a shared misconception was present in the cluster, in which
all (or nearly all) students failed the rubric item due to the same
misconception. This process led to the discovery of 7 distinct misconceptions
(shown in Table 2), which involved viewing 63 distinct submissions (about half
of the incorrect submission). The author then created a short definition for
each misconception.

Of the 17 clusters identified, only 4 had no consistent pattern or
misconception (no label). This suggests that our approach frequently
identified meaningful groups of students. To validate the original
misconception labels, 2 other authors familiar with the class inspected the
clusters and marked each submission as matching or not matching the
misconception, resolving any disagreements. We report then number of
“outliers” in each cluster which did not have the misconception. Many clusters
had 0 outliers, and none had more than 1, further suggesting that clusters
have internal consistency. One misconception (Move/Turn) showed up across
almost every rubric item, often represented by similar or identical clusters
of students. In the future, this redundancy could be avoided by excluding
clusters that have high overlap with previously discovered clusters. To
illustrate the types of misconceptions discovered by our approach, we describe
3 of the misconceptions discovered for one rubric item in detail below.

###  5.3. Case Study: “Procedure with One Parameter” Rubric Item

The first rubric item (referred to as R0) requires students to create a
procedure with one parameter that holds the number of rotations of the spiral-
square shape. This rubric was originally designed to test students’ ability to
create procedures with parameters, which demonstrates an understanding of
abstraction. While the rubric item was designed to assess a single student
skill, we found that students failed the item for a wide variety of reasons,
as illustrated by 3 distinct misconceptions:

The green cluster in Figure 3 contains 11 students who shared a misconception
that iteration should be accomplished by duplicating code multiple times,
(e.g. 5 pairs of “move” and “turn” blocks), rather than correctly repeating
iterations with a loop. This misconception has little to do with R0 or with
procedures (some students used a procedure; others did not), but it caused
students to fail R0, since they could not correctly use the parameter without
a loop. Unlike the other R0 clusters, these students needed basic feedback on
a prerequisite programming concept (iteration), and would likely not benefit
from feedback on procedures or parameters. These students all failed other
rubric items as well, and this misconception shows up consistently across
rubric items.

The orange cluster in Figure 3 consists of 8 students who created a loop that
repeats a fixed number of times, rather than using the procedure’s parameter
to determines the number of rotations. This suggests a misconception about
using loops with parameters. Unlike the previous cluster, students in this
cluster knew how to create a loop, but they likely had a misconception that
loops always iterated a fixed number of times, which was reflected in their
inability to use a parameter or even a variable in the “repeat” block. Despite
this similarity, there was also variety within the cluster: two of these
students used a procedure without a parameter, while six did not create a
procedure, and some used variables while others did not. Despite these
syntactic differences, these submissions were positioned very close together
in the embedding.

The brown cluster in Figure 3 consists of three students, where all of them
used a local variable to determine the number of rotations, instead of the
procedure’s parameter. In particular, two students created a procedure without
parameters, then used an ask block to ask the user for an input and finally
store it in a different created variable: “Rotations”. The third student did
not create a procedure, and created a variable: “Rotations” and initialized it
with a static value. Unlike the previous clusters, all students demonstrated
an understanding that the size of the shape should be dynamic, using a
variable in the repeat block. However, they shared a misconception about how a
procedure parameter can be used to vary this value. This could also be
explained by a misunderstanding about the assignment requiring such a
parameter, but in either case, students would benefit from targeted feedback
on this misconception.

###  5.4. Are Clusters Distinct and Non-obvious?

Our proposed method is only useful if it detects clusters of student code that
could not easily be otherwise identified. For example, if the clusters simply
correspond to getting specific items in the rubric incorrect, there would be
no need for a new approach to discover them. However, we found that the
individual rubric scores varied widely within each cluster, without consistent
patterns of which rubric items were gotten correct or incorrect (beyond the
initial rubric item used to discover the cluster, which all students got
incorrect).

Another possibility is that the clusters simply have similar ASTs, allowing
existing code clustering methods to detect them. However, investigation of the
code snapshots within each cluster revealed wide variety in the size and
syntactic structure. To verify this, we calculated the average tree edit
distance between each item in each cluster, and normalized this number by the
average distance to the overall centroid. We compared this normalized cluster
tree edit distance (TED) with the normalized embedding distance (ED), as shown
in Table 2. We found the embedding distance is always much smaller than the
tree edit distance, showing that the clustered submissions were relatively
much closer together in the embedded space (compared to non-clustered
submission), than in TED space, suggesting they would not be easily detected
by traditional clustering methods. This shows the the embedding captures some
aspects of code similarity which not apparent by simply comparing ASTs.

##  6\. Discussion

Implications for Research and Teaching: We envision a number of potential
applications of our approach to help researchers and instructors to address
students’ misconceptions. Feedback propagation: We found that students in the
clusters we discovered would have benefited from targeted feedback that
addressed their misconception. One application of our approach is in feedback
propagation (Head et al., 2017), where an instructor can write a single piece
of feedback and send it to all students who might benefit. Moreover, our
clusters would not have been discovered through traditional code clustering
methods used in prior work (e.g. canonicalization (Glassman et al., 2015)).
Semi-automated feedback: Many of the misconceptions we discovered would be
best addressed with formative feedback, as the student works. Since the
patterns we discovered were relatively straightforward, one could imagine
building a system to detect them automatically and offer appropriate immediate
feedback early in a students’ work. In our investigation, we found that our
clusters were not exhaustive, and did not include all students who shared the
common misconception, just a representative subset. However, prior work
suggests that, once a misconception is identified, models can be trained to
accurately identify it automatically (Michalenko et al., 2017). Rubric
refinement: We found that a single rubric item can easily correspond to
numerous, distinct challenges faced by students, as described in Section 5.3.
Instructors and researchers may want to assess student knowledge in a more
granular way, and our approach could help develop rubrics that capture the
full range of students’ ability and knowledge. For example, it might be best
to split the rubric item R0 into multiple items, or convert it from a binary
pass/fail item to having scale values representing the various degrees of
success.

Domain-Specific Implications for Computing Education: Another application of
misconception discovery is to inform our understanding of a learning domain,
and here we reflect on the implications of our findings for computing
education. In this paper, we focused on R0, which assessed students’ ability
to use a procedure parameter to vary the size of the shape they were drawing
(determined by the number of iterations in a loop). While this rubric item was
designed to assess a single concept (use of a parameter), our method
discovered three clusters representing distinct barriers that students faced,
requiring different remediation. The first cluster included students who had
not figured out how to use a loop to draw the shape, suggesting the need for
basic help on programming concepts needed in the assignment. The second
cluster included students who were able to use a loop to draw the shape, but
they did not understand that the size of the shape should vary; they used a
static value instead. These students may need help understanding the
assignment requirements, or which property of the shape should be
parameterized. The third cluster of students did understand that the size of
the shape should vary, but used a variable instead of the procedure parameter
for this, suggesting their need to understand the use of parameters.

These results suggest implications for how to teach the lesson preceding this
assignment, and how to teach procedure parameters in general. For our
classroom, the instructor may want to do a more thorough review of loops and
variables before the assignment (e.g. to help students in the first/green
cluster). In general, our results suggest that students may struggle to use
abstraction in the absence of a clear set of steps for creating a procedure
with parameters. The instructor may want to teach students steps that address
each of the barriers we identified, e.g.: 1) create a non-parameterized
version of the procedure, which is the same every time, and make sure it
works; 2) identify what aspect(s) of the procedure should be able to vary and
create corresponding parameter(s); 3) replace the corresponding literal values
in your code with the appropriate parameters. This aligns with a similar
series of steps presented by the popular textbook on “How to Design Programs”
to teach abstraction (Felleisen et al., 2018).

Limitations: This study is exploratory and has important limitations. First,
we focused on one assignment from one course. This allowed us to discuss the
misconceptions we discovered in depth, but as a result, it is not clear how
well our results will generalize to other assignments. Second, our approach –
and our evaluation – relied on the interpretations of experts to describe and
label misconceptions, making the process semi-automatic. However, we argue
this interpretation is a necessary part of making use of any misconceptions to
verify their meaningfulness, and in our evaluation we used multiple raters to
verify cluster meaning. Third, our approach yield some clusters that have no
clear interpretation, and some duplicates, suggesting the need for future work
to refine the process. Lastly, the discovered clusters are not exhaustive,
meaning not all students who make a given misconception show up in the
cluster. However, as discussed in Section 6, the clusters can still be useful
to researchers and instructors, prompting changes to course structure that can
benefit students not captured by the clusters.

##  7\. Conclusion

In this paper, we presented a method for discovering student misconceptions
semi-automatically using code assessment. We found that the code2vec model
achieves a better semi-automated assessment performance than baseline models,
showing that useful code structural information is learned in the model for
the embeddings. We then examined if the embeddings could be used to discover
misconceptions, and found that the embeddings generated clusters corresponding
to meaningful and distinct misconceptions. From a case study on three
clusters, we found that they are novel, consistent, and cannot be discovered
by traditional code clustering methods, e.g. using tree edit distance. These
results suggest that deep learning approaches have exciting potential to not
only assess code, but help in the identification of learners’ misconceptions.

###### Acknowledgements.

This research was supported in part by the Amazon Web Services (AWS) Cloud
Credits for Research program.

## References

  * (1)
  * Allamanis et al. (2016) Miltiadis Allamanis, Hao Peng, and Charles Sutton. 2016\.  A convolutional attention network for extreme summarization of source code. In _ICML’16_.
  * Alon et al. (2019) Uri Alon, Meital Zilberstein, Omer Levy, and Eran Yahav. 2019.  code2vec: Learning distributed representations of code.  _POPL’19_ (2019).
  * Azcona et al. (2019) David Azcona, Piyush Arora, I-Han Hsiao, and Alan Smeaton. 2019\.  user2code2vec: Embeddings for profiling students based on distributional representations of source code. In _LAK’19_.
  * Baffles (1994) Paul T Baffles. 1994\.  _Learning to Model Students: Using Theory Refinement to Detect Misconceptions_.  Technical Report. 1–34 pages.
  * Caceffo et al. (2016) Ricardo Caceffo, Steve Wolfman, Kellogg S Booth, and Rodolfo Azevedo. 2016.  Developing a computer science concept inventory for introductory programming. In _SIGCSE’16_.
  * Davies et al. (2015) Randall Davies, Rob Nyland, John Chapman, and Gove Allen. 2015\.  Using Transaction-Level Data to Diagnose Knowledge Gaps and Misconceptions. In _LAK’15_ (Poughkeepsie, New York).  https://doi.org/10.1145/2723576.2723620
  * Diana et al. (2018) Nicholas Diana, Michael Eagle, John Stamper, Shuchi Grover, Marie Bienkowski, and Satabdi Basu. 2018\.  Data-driven generation of rubric criteria from an educational programming environment. In _LAK’18_. 16–20.
  * Dimopoulos et al. (2013) Ioannis Dimopoulos, Ourania Petropoulou, and Symeon Retalis. 2013.  Assessing students’ performance using the learning analytics enriched rubrics. In _LAK’13_. 195–199.
  * Edwards and Murali (2017) Stephen H Edwards and Krishnan Panamalai Murali. 2017\.  CodeWorkout: short programming exercises with built-in data collection. In _Proceedings of the 2017 ACM Conference on Innovation and Technology in Computer Science Education_. 188–193.
  * Elbatta and Ashour (2013) Mohammed TH Elbatta and Wesam M Ashour. 2013.  A dynamic method for discovering density varied clusters.  _International Journal of Signal Processing, Image Processing and Pattern Recognition_ 6, 1 (2013).
  * Elmadani et al. (2012) Myse Elmadani, Moffat Mathews, and Antonija Mitrovic. 2012\.  Data-driven misconception discovery in constraint-based intelligent tutoring systems. In _Proceedings of the 20th International Conference on Computers in Education._ http://ir.canterbury.ac.nz/handle/10092/7399
  * Ester et al. (1996) Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. 1996.  A density-based algorithm for discovering clusters in large spatial databases with noise. AAAI Press, 226–231.
  * Felleisen et al. (2018) Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, and Shriram Krishnamurthi. 2018\.  _How to design programs: an introduction to programming and computing_.  MIT Press.
  * Garcia et al. (2015) Dan Garcia, Brian Harvey, and Tiffany Barnes. 2015.  The Beauty and Joy of Computing.  _ACM Inroads_ 6, 4 (2015), 71–79.
  * Glassman et al. (2015) Elena L Glassman, Jeremy Scott, Rishabh Singh, Philip J Guo, and Robert C Miller. 2015.  OverCode: Visualizing variation in student solutions to programming problems at scale.  _ACM Transactions on Computer-Human Interaction (TOCHI)_ 22, 2 (2015), 1–35.
  * Guzmán et al. (2010) Eduardo Guzmán, Ricardo Conejo, and Jaime Gálvez. 2010.  A data-driven technique for misconception elicitation.  _UMAP’10_ 6075 LNCS (2010), 243–254.
  * Head et al. (2017) Andrew Head, Elena Glassman, Gustavo Soares, Ryo Suzuki, Lucas Figueredo, Loris D’Antoni, and Björn Hartmann. 2017.  Writing Reusable Code Feedback at Scale with Mixed-Initiative Program Synthesis. In _Proceedings of the ACM Conference on Learning @ Scale_. 89–98.  https://doi.org/10.1145/3051457.3051467
  * Kaczmarczyk et al. (2010) Lisa C Kaczmarczyk, Elizabeth R Petrick, J Philip East, and Geoffrey L Herman. 2010.  Identifying student misconceptions of programming. In _SIGCSE’10_.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ (2014).
  * Kurvinen et al. (2016) Einari Kurvinen, Niko Hellgren, Erkki Kaila, Mikko-Jussi Laakso, and Tapio Salakoski. 2016\.  Programming Misconceptions in an Introductory Level Programming Course Exam. In _ITiCSE’16_. 308–313.  https://doi.org/10.1145/2899415.2899447
  * Kuzi et al. (2019) Saar Kuzi, William Cope, Duncan Ferguson, Chase Geigle, and ChengXiang Zhai. 2019.  Automatic Assessment of Complex Assignments using Topic Models. In _Proceedings of the Sixth (2019) ACM Conference on Learning@ Scale_. 1–10.
  * Liu (2016) M. Hui. Liu. 2016\.  Blending a class video blog to optimize student learning outcomes in higher education.  _The Internet and Higher Education_ 30 (2016), 44 – 53.  https://doi.org/10.1016/j.iheduc.2016.03.001
  * Liu et al. (2016) Ran Liu, Rony Patel, and Kenneth R. Koedinger. 2016\.  Modeling common misconceptions in learning process data.  _LAK’16_ (2016).  https://doi.org/10.1145/2883851.2883967
  * Maaten and Hinton (2008) Laurens van der Maaten and Geoffrey Hinton. 2008.  Visualizing data using t-SNE.  _Journal of machine learning research_ 9, Nov (2008), 2579–2605.
  * Mao et al. (2019) Ye Mao, Rui Zhi, Farzaneh Khoshnevisan, Thomas W Price, Tiffany Barnes, and Min Chi. 2019\.  One Minute Is Enough: Early Prediction of Student Success and Event-Level Difficulty During a Novice Programming Task.  _International Educational Data Mining Society_ (2019).
  * Michalenko et al. (2017) Joshua J. Michalenko, Andrew S. Lan, Andrew E. Waters, Phillip J. Grimaldi, and Richard G. Baraniuk. 2017.  Data-mining textual responses to uncover misconception patterns.  _Proceedings of the 10th International Conference on Educational Data Mining, EDM 2017_ (2017), 208–213.  arXiv:1703.08544
  * Mikolov et al. (2013) Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013.  Distributed representations of words and phrases and their compositionality. In _Advances in neural information processing systems_. 3111–3119.
  * Nathan and Petrosino (2003) Mitchell J. Nathan and Anthony Petrosino. 2003.  Expert Blind Spot Among Preservice Teachers.  _American Educational Research Journal_ 40, 4 (2003), 905–928.  https://doi.org/10.3102/00028312040004905 arXiv:https://doi.org/10.3102/00028312040004905
  * Paul and Vahrenhold (2013) Wolfgang Paul and Jan Vahrenhold. 2013.  Hunting high and low: Instruments to detect misconceptions related to algorithms and data structures.  _SIGCSE’13_ (2013).
  * Piech et al. (2015) Chris Piech, Jonathan Huang, Andy Nguyen, Mike Phulsuksombati, Mehran Sahami, and Leonidas Guibas. 2015\.  Learning Program Embeddings to Propagate Feedback on Student Code. In _International Conference on Machine Learning_. 1093–1102.
  * Segedy et al. (2011) James René Segedy, John S Kinnebrew, and Gautam Biswas. 2011\.  Modeling learner’s cognitive and metacognitive strategies in an open-ended learning environment. In _2011 AAAI Fall Symposium Series_.
  * Sirkiä and Sorva (2012) Teemu Sirkiä and Juha Sorva. 2012.  Exploring programming misconceptions: an analysis of student mistakes in visual program simulation exercises. In _Proceedings of the 12th Koli Calling International Conference on Computing Education Research_. 19–28.
  * Sorva (2013) Juha Sorva. 2013\.  Notional Machines and Introductory Programming Education.  _ACM Transactions on Computing Education_ 13 (06 2013), 8:1–8:31.  https://doi.org/10.1145/2483710.2483713
  * Swidan et al. (2018) Alaaeddin Swidan, Felienne Hermans, and Marileen Smit. 2018\.  Programming misconceptions for school students. In _ICER’18_. 151–159.
  * Zhi et al. (2018) Rui Zhi, Thomas W Price, Nicholas Lytle, Yihuan Dong, and Tiffany Barnes. 2018.  Reducing the state space of programming problems through data-driven feature detection. In _Educational Data Mining in Computer Science Education (CSEDM) Workshop@ EDM_.