text:
# CF877E Danil and a Part-time Job

• 46通过
• 102提交
• 题目来源
• 评测方式 RemoteJudge
• 标签
• 难度 省选/NOI-
• 时空限制 2000ms / 256MB
• 提示：收藏到任务计划后，可在首页查看。

## 题意翻译

题目大意:

有一棵 $n$ 个点的树，根结点为 $1$ 号点，每个点的权值都是 $1$ 或 $0$

共有 $m$ 次操作，操作分为两种

$get$ 询问一个点 $x$ 的子树里有多少个 $1$

$pow$ 将一个点 $x$ 的子树中所有节点取反

对于每个 $get$ 给出答案

输入格式：

第一行一个整数 $n$

第二行共 $n-1$ 个整数，第 $i$ 个数 $x_i$ 表示 $x_i$ 是 $i+1$ 的父亲，

第三行给出每个点的初始权值

第四行一个整数 $m$

接下来 $m$ 行为操作类型和位置

## 题目描述

Danil decided to earn some money, so he had found a part-time job. The interview have went well, so now he is a light switcher.

Danil works in a rooted tree (undirected connected acyclic graph) with $n$ vertices, vertex $1$ is the root of the tree. There is a room in each vertex, light can be switched on or off in each room. Danil's duties include switching light in all rooms of the subtree of the vertex. It means that if light is switched on in some room of the subtree, he should switch it off. Otherwise, he should switch it on.

Unfortunately (or fortunately), Danil is very lazy. He knows that his boss is not going to personally check the work. Instead, he will send Danil tasks using Workforces personal messages.

There are two types of tasks:

1. pow v describes a task to switch lights in the subtree of vertex $v$ .
2. get v describes a task to count the number of rooms in the subtree of $v$ , in which the light is turned on. Danil should send the answer to his boss using Workforces messages.

A subtree of vertex $v$ is a set of vertices for which the shortest path from them to the root passes through $v$ . In particular, the vertex $v$ is in the subtree of $v$ .

Danil is not going to perform his duties. He asks you to write a program, which answers the boss instead of him.

## 输入输出格式

输入格式：

The first line contains a single integer $n$ ( $1<=n<=200000$ ) — the number of vertices in the tree.

The second line contains $n-1$ space-separated integers $p_{2},p_{3},...,p_{n}$ ( $1<=p_{i}<i$ ), where $p_{i}$ is the ancestor of vertex $i$ .

The third line contains $n$ space-separated integers $t_{1},t_{2},...,t_{n}$ ( $0<=t_{i}<=1$ ), where $t_{i}$ is $1$ , if the light is turned on in vertex $i$ and $0$ otherwise.

The fourth line contains a single integer $q$ ( $1<=q<=200000$ ) — the number of tasks.

The next $q$ lines are get v or pow v ( $1<=v<=n$ ) — the tasks described above.

输出格式：

For each task get v print the number of rooms in the subtree of $v$ , in which the light is turned on.

## 输入输出样例

输入样例#1： 复制
4
1 1 1
1 0 0 1
9
get 1
get 2
get 3
get 4
pow 1
get 1
get 2
get 3
get 4

输出样例#1： 复制
2
0
0
1
2
1
1
0

## 说明

The tree before the task pow 1.The tree after the task pow 1.

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。


text:
## Departmental PhD Thesis Exam – Fabian Parsch

Everyone is welcome to attend.  Refreshments will be served in the Math Lounge before the exam.

Tuesday, June 18, 2019
11:10 a.m.
BA6183

PhD Candidate:  Fabian Parsch
Supervisor:   Alex Nabutovsky
Thesis title:  Geodesic Nets with Few Boundary Points

***

Geodesic nets on Riemannian manifolds form a natural class of stationary objects generalizing geodesics. Yet almost nothing is known about their classification or general properties even when the ambient Riemannian manifold is the Euclidean plane or the round 2-sphere.
We survey some results and open questions (old and new) about geodesic nets on Riemannian manifolds. A particular focus will be put on the question if the number of inner vertices (balanced vertices) in a geodesic net can be bounded by the number of boundary points (unbalanced vertices) or the total imbalance.
We prove that a geodesic net with three unbalanced vertices on a non-positively curved plane has at most one balanced vertex. We do not assume any a priori bound for the degree of unbalanced vertices. The result seems to be new even in the Euclidean case.
We demonstrate by examples that the result is not true for metrics of positive curvature on the plane, and that there are no immediate generalizations of this result for geodesic nets with four unbalanced vertices which can have a significantly more complicated structure. In particular, an example of a geodesic net with four unbalanced vertices and sixteen balanced vertices that is not a union of simpler geodesic nets is constructed. The previously known irreducible geodesic nets with four unbalanced vertices have at most two balanced vertices.
We provide a partial answer for a related question, namely a description of a new infinite family of geodesic nets on the Euclidean plane with 14 unbalanced vertices and arbitrarily many balanced vertices of degree three or more.

A copy of the thesis can be found here: parsch_thesis_2019-04-09

## Departmental PhD Thesis Exam – Zhifei Zhu

Everyone is welcome to attend.  Refreshments will be served in the Math Lounge before the exam.

Tuesday, June 18, 2019
2:10 p.m.
BA6183

PhD Candidate:  Zhifei Zhu
Supervisor:   Regina Rotman
Thesis title: Geometric inequalities on Riemannian manifolds

***

In this thesis, we will show three results which partially answer several questions in the field of quantitative geometry. We first show that there exists Riemannian metric on a 3-disk so that the diameter, volume and surface area of the boundary is bounded, but during any contraction of the boundary of the disk, there exists a surface with arbitrarily large surface area. This result answers a question of P. Papasoglu.

The second result we will prove is that on any closed 4-dimensional simply-connected Riemannian manifolds with diameter <=D, volume > v > 0 and Ricci curvature |Ric| < 3, the length of a shortest closed geodesic can be bounded by some function f(v,D) which only depends on the volume and diameter of the manifold. This result partially answers a question of M. Gromov.

As an extension of our second result, we show that on 4-dimensional Riemannian manifolds satisfying the above conditions, the first homological filling function HF_1(l) <=f_1 (v,D)l +f_2 (v,D), for some functions f_1 and f_2 which only depends on v and D. And in particular, the area of a smallest minimal surface on the manifold can be bounded by some function which only depends on v and D.

A copy of the thesis can be found here: ut-thesis

## Departmental PhD Thesis Exam – Leonid Monin

Everyone is welcome to attend.  Refreshments will be served in the Math Lounge before the exam.

Friday, April 26, 2019
11:10 a.m.
BA6183

PhD Candidate:  Leonid Monin
Thesis title: Newton Polyhedra, Overdetermined system of equations, and Resultants

***

In the first part of this thesis we develop Newton polyhedra theory for overdetermined systems of equations. Let A_1…A_k be finite sets in Z^n  and let be an algebraic subvariety of (C^*)^n  defined by a system of  Laurent polynomials with supports in A_1… A_k.  Assuming that  Laurent polynomials are sufficiently generic, the Newton polyhedron theory computes discrete invariants of Y in terms of their Newton polyhedra. It may appear that the generic system with fixed supports  is inconsistent. In this case one is interested in the generic consistent system. We extend Newton polyhedra theory to this case and compute discrete invariants generic non-empty zero sets. Unlike the classical situation, not only the Newton polyhedra of Laurent polynomials, but also their supports themselves appear in the answers.

We proceed then to the study of overdetermined collections of linear series on algebraic varieties other than algebraic torus. That is let E_1…E_k be a finite dimensional subspace of the space of  regular sections of line bundles on an irreducible algebraic variety X, so that the system

s_1 = … = s_k = 0,

where s_i is a generic  element of E_i does not have any roots on X. In this case we investigate the consistency variety  (the closure of the set of all systems which have at least one common root) and study general properties of zero sets Z of a generic consistent system. Then, in the case of equivariant linear series on spherical homogeneous spaces we provide a strategy for computing discrete invariants of such generic non-empty set Z.

The second part of this thesis is devoted to the study of Delta-resultants of (n+1)-tuple of Laurent polynomials with generic enough Newton polyhedra.  We provide an algorithm for computing Delta-resultant assuming that an n-tuple f_2, …, f_{n+1} is developed. We provide a relation between the product of f_1 over roots of  f_2 = … = f_{n+1} = 0 in (C^*)^n and the product of f_2 over roots of f_1=f_3 = … = f_{n+1} = 0 in (C^*)^n assuming that the n-tuple (f_1f_2, f_3…f_{n+1} is developed. If all n-tuples contained  in (f_1…f_{n+1}) are developed we provide a signed version of Poisson formula for Delta-resultant. Interestingly, the sign of the sparse resultant is nontrivial and is defined through Parshin symbols. Our proofs are based on a topological version of the Parshin reciprocity laws.
A copy of the thesis can be found here:  ut-thesis monin

## Departmental PhD Thesis Exam – Francisco Guevara Parra

Everyone is welcome to attend.  Refreshments will be served in the Math Lounge before the exam.

Friday, March 15, 2019
1:30 p.m.
Fields Institute, room 210

PhD Candidate:  Francisco Guevara Parra
Supervisor:   Stevo Todorcevic
Thesis title:  Analytic spaces and their Tukey types

***

In this Thesis we study topologies on countable sets from the perspective of Tukey reductions of their neighbourhood filters. It turns out that is closely related to the already established theory of definable (and in particular analytic) topologies on countable sets. The connection is in fact natural as the neighbourhood filters of points in such spaces are typical examples of directed sets for which Tukey theory was introduced some eighty years ago. What is interesting here is that the abstract Tukey reduction of a neighbourhood filter $\mathcal{F}_{x}$ of a point to standard directed sets like $\mathbb{N}^\mathbb{N}$ or $\ell_1$ imposes that $\mathcal{F}_{x}$ must be analytic. We develop a theory that examines the Tukey types of analytic topologies and compare it by the theory of sequential convergence in arbitrary countable topological spaces either using forcing extensions or axioms such as, for example, the Open Graph Axiom. It turns out that in certain classes of countable analytic groups we can classify all possible Tukey types of the corresponding neighbourhood filters of identities. For example we show that if $G$ is a countable analytic $k$-group then $1=\{0\},$ $\mathbb{N}$ and $\mathbb{N}^\mathbb{N}$ are the only possible Tukey types of the neighbourhood filter $\mathcal{F}_{e}^{G}$. This will give us also new metrization criteria for such groups. We also show that the study of definable topologies on countable index sets has natural analogues in the study of arbitrary topologies on countable sets in certain forcing extensions.

A copy of the thesis can be found here: Francisco_PhD_Thesis

## Departmental PhD Thesis Exam – Duncan Dauvergne

Everyone is welcome to attend.  Refreshments will be served in the Math Lounge before the exam.

Monday, March 25, 2019
10:10 a.m.
BA6183

PhD Candidate:  Duncan Dauvergne
Supervisor:   Balint Virag
Thesis title:  Random sorting networks, the directed landscape, and random polynomials

***

The first part of this thesis is on random sorting networks. A sorting network is a shortest path from $12 \cdots n$ to $n \cdots 21$ in the Cayley graph of the symmetric group $S_n$ generated by adjacent transpositions. We prove that in a uniform random $n$-element sorting network $\sigma^n$, all particle trajectories are close to sine curves with high probability. We also find the weak limit of the time-$t$ permutation matrix measures of $\sigma^n$. As a corollary, we show that if $S_n$ is embedded into $\mathbb{R}^n$ via the map $\tau \mapsto (\tau(1), \tau(2), \dots \tau(n))$, then with high probability, the path $\sigma^n$ is close to a great circle on a particular $(n-2)$-dimensional sphere. These results prove conjectures of Angel, Holroyd, Romik, and Vir\’ag. To prove these results, we find the local limit of random sorting networks and prove that the local speed distribution is the arcsine distribution on $[-\pi, \pi]$.

The second part of this thesis is on last passage percolation. The conjectured limit of last passage percolation is a scale-invariant, independent, stationary increment process with respect to metric composition. We prove this for Brownian last passage percolation. We construct the Airy sheet and characterize it in terms of the Airy line ensemble. We also show that the last passage geodesics converge to random functions with H\”older-$2/3^-$ continuous paths. To prove these results, we develop a new probabilistic framework for understanding the Airy line ensemble.

The third part of this thesis is on random sums of orthonormal polynomials. Let $G_n = \sum_{i=0}^n \xi_i p_i$, where the $\xi_i$ are i.i.d. non-degenerate complex random variables, and $\{p_i\}$ is a sequence of orthonormal polynomials with respect to a regular measure $\tau$ supported on a compact set $K$. We show that the zero measure of $G_n$ converges weakly almost surely to the equilibrium measure of $K$ if and only if $\mathbb{E}\log(1 + |\xi_0|) < \infty$. We also show that the zero measure of $G_n$ converges weakly in probability to the equilibrium measure of $K$ if and only if $\mathbb{P}(|\xi_0| > e^n) = o(n^{-1})$. Our methods also work for more general sequences of asymptotically minimal polynomials in $L^p(\tau)$, where $p \in (0, \infty]$.

A copy of the thesis can be found here: MainThesisPhD

## 2018 Malcolm Slingsby Robertson Prize winner and doctoral awards competition

The Department is happy to announce that the 2018 winner of the Malcolm Slingsby Robertson Prize in Mathematics for “a graduating PhD student who has demonstrated excellence in research” is:

• Alexander (Sacha) Mangerel

The Awards subcommittee of the Graduate Committee reviewed the theses and appraisal reports of several excellent graduating students for this prize.

Sacha wrote his thesis titled “Topics in Multiplicative and Probabilistic Number Theory under the supervision of John Friedlander.  One of his papers, joint with O. Klurman, of close to fifty pages, has been accepted for
publication in Mathematische Annalen.
He took on a Postdoctoral position at the
Centre de Recherches Mathématiques, Université de Montréal.

The prize carries a $500 monetary award. We congratulate Sacha for his excellent work and wish him great success! Malcolm Slingsby Robertson Prize winner 2018 Sacha is also the department’s sole nomination for the CMS Doctoral Prize. Our sole nomination for the CAIMS Cecil Graham Doctoral Dissertation Award (Applied Math) is Shuangjian Zhang, student of Robert McCann. Shuangjian is presently a postdoc at ENSAE ParisTech. We hope the nominations are successful. ## UTGSU accepting applications for the 2018 Conference Bursary (Fall Cycle) The UTGSU Conference Bursary was created in 2016 to financially assist UTGSU Members attending and/or presenting at academic conferences. The amount of a single bursary is$250, regardless of conference location or estimated expenses. A total of 120 bursaries are distributed each year, corresponding to 40 bursaries per each of the UTGSU’s three (3) Conference Bursary Cycles: Fall Cycle, Spring Cycle, and Summer Cycle.

Applications to the 2018 UTGSU Conference Bursary (Fall Cycle) will open on November 1, 2018 and will remain open until 11:59 PM on November 15, 2018.  This cycle is for conferences with start dates on or between December 1, 2018 and March 31, 2019.

Please note that you must be a UTGSU Member at the time of application for your application to be deemed eligible. Applications will only be accepted for conferences yet to be attended, not for conferences already attended. Additionally, applicants may only submit one application per Conference Cycle.

For more information and to access the Conference Bursary Application and Instructions please visit: https://www.utgsu.ca/funding/conference-bursary/ Contact Information and Accessibility If you require accessibility accommodations or have any questions related to the UTGSU Conference Bursary, please email the UTGSU Finance Commissioner at finance@utgsu.ca.

## Drop courses deadline – October 29, 2018

Drop courses absolute deadline: Monday, October 29, 2018

Students dropping courses on ACORN must also fill out a drop courses
form and submit to the Graduate Office.

Forms are also available on the counter in the math mailroom (BA 6290A).

## Departmental PhD Thesis Exam – Chia-Cheng Liu

Everyone is welcome to attend.  Refreshments will be served in the Math Lounge before the exam.

Wednesday, December 5, 2018
11:10 a.m.
BA1170

PhD Candidate:  Chia-Cheng Liu
Co-Supervisors:   Joel Kamnitzer/Alexander Braverman
Thesis title:  Semi-innite Cohomology, Quantum Group Cohomology, and the Kazhdan-Lusztig
Equivalence

The Kazhdan-Lusztig tensor equivalence is a monoidal functor which sends modules over ane
Lie algebras at a negative level to modules over quantum groups at a root of unity. A positive
level Kazhdan-Lusztig functor is dened using Arkhipov-Gaitsgory’s duality between ane Lie
algebras of positive and negative levels. We prove that the semi-innite cohomology functor
for positive level modules factors through the positive level Kazhdan-Lusztig functor and the
quantum group cohomology functor with respect to the positive part of Lusztig’s quantum
group. This is the main result of the thesis.

Monoidal structure of a category can be interpreted as factorization data on the associated
global category. We describe a conjectural reformulation of the Kazhdan-Lusztig tensor equivalence
in factorization terms. In this reformulation, the semi-innite cohomology functor at
positive level is naturally factorizable, and it is conjectured that the factorizable semi-innite
cohomology functor is essentially the positive level Kazhdan-Lusztig tensor functor modulo the
Riemann-Hilbert correspondence. Our main result provides an important technical tool in a
proposed approach to a proof of this conjecture.

A copy of the thesis can be found here: thesis_chiachengliu-1

format: plain


text:
Global Weak Solutions to the Navier-Stokes Equations for a 1D Viscous Polytropic Ideal Gas

S. Jiang and P. Zhang

Abstract: We prove the existence of global weak solutions to the Navier-Stokes equations for a one-dimensional viscous polytropic ideal gas. We require only that the initial density is in $L^\infty\cap L^2_{loc}$ with positive infimum, the initial velocity is in $L^2$ and the initial temperature is in a larger space than $L^2$ with positive infimum. The initial density and the initial velocity may have differing constant states at $x=\pm\infty$. In particular, piesewise constant data with arbitrary large jump discontinuities are included. Our results show that neither vacuum states nor concentration states can form and the temperature remains positive in finite time.

Paper:
Available as PostScript.
Author(s):
S. Jiang, <jiang@mail.iapcm.ac.cn>
P. Zhang, <zp@math03.math.ac.cn>
Publishing information:


text:
×

# Divisibility example.

If $$d|n$$ then prove that $${ 2 }^{ d }-1|{ 2 }^{ n }-1$$.

This is my solution

If $$d|n$$ then $$n=dk$$ for some $$k$$.Then we have to prove $${ 2 }^{ d }-1|{ 2 }^{ dn }-1$$ or $${ 2 }^{ d }-1|{ ({ 2 }^{ d }) }^{ k }-1$$.Now let $$x={ 2 }^{ d }$$ therefore we have to prove $$x-1|{ x }^{ k }-1$$ which is true by Remainder theorem.

Note by Shivamani Patil
1 year, 10 months ago

## Comments

Sort by:

Top Newest

NICE but too EASY. · 1 year, 10 months ago

Log in to reply

Math is neither easy nor difficult for her lover.@Krishna Ar · 1 year, 10 months ago

Log in to reply

haha · 1 year, 10 months ago

Log in to reply

Your proof is awesome. · 1 year, 10 months ago

Log in to reply

Thanx.@Adarsh Kumar · 1 year, 10 months ago

Log in to reply

nice.... · 1 year, 10 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...


text:
lilypond-user
[Top][All Lists]

## Re: Auto-beaming in asymmetrical time signatures

 From: Hans Aberg Subject: Re: Auto-beaming in asymmetrical time signatures Date: Sun, 7 Aug 2005 14:28:11 +0200

On 7 Aug 2005, at 04:28, Graham Percival wrote:

How do I auto-beam in asymmetrical times signatures? For example, 7/16 may decompose as (2+2+3)/16, (4+3)/16, (3+2+2)/16.

You look at doc section 6.4.4 Automatic beams

You could also look at the "tips and tricks" documents (beam-auto- *.ly), or
search examples in LSR.

Thank you for the reply. The rule seems to only work when decomposing the time signature in two parts. For example 7 = 4 + 3 works fine using
\time 7/16
#(override-auto-beam-setting '(end * * 7 16) 4 16)
But what do I write if I want to use 7 = 2 + 2 + 3 (or 13 = 4 + 4 + 2 + 3)?

Hans Aberg


text:
# Worksheet on Time and Work

In worksheet on time and work the questions will be mainly given to calculate the time required to complete the piece of work, to calculate the work done in a given period of time and also the questions will be from pipes and cistern.

1. A can do a piece of work in 24 days while B can do it in 30 days. In how many days can they complete it, if they work together?

2. A can do a piece of work in 15 hours while B can do it in 12 hours. How long will both take to do it, working together?

3. A and B, working together can finish a piece of work in 6 days, while A alone can do it in 9 days. How much time will B alone take to finish it?

4. Two motor mechanics, Ron and Sam, working together can overhaul a scooter in 6 hours. Ron alone can do the job in 15 hours. In how many hours, can Sam alone do it?

5. A, B and C can do a piece of work in 8 days, 12 days and 15 days respectively. How long will they take to finish it if they work together?

6. A can do a piece of work in 6 hours while B alone can do it in 16 hours. If A, B and C working together can finish it in 8 hours, in how many hours can C alone finish the work?

7. A, B and C working together can finish a piece of work in 8 hours. A alone can do it in 20 hours and B alone can do it in 24 hours. In how many hours will C alone do the same work?

8. A and B can finish a piece of work in 6 days and 4 days respectively. A started the work and worked at it for 2 days. He was then joined by B. Find the total time taken to finish the work.

9. A can do a piece of work in 14 days while B can do it in 21 days. They began together and worked at it for 7 days. Then, A was not well and B had to complete the work. In how many days was the work completed?

10. A, B and C can do a piece of work in 15, 12 and 20 days respectively. They started the work together, but C left after 2 days. In how many days will the remaining work be completed by A and B?

11. A and B can do a piece of work in 18 days; B and C can do it in 24 days while C and A can finish it in 36 days. In how many days can A, B, C finish it, if they all work together?

12. A and B can do a piece of work in 12 days, B and C in 15 days, and C and A in 20 days. How much time will A alone take to finish the job?

13. Pipes A and B can fill an empty tank in 10 hours and 15 hours respectively. If both are opened together in the empty tank, how much time will they take to fill it completely?

14. Pipe A can fill an empty tank in 5 hours while pipe B can empty the full tank in 6 hours. If both are opened at the same time in the empty tank, how much time will they take to fill it up completely?

15. Three taps A, B and C can fill an overhead tank in 6 hours, 8 hours and 12 hours respectively. How long would the three taps take to fill the empty tank, if all of them are opened together?

16. A cistern has two inlets A and B which can fill it in 12 minutes and 15 minutes respectively. An outlet C can empty the full cistern in 10 minutes. If all the three pipes are opened together in the empty tank, how much time will they take to fill the tank completely?

17. A pipe can fill a cistern in 9 hours. Due to a leak in its bottom, the cistern fills up in 10 hours. If the cistern is full, in how much time will it be emptied by the leak?

Hint. Work done by the leak in 1 hour = (¹/₉ – ¹/₁₀) = ¹/₉₀

18. Pipe A can fill a cistern in 6 hours and pipe B can fill it in 8 hours. Both the pipes are opened and after two hours, pipe A is cl?sed. How much time will B take to fill the remaining part of the tank?

Hint. Work done by (A + B) in 1 hour = (¹/₆ + ¹/₈) = ⁷/₂₄

Work done by both in 2 hours = (⁷/₂₄ × 2) = ⁷/₁₂

Remaining part = (1 - ⁷/₁₂) = ⁵/₁₂

Now, ¹/₈ part is filled by B in 1 hour. Find how much time B will take to fill ⁵/₁₂ part.

### Below the worksheet on time and work we will find the answers of the given question.

1. 13¹/₃ days.

2. 6 hours 40 minutes.

3. 18 days.

4. 10 hours

5. 3⁷/₁₁ days.

6. 48 hours.

7. 30 hours.

8. 3³/₅ days.

9. 10¹/₂ days.

10. 4 days.

11. 16 days.

12. 30 days.

13. 6 hours.

14. 30 hours.

15. 2 hours 40 minutes.

16. 20 minutes.

17. 90 hours.

18. 3¹/₃ hours.

Time and Work

Time and Work

Pipes and Cistern

Practice Test on Time and Work

Time and Work - Worksheets

Worksheet on Time and Work


text:
A Matrix equation

Let $A$ and $B$ be two $n \times n$ full-rank matrices.

Let $XAY = B$ be the given equation where $X$ and $Y$ are unknown $n \times n$ matrices. We know that $Vec(B) = (Y^{T} \otimes X)Vec(A)$. Under what conditions can we determine $X$ and $Y$ and what would be the procedure to determine $X$ and $Y$?

Not looking for the obvious solutions such as $Y^{-1}=A$ and $X=B$, $A$ is the eigenvalue (or some multiple of eigenvalue) diagonal matrix of $B$ where $X$ and $Y$ diagonalizes $B$ and $A$ and $B$ are similar to $X$ and $Y$. In general are there any other possible choices that $Y^{T} \otimes X$ can take? These may be the only choices for general $A$ and $B$. However, given $A$ and $B$ are some other structured matrices, has such an equation been studied before?

-
$X=I$ and $Y=A^{-1}B$? or am I missing something? –  Suvrit Aug 31 '11 at 0:18

1 Answer

Since $A$ and $B$ are invertible, replace $X$ by $X' = XA$ and replace $Y$ by $Y' = YB^{-1}$. Then your equation reduces to solving $X'Y' = I$, i.e. the space of solutions is parametrized by $GL(n)$.

-
I was actually curious of a meaning behind Theorem 9.3.5 here: books.google.com/… –  user16007 Aug 31 '11 at 4:23
No idea about that, sorry. I can't see the second half of the theorem since Google is not showing me page 311. –  MTS Aug 31 '11 at 4:48
I think you need only pages 309 and 310! –  user16007 Aug 31 '11 at 11:27


text:
This is the final installment of this this mini-series on application performance profiling. The aim of these blogs is to give an overview of the process of application profiling for performance optimization. The topics we cover in this series are:

1. Performance profiling concepts: Parallelism, the critical path, and Amdahl's argument.
2. The right tool for the job: Tracing, sampling and instrumenting profilers.
3. Interpreting profiles and diagnosing issues: An example with MPI and I/O.

In this blog, we will use the concepts introduced in the previous two parts to analyze an example application, first at a high level, and then looking into a specific area of performance.

## The Example Code

For this blog post the example that we will use is the EPOCH open-source plasma physics code. This is a high-performance, MPI parallel application, capable of scaling efficiently to use many thousands of processors in HPC clusters. However, in this case, we will run it on just a few processes and look at the efficiency in the case that we want to write a large number of output files during the simulation. This might be required, for example, to capture fine-grained time-dependent behaviour of the plasma during the simulation period.

## Building A Picture of the Application

As we saw in part one, it is important to understand the overall application behaviour in order to determine what the code spends its time doing. For the case of a pure MPI code with no accelerators, and no OpenMP regions, we can cleanly divide the runtime into time spent doing computation, communication, and file I/O. Since EPOCH is an MPI parallel code, using MPI I/O to write data files, we can use a tracing profiler to efficiently gather this information. For this example, the data was collected with the open source Extrae tracing profiler. In this case, the code is configured to save its output after every 20 simulation steps, running for 100 steps in total.

The resulting trace timeline is shown below

From this, we can see that the simulation runs for roughly 150 seconds and appears to make balanced use of all the cores. However, when we look to see what the code is doing we find the runtime is dominated by the time in the I/O routines actually writing the output files, the actual simulation is a tiny fraction of this.

## Investigating the Hotspot

Now we know that writing the output files is the major bottleneck, we can investigate in more detail to try and work out what exactly the code is doing, and whether the performance can be improved.

To investigate the I/O issues in more detail we can now switch to using a tool specifically designed for investigating I/O behaviour. In this case we use Darshan, another open-source profiler. It is a tracing profiler designed to capture detailed statistics about the application's use of multiple types of I/O including MPI I/O and Posix I/O.

As with the high-level profiling, the first information to extract is the summary performance data:

# *******************************************************
# POSIX module data
# *******************************************************
# performance
# -----------
# total_bytes: 7686
#
# I/O timing for unique files (seconds): 0.019487
# I/O timing for shared files (seconds): 3.654749
# Aggregate performance, including both shared and unique files (MiB/s): 0.001995

# *******************************************************
# MPI-IO module data
# *******************************************************
# performance
# -----------
# total_bytes: 2466400536
#
# I/O timing for unique files (seconds): 0.000000
# I/O timing for shared files (seconds): 124.677478
# Aggregate performance, including both shared and unique files (MiB/s): 18.865820

This confirms that EPOCH almost exclusively performs MPI parallel I/O and, as reported by Extrae, spends roughly 82% of its time performing this I/O. The 7 kB of POSIX I/O is performed by the master process to read the configuration file at the start of the execution. (Note that there is some overlap between the data gathered by Darshan and Extrae, however as a dedicated I/O profiler Darshan is capable of gathering richer data and automatically calculating useful figures of merit.)

The next question we should ask is, "is this what we expect?" Checking the six output files shows they are each about 400 MB in size, consistent with the reported total I/O size. What is concerning, however, is the fact that the code takes roughly 124 seconds to write just 2.4 GB of data, an average performance of just 18 MB/s. Given that this data was captured on an HPC with a high performance GPFS filesystem, we would expect at least an order of magnitude better I/O performance, for example a write rate of over 1000 MB/s is achieved by the BT-IO benchmark on the same system.

To understand more about the behaviour of EPOCH we can use the Darshan results to view the type of writes that EPOCH is performing. The histogram below shows the number and size of writes performed as well as whether they are independent (i.e by a single process) writes, or collective writes (i.e all processes write some data at once). For MPI I/O collective writes are typically much more efficient than independent writes as the library can make performance optimizing decisions, as well as writing data in parallel. Writing large amounts of data in a single write is also much more efficient than writing in multiple segments as there are large latency and overhead costs associated with writing to the filesystem, managing metadata etc,

From this we can see that EPOCH is performing many thousands of very small (< 100 byte) independent writes which are used to populate metadata fields in the output file. This suggests that the cause of the poor write performance is due to large overhead costs being incurred by writing the data as small blocks through many calls. Modifying the code to merge as many of these small writes as possible should improve the performance of the code, something that can be quickly checked by repeating the analysis above with a modified version and comparing the results.

In the above example, we were able to use two tools to determine the primary cause of inefficiency in an example code. By first considering the overall application behaviour we found that the application spent the majority of time performing I/O and that this I/O performance was unexpectedly poor. This suggests the use of a second tool to provide detailed information on the I/O behaviour of code which highlighted a large number of very small, independent writes, which is a common inefficiency pattern observed in MPI-IO codes.

## Conclusions

There is a huge number of different profiling and performance analysis tools available in the software development ecosystem, and knowing which tool to choose and where to begin analysing performance is not straightforward.

In the previous parts of the series we considered the types of tools that are available and strategies for efficiently locating the causes of performance inefficiencies. In this final entry in the series we used the EPOCH PIC code as an example of this approach. Initially looking at an overview of the trace showed that the majority of the time was spent in I/O, making it the optimization target with the greatest potential for improvement.

Looking deeper at the I/O using a dedicated I/O profiler the average write speed was just 20 MB/s, compared to the benchmarked value of over 1 GB/s suggesting that the code performance can potentially be improved by an order of magnitude or more. Then using the same tool to look at the actual writes made, it is clear that the code is performing many very small writes. This is a known inefficient pattern which can be improved by aggregating many small writes into one larger one.

## Example Files

The trace files used in this blog and the accompanying webinar, along with the original EPOCH configuration file are available to download here. Please read the included instructions for detailed information on how to open and explore them.

Author


text:
# If $X$ is a simplicial complex, is their a characterization of the links of the vertices of $X$ that is equivalent to the statement "$|X|$ is a manifold

We have a characterization when we want $|X|$ to be a PL-manifold, in particular that the links of all the vertices are themselves (PL) spheres. If we are in the category of PL- spaces then this is a necessary and sufficient condition. If however, we leave the PL category, then we get simplicial complexes that are topologically spheres, but not PL spheres. For instance if we take the double suspension of a homology sphere, then we get a sphere. If our homology sphere has a triangulation (and is not itself a sphere), then the double suspension also has a triangulation. The links of the suspension points are not spheres, but these links do have the homotopy type of spheres. Furthermore, the links of these suspension points are also pure simplicial complexes (pure meaning that that all top dimensional simplicies have the same dimension).

I have drawn the following conclusion: If $X$ is a simplicial complex, |X| is a topological manifold of dimension $N$, then the links of all of the vertices are pure simplicial complexes of dimension $N-1$ and have the homotopy type of the $N-1$ sphere.

What is the converse to this conclusion? Namely what extra conditions must be put on the links of the vertices other than purity and being homotopy sphere that will be equivalent to $|X|$ is a manifold?

note: This question is similar to When are (finite) simplicial complexes (smooth) manifolds? . However, the I did not find the answer there. This is also a slightly different question.

• A tautological answer would be "all links have to be homeomorphic, not just homotopy equivalent to spheres". But I'm not sure whether this is really what you're after. – algori Dec 13 '12 at 21:18
• That does not seem true, since if you take the link of one of the suspension points of a double suspension of a homology three sphere (like Poincare's dodecaheadral space), you get the suspension of the homology manifold, which I do not even think is a manifold. – Spice the Bird Dec 13 '12 at 21:46
• Spice the Brid -- this is a sufficient condition, not a necessary one. I.e., it implies that $|X|$ is a manifold, but not the other way around. – algori Dec 13 '12 at 21:58
• OK I agree with that. I was looking for an equivalent statement. That is reflected in the title, but is not reflected properly in the grey box. Thank you. – Spice the Bird Dec 13 '12 at 22:02

In dimensions $\geq 5$, Theorem 1.5 of Galewski and Stern implies that if the links of the vertices of a homology manifold of dimension $\geq 5$ are simply-connected, then it is a manifold.

I'm not sure if this is equivalent to your condition. Certainly your condition implies that the links of vertices are simply-connected and are homology spheres. But to be a homology $n$-manifold, the links of the barycentric subdivision must be $n-1$-homology spheres as well, and I'm not sure whether that is implied by your conditions.

In $1, 2, 3$ and (I believe) $4$ dimensions, I think it's necessary and sufficient to have links be $n-1$-spheres.

I don't think there will be a simple necessary and sufficient condition.

For exotic triangulations, the links $L$ of vertices will not be manifolds. One thing you need (not sufficient) is for $L \times \mathbb{R}$ to be a manifold. It's kind of shocking that this is possible for non-manifolds; the first example of it is Bing's dogbone space. A weaker version of the phenomena is the Whitehead manifold $W$, which is a contractible $3$-manifold which is not homeomorphism to $\mathbb{R}^3$ but such that $W \times \mathbb{R}$ is homeomorphism to $\mathbb{R}^4$.

To get an idea of the kinds of things that are involved here, I recommend reading the introduction to Edwards's paper "Suspensions of homology spheres", available here. That paper also contains a very detailed account of the fact that the double suspension of Mazur's homology 3-sphere is a 5-sphere (with lots of pictures). Another nice account of this is in Steve Ferry's notes on geometric topology, available here.

• Rob Kirby's lecture here dailymotion.com/video/xuvg6y_kirby1_tech has a discussion of the examples obtained from the double suspension theorem. From what Kirby says of such examples, I would not want to meet them in a dark alley. – Lee Mosher Dec 14 '12 at 0:56
• I met one in a dark alley once. He wasn't so mean, but sort of ugly. – Spice the Bird Dec 14 '12 at 2:27


text:
# How to evaluate a limit with roots

1. Sep 26, 2013

### MathewsMD

1. The problem statement, all variables and given/known data

I have the limit: lim [ (x+h)^2/3 - x^(2/3) /h ]

How would I further simplify and evaluate this limit.

2. The attempt at a solution

I have tried using a change of variable and using this in the sum of cubes formula (i.e. (x+h)^(2/3) = a, x^(2/3) = b, and then plugging this in to the sum of a cube equation. This did not help and just further complicated matters.

Next, I tried multiplying the numerator and denominator by {x+h)^(1/3) + x^(1/3) to cancel out the roots, but this just made new ones that were even harder to factor out.

I keep trying variations of the two methods I just described, but none of them work. Any direction or help on what to do next would be great. Thanks!

2. Sep 26, 2013

### Dick

Your sum of cubes formula really should help. (a-b)(a^2+ab+b^2)=a^3-b^3. Show why it doesn't? Multiply numerator and denominator by (a^2+ab+b^2).

3. Sep 26, 2013

### MathewsMD

Well I had h in the denominator, and what I was doing never allowed me to factor out the h in the expression. I ended up getting limh→0 [(a^(1/3) - b^(1/3))(a^2/3) + a^(1/3)b^(1/3) + b^(2/3) / h] and a = (x+h)^(2/3) and b = x^(2/3)

It got very messy, and I'm not sure if it's because I made an error in my steps, but I couldn't really go much further than this. I could just never factor out the h when I substituted the values for a and b back in. Any advice/thoughts would be appreciated.

4. Sep 27, 2013

### Simon Bridge

$$\lim_{h\rightarrow 0}\frac{(x+h)^{2/3}-x^{2/3}}{h}$$ ... is the derivative of $x^{2/3}$.

Is the problem to show this derivative by the definition or just to show the derivative?

if the latter then you can rewrite it as $y^3(x)=x^2$ and use the power rule.

If the former - OK: then you need to check your algebra if you cannot get h to factor out.
Just looking at it - for some reason you ended up with h alone in the denominator ... don't do that. Leave the denominator alone and concentrate on factoring an h out of the numerator.

Compare yours with:

$$\lim_{h\rightarrow 0}\frac{(x+h)^{2/3}-x^{2/3}}{h}= \lim_{h\rightarrow 0}\left [ \left ( \frac{(x+h)^{2/3}-x^{2/3}}{h}\right ) \left ( \frac{(x+h)^{4/3}+(x+h)^{2/3}x^{2/3}+x^{4/3}}{(x+h)^{4/3}+(x+h)^{2/3}x^{2/3}+x^{4/3}}\right ) \right ]$$

... it does get messy - which is why we don't normally do it that way - you just have to slog through carefully. I find it helps to use a large window and a whiteboard marker.

5. Sep 27, 2013

### Dick

It's not even all that much of a slog, is it? If you remember (a-b)(a^2+ab+b^2)=a^3-b^3, you can immediately replace the numerator with a^3-b^3=(x+h)^2-x^2. That's easy to expand. Then factor out the h and take h->0.

Last edited: Sep 27, 2013
6. Sep 27, 2013

### Simon Bridge

If you are used to this sort of stuff it can be shown in about three steps from here. That would make it just-about "doing the problem for him" - I realize.

If you are just learning - though - there will still be a bunch of false starts, like we've seen already, and it can get confusing keeping track of all the exponents and where the minus signs go.

Making sure students do an exercise like this is supposed to motivate the shortcut approaches. I think MathewsMD has got there already :) The RH parentheses is basically what those a's and b's expand out to and it's the lynchpin. Comparing that with what he got should expose what went wrong.

Building on the power rule for integers, already proved by the definition, and using implicit differentiation, turns this into a bunch of much easier steps... and is more like how math is actually done.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted


text:
Documentation

# blackmanharris

Minimum four-term Blackman-Harris window

## Description

example

w = blackmanharris(N) returns an N-point symmetric four-term Blackman-Harris window.

w = blackmanharris(N,sflag) returns a Blackman-Harris window using the window sampling method specified by sflag.

## Examples

collapse all

Create a 32-point symmetric Blackman-Harris window. Display the result using wvtool.

N = 32;
wvtool(blackmanharris(N))

## Input Arguments

collapse all

Window length, specified as a positive integer.

Data Types: single | double

Window sampling method, specified as:

• 'symmetric' — Use this option when using windows for filter design.

• 'periodic' — This option is useful for spectral analysis because it enables a windowed signal to have the perfect periodic extension implicit in the discrete Fourier transform. When 'periodic' is specified, the function computes a window of length L + 1 and returns the first L points.

## Output Arguments

collapse all

Blackman-Harris window, returned as a column vector.

## Algorithms

The equation for the symmetric four-term Blackman-Harris window of length N is

$w\left(n\right)={a}_{0}-{a}_{1}\mathrm{cos}\left(\frac{2\pi n}{N-1}\right)+{a}_{2}\mathrm{cos}\left(\frac{4\pi n}{N-1}\right)-{a}_{3}\mathrm{cos}\left(\frac{6\pi n}{N-1}\right),\text{ }0\le n\le N-1$

The equation for the periodic four-term Blackman-Harris window of length N is

$w\left(n\right)={a}_{0}-{a}_{1}\mathrm{cos}\frac{2\pi n}{N}+{a}_{2}\mathrm{cos}\frac{4\pi n}{N}-{a}_{3}\mathrm{cos}\frac{6\pi n}{N},\text{ }0\le n\le N-1$

The periodic window is N-periodic.

CoefficientValue
a00.35875
a10.48829
a20.14128
a30.01168

## References

[1] harris, fredric j. “On the Use of Windows for Harmonic Analysis with the Discrete Fourier Transform.” Proceedings of the IEEE®. Vol. 66, January 1978, pp. 51–83.


text:
# innodb_status_file

--innodb-status-file

Property Value
Command-Line Format –innodb-status-file[={OFF ON}]
Type Boolean
Default Value OFF

The --innodb-status-file startup option controls whether InnoDB creates a file named innodb_status.*pid* in the data directory and writes SHOW ENGINE INNODB STATUS output to it every 15 seconds, approximately.

The innodb_status.*pid* file is not created by default. To create it, start mysqld with the --innodb-status-file option. InnoDB removes the file when the server is shut down normally. If an abnormal shutdown occurs, the status file may have to be removed manually.

The --innodb-status-file option is intended for temporary use, as SHOW ENGINE INNODB STATUS output generation can affect performance, and the innodb_status.*pid* file can become quite large over time.

For related information, see Section 14.18.2, “Enabling InnoDB Monitors”.

#### Directing Standard InnoDB Monitor Output to a Status File

Standard InnoDB Monitor output can be enabled and directed to a status file by specifying the --innodb-status-file option at startup. When this option is used, InnoDB creates a file named innodb_status.*pid* in the data directory and writes output to it every 15 seconds, approximately.

InnoDB removes the status file when the server is shut down normally. If an abnormal shutdown occurs, the status file may have to be removed manually.

The --innodb-status-file option is intended for temporary use, as output generation can affect performance, and the innodb_status.*pid* file can become quite large over time.

# innodb_status_output_locks

innodb_status_output_locks=off

innodb_status_output_locks=on, innodb_show_verbose_locks=0

innodb_status_output_locks=on, innodb_show_verbose_locks=1

# innodb_show_verbose_locks

percona分支参数

• variable innodb_show_verbose_locks

Command Line:YesConfig File:YesScope:GlobalDynamic:YesVariable Type:ULONGDefault Value:0Range:0 - 1

Specifies to show records locked in SHOW ENGINE INNODB STATUS. The default is 0, which means only the higher-level information about the lock (which table and index is locked, etc.) is printed. If set to 1, then traditional InnoDB behavior is enabled: the records that are locked are dumped to the output.

innodb_show_verbose_locks=1, innodb_print_all_deadlocks=1, 则error log中死锁信息为

innodb_status_output=1,innodb_show_verbose_locks=0或1, innodb_status_output_locks=off

innodb_status_output=1,innodb_show_verbose_locks=0, innodb_status_output_locks=on

innodb_status_output=1,innodb_show_verbose_locks=1, innodb_status_output_locks=on


text:
# Marginal Distribution for x [closed]

I want to calculate the marginal distribution of $$X$$ given that the joint probability density function of $$(X,Y)$$ is given by $$f(x,y)=2592(x^2-y^2)e^{-2x} \qquad 0

My problem is to determine the bounds of integration for the marginal density. Are they going to be from $$-x$$ to $$0$$ and then from $$0$$ to $$x$$? Or just from $$0$$ to $$x$$ since $$x$$ can only assume positive values?

• You seem to be circumventing an automatic block the system has placed on your posts due to consistently poor questions. Please visit stats.stackexchange.com/help/merging-accounts to merge your accounts, lest the system take more drastic action. – whuber Oct 24 '20 at 15:46

The support of $$Y$$ conditional on the value of $$X=x$$ is $$(-x,x)$$ so that should be your region of integration.


text:
# Skewness of a mixture density

I am fitting a gaussian mixture to financial data. My mixture density is given by:

$f(l)=πϕ(l;μ_1,σ^2_1)+(1−π)ϕ(l;μ_2,σ_2^2)$

I calculated the skewness of the data already. Now, I want to look at the skewness of the fitted gaussian mixture. Since I used ML (EM algorithm) and not method of moments, the moments will not be the same. I know this. But I don't know how to calculate the skewness of the mixed gaussian? I want to have a theoretical derived formula, so I mean, I don't want to calculate this empirical by taking the fitted values and do e.g. skew(...) in R. I will do this to control myself, but first I want to have the theoretical formula for it. I could not find it (I googled for skewness mixture density and so.)

I know that the the skewness is given by

$\gamma_1 = \operatorname{E}\Big[\big(\tfrac{X-\mu}{\sigma}\big)^{\!3}\, \Big] = \frac{\mu_3}{\sigma^3} = \frac{\operatorname{E}\big[(X-\mu)^3\big]}{\ \ \ ( \operatorname{E}\big[ (X-\mu)^2 \big] )^{3/2}}$

So what is the Skewness of a mixture gaussian? How can I derive it? A mathematical derivation would be great. I have estimated both densities and I have the estimates for μ and σ. I want a formula in what I can insert those values to get the skewness of the mixed density. Then I will control it empirically with skew(...) in R.

I know this for the kurtosis: and I want to have this for skewness and - this would be great- a derivation of it?

• The formulas for moments of mixture distributions are given in the statement of the question at stats.stackexchange.com/questions/54645/…. That substantially answers this one, too, given that skewnesses are rational combinations of moments as shown in the formula for $\gamma_1$. – whuber Mar 30 '13 at 15:17
• @whuber mh, this doesn't help me much, I am not good in reading those formulas.... – Stat Tistician Mar 30 '13 at 15:18
• Please explain: you are asking for a formula and a theoretical derivation and that thread provides it. If there is a part of it you do not understand (or think is incorrect), then please point it out; otherwise it's impossible to know what your question really is and it will just be closed by the community. – whuber Mar 30 '13 at 15:19
• I want to have a formula for the skewness like I have for the kurtosis above in my question @whuber I want to plug in my estimators and get the skewness. – Stat Tistician Mar 30 '13 at 15:20
• And using either the formulas in that thread or the one given by @Triple roast here, in conjunction with formulas you have already presented in your question, you have a plug-in solution. – whuber Mar 30 '13 at 15:21

Skewness is a vague concept which allows its formalisation in several ways. The most popular measure of skewness is the one you mention, which was proposed more than 100 years ago. However, there are better (more interpretable) measures nowdays.

It has been largely discussed the validity of using a measure of skewness in multimodal distributions, since its interpretation becomes unclear. This is the case of finite mixtures. If your mixture looks (or is) unimodal, then you can use this value to understand a bit how asymmetric it is.

In R, this quantity is implemented in the library moments, in the command skewness().

The moments of a mixture $X$, with density $g=\sum_{j=1}^n \pi_j f_j$ can be calculated as $E[X^k] = \sum_{j=1}^n \pi_j\int x^k f_j(x)dx$.

A numerical solution in R.

# Sampling from a 2-gaussian mixture
gaussmix <- function(n,m1,m2,s1,s2,alpha) {
I <- runif(n)<alpha
rnorm(n,mean=ifelse(I,m1,m2),sd=ifelse(I,s1,s2))
}

# A simulated sample
samp <- gaussmix(100000,0,0,1,1,0.5)

library(moments)
# Approximated kurtosis and skeweness using the simulated sample
skewness(samp)
kurtosis(samp)

• yeah, but I don't want to do the R step first. I want to have mathematical derivation/formula for it? @Triple roast I mean, I have the ML estimates and I put them into a mathematical derived formula to get the skewness. So not the empirical solution, you know what I mean? But in your formula I cannot put in my estimates? – Stat Tistician Mar 30 '13 at 15:10
• Yes, please see my update. It is simple to calculate moments of a mixture, using the linearity of the expectation. Still, my first argument may be of interest. – Triple roast Mar 30 '13 at 15:12
• see my edit in my question, I have this for kurtosis and want to have a similiar formula for skewness. – Stat Tistician Mar 30 '13 at 15:14
• +1 The preliminary discussion and cautionary comments are on the mark. Thank you for sharing your wisdom and welcome to our site! – whuber Mar 30 '13 at 15:18
• Thanks, @whuber. Stat, please check my update (stolen from this answer). It is numerical, but it may be of some help. Cheers. – Triple roast Mar 30 '13 at 15:30


text:
Maximum sum of angles in triangle in sphere

Recently my differential geometry lecturer demonstrated that the sum of the interior angles of a triangle in a sphere is not necessarily never $180^\circ$. This is one way to prove that the earth is not flat. I was wondering, what then is the maximum sum of the interior angles of triangles in a sphere, since this sum is not a constant?

• The maximal sum of interior angles is achieved by drawing a very small triangle somewhere on the sphere and then declaring the inside to be the outside and vice versa. The sum of the interior and exterior angles is necessarily always $3\times 360^\circ$ and since one of these sets cannot sum to less than $180^\circ$, the opposite one cannot be more than $5\times 180^\circ$. – Henning Makholm Oct 24 '11 at 23:52
• The "not necessarily" in the question should be replaced by "never" (unless one is prepared to accept degenerate triangles, where all three vertices lie on a line). – Gerry Myerson Oct 25 '11 at 0:04
• @GerryMyerson Hmm...I never thought of that. – Samuel Tan Oct 25 '11 at 0:25

Perhaps your teacher taught you something like this from Wikipedia: $$180^{\circ}\times\left(1+4 \tfrac{\text{Area of triangle}}{\text{Surface area of the sphere}}\right)$$
If you are prepared to have a triangle which has more than half the area of the sphere then the maximum can approach $900^\circ$; if not then $540^\circ$.
• You get an angle sum close to $180^{\circ}$ with a very small triangle. Turn this inside out and you get an angle sum close to $900^{\circ}$ with a triangle which covers almost all of the sphere. In each case the limit is a degenerate triangle (as Gerry Myerson said) and so perhaps cannot be achieved. – Henry Oct 25 '11 at 11:17


text:
Turns wide-table formats (species-traits matrix and occurrence table) into long-table format. As input, the function requires information about which columns contain traits, given as a list of trait-names, and which column contains the taxon name. For tables containing repeated measurements of traits within the same taxon, an occurrenceID should be given or will be created.

as.traitdata(x, traits = attributes(x)$traits, taxa = attributes(x)$taxa,
individuals = attributes(x)$individuals, occurrences = individuals, datasetID = attributes(x)$datasetID,
measurements = attributes(x)$measurements, units = attributes(x)$units,
keep = attributes(x)$keep, drop = NULL, na.rm = TRUE, id.vars = names(x)[names(x) %in% keep & !names(x) %in% drop], mutate = NULL, thesaurus = attributes(x)$thesaurus,


text:
# Triangle of Maximum Area II

Leo Giugiuc posted an optimization problem at the CutTheKnotMath facebook page together with a solution (Solution 1) by Claudia Nanuti, Diana Trailescu, Dan Sitaru and Leo Giugiuc and with a reference to the Mathematical Inequalities facebook group.

Let $ABC$ be a triangle whose sides $a,b,c$ satisfy

$1\lt a\le 2\le b\le 5\le c\le 6.$

Find maximum possible area of $\Delta ABC.$

Solution

Let $ABC$ be a triangle whose sides $a,b,c$ satisfy

$1\lt a\le 2\lt b\le 5\lt c\le 6.$

Find maximum possible area of $\Delta ABC.$

### Solution 1

Let $x=c^2\in (25,36],\;$ $y=b^2\in (9,25],\;$ $z=a^2\in (1,4].$ By Heron's formula, for the area $[\Delta ABC]\;$ of $\Delta ABC\;$ we have

$16[\Delta ABC]^2=-x^2+2(y+z)x-(y-z)^2.$

The function $f(x)=-x^2+2(y+z)x-(y-z)^2\;$ attains its maximum at $x=y+z:\;$ $f(x)\le f(y+z)=4yz,$ implying that $f(x)\le 400.\;$ We observe that that value is attained for $y=25\;$ and $z=4\;$ such that $x=25+4=29.\;$ Thus $\max [\Delta ABC]=5\;$ and is attained with $a=2,\;$ $b=5,\;$ and $c=\sqrt{29}.$

### Solution 2

Observe that at least one of $a,b,c$ for which the area of the triangle is maximum ought to be at the upper end of its range, i.e., either $a=2,\;$ or $b=5,\;$ or $c=6.\;$ For, otherwise, it would be possible to expand the triangle (if only a little) by making one of the conditions satisfied without infringing on other constraints.

The three diagrams below illustrate the three possible cases: when one of the sides (viz, the horizontal one) is successively $2,\;$ $5,\;$ and $6.\;$ In each case the area where the remaining constraints are satisfied is filled yellow.

Assume $AB=2.\;$ The yellow area is the intersection of the filled circles $A(5)\;$ and $B(6).\;$ The maximum area is attained for the third vertex $C$ at the top of circle $A(5)\;$ with center $A\;$ and radius $5.\;$ $\Delta ABC\;$ is right with area $\frac{1}{2}2\cdot 5.$

Assume $AB=5.\;$ The yellow area is the intersection of the filled circles $A(2)\;$ and $B(6).\;$ The maximum area is attained for the third vertex $C$ at the top of circle $A(2)\;$ with center $A\;$ and radius $2.\;$ $\Delta ABC\;$ is right with area $\frac{1}{2}2\cdot 5.$

Assume $AB=6.\;$ The maximum area is attained for the third vertex $C$ at the intersection of $A(2)\;$ and $B(5).\;$ In this case, $[\Delta ABC]=\frac{1}{2}2\cdot 5\sin\angle ACB\lt 5.\;$

In the first two cases, by the Pythagorean theorem, $c=\sqrt{29}.$

### Proof 3

Grégoire Nicollier has observed that, in general, $[\Delta ABC=\frac{1}{2}ab\sin\angle ACB\;$ is a function that depends linearly on the independent variables $a,\;$ $b,\;$ and $\sin\angle ACB\;$ so that it attains its maximum when each of them takes up the maximum possible value, i.e., in this case, $a=2,\;$ $b=5,\;$ and $\sin\angle ACB=1,\;$ making the maximum area $\frac{1}{2}ab=5.\;$ The only restriction to this happening may come from the hypotenuse $\sqrt{a^2+b^2}\;$ not satisfying the constraint imposed on $c.\;$ But clearly $\sqrt{2^2+5^2}=\sqrt{29}\in (5,6].$

### A Sample of Optimization Problems III

• Mathematicians Like to Optimize
• Mathematics in Pizzeria
• The Distance to Look Your Best
• Building a Bridge
• Linear Programming
• Residence at an Optimal Distance
• Distance Between Projections
• Huygens' Problem
• Optimization in a Crooked Trapezoid
• Greatest Difference in Arithmetic Progression
• Area Optimization in Trapezoid
• Minimum under Two Constraints
• Optimization with Many Variables
• Minimum of a Cyclic Sum with Logarithms
• A Problem with a Magical Solution from Secrets in Inequalities
• Leo Giugiuc's Optimization with Constraint
• Problem 4033 from Crux Mathematicorum
• An Unusual Problem by Leo Giugiuc
• A Cyclic Inequality With Constraint in Two Triples of Variables
• Two Problems by Kunihiko Chikaya
• An Inequality and Its Modifications
• A 2-Variable Optimization From a China Competition


text:
<< October 2018 >>

Tuesday, October 2, 2018

Seminar 217, Risk Management: Predicting Portfolio Return Volatility at Median Horizons

Seminar: Risk Seminar | October 2 | 11 a.m.-12:30 p.m. | 1011 Evans Hall

Speaker: Dangxing Chen, UC Berkeley

Commercially available factor models provide good predictions of short-horizon (e.g. one day or one week) portfolio volatility, based on estimated portfolio factor loadings and responsive estimates of factor volatility. These predictions are of significant value to certain short-term investors, such as hedge funds. However, they provide limited guidance to long-term investors, such as Defined...   More >

The challenge of big data and data science for the social sciences: Berkeley Distinguished Lectures in Data Science

Lecture: Other Related Seminars | October 2 | 4:10-5 p.m. | 190 Doe Library

Henry Brady, Dean, Goldman School of Public Policy; Henry Brady, Dean, Goldman School of Public Policy

The 2005 National Science Foundation workshop report on "Cyberinfrastructure for the Social and Behavioral Sciences" (Fran Berman and Henry Brady) argued that the methods of doing research in the social sciences would be transformed by big data and data science and that the social sciences should be centrally involved in studying the impacts of big data and data science on society. In "The...   More >

Wednesday, October 3, 2018

Concentration from Geometry in High Dimension

Seminar: Probability Seminar | October 3 | 3-4 p.m. | 1011 Evans Hall

Santosh Vempala, Georgia Tech

Department of Statistics

The concentration of Lipschitz functions around their expectation is a classical topic that continues to be very active. We will discuss some recent progress, including:
1- A tight log-Sobolev inequality for isotropic logconcave densities
2- A unified and improved large deviation inequality for convex bodies
3- An extension of the above to Lipschitz functions (generalizing the Euclidean...   More >

Statistical challenges in casualty estimation

Seminar: Neyman Seminar | October 3 | 4-5 p.m. | 1011 Evans Hall

Kristian Lum, Human Rights Data Analysis Group

Department of Statistics

An accurate understanding of the magnitude and dynamics of casualties during a conflict is important for a variety of reasons, including historical memory, retrospective policy analysis, and assigning culpability for human rights violations. However, during times of conflict and their aftermath, collecting a complete or representative sample of casualties can be difficult if not impossible. One...   More >

Center for Computational Biology Seminar: Dr. Quaid Morris, Professor, Donnelly Centre for Cellular and Biomolecular Research, University of Toronto

Seminar: Other Related Seminars | October 3 | 4:30-5:30 p.m. | 101 Life Sciences Addition

Center for Computational Biology

Title: Making sense of the “noise” in cancer data

Tuesday, October 9, 2018

Seminar 217, Risk Management: Robust Learning: Information Theory and Algorithms

Seminar: Risk Seminar | October 9 | 11 a.m.-12:30 p.m. | 1011 Evans Hall

Speaker: Jacob Steinhardt, Stanford

This talk will provide an overview of recent results in high-dimensional robust estimation. The key question is the following: given a dataset, some fraction of which consists of arbitrary outliers, what can be learned about the non-outlying points? This is a classical question going back at least to Tukey (1960). However, this question has recently received renewed interest for a combination of...   More >

Letters of recommendation in Berkeley undergraduate admissions: Program evaluation and natural language processing: Berkeley Distinguished Lectures in Data Science

Lecture: Other Related Seminars | October 9 | 4:10-5 p.m. | 190 Doe Library

Jesse Rothstein, Professor, Public Policy and Economics, UC Berkeley

In Fall 2015 and 2016, UC Berkeley asked many freshman applicants to submit letters of recommendation as part of their applications. This was highly controversial. Proponents argued that letters would aid in the identification of disadvantaged students who had overcome obstacles that were not otherwise apparent from their applications, while opponents argued that disadvantaged students were...   More >

Wednesday, October 10, 2018

Large deviations of subgraph counts for sparse Erd\H{o}s--R\'enyi graphs

Seminar: Probability Seminar | October 10 | 3-4 p.m. | 1011 Evans Hall

Nicholas Cook, UCLA

Department of Statistics

For each fixed integer $\ell\ge 3$ we establish the leading order of the exponential rate function for the probability that the number of cycles of length $\ell$ in the Erd\H{o}s--R\'enyi graph $G(N,p)$ exceeds its expectation by a constant factor, assuming $N^{-1/2}\ll p\ll 1$ (up to log corrections) when $\ell\ge 4$, and $N^{-1/3}\ll p\ll 1$ in the case of triangles. We additionally obtain the...   More >

To persist or not to persist?

Seminar: Neyman Seminar | October 10 | 4-5 p.m. | 1011 Evans Hall

Sebastian Schreiber, UC Davis

Department of Statistics

Two long standing, fundamental questions in biology are "Under what conditions do populations persist or go extinct? When do interacting species coexist?" The answers to these questions are essential for guiding conservation efforts and identifying mechanisms that maintain biodiversity. Mathematical models play an important role in identifying these mechanisms and, when coupled with empirical...   More >

Tuesday, October 16, 2018

Seminar 217, Risk Management: Asymptotic Spectral Analysis of Markov Chains with Rare Transitions: A Graph-Algorithmic Approach

Seminar: Risk Seminar | October 16 | 11 a.m.-12:30 p.m. | 1011 Evans Hall

Speaker: Tingyue Gan, UC Berkeley

Parameter-dependent Markov chains with exponentially small transition rates arise in modeling complex systems in physics, chemistry, and biology. Such processes often manifest metastability, and the spectral properties of the generators largely govern their long-term dynamics. In this work, we propose a constructive graph-algorithmic approach to computing the asymptotic estimates of eigenvalues...   More >

Wednesday, October 17, 2018

The Lovász theta function for random regular graphs

Seminar: Probability Seminar | October 17 | 3-4 p.m. | 1011 Evans Hall

Jess Banks, UC Berkeley

Department of Statistics

The Lovász theta function is a classic semidefinite relaxation of graph coloring. In this talk I'll discuss the power of this relaxation for refuting colorability of uniformly random degree-regular graphs, as well as for distinguishing this distribution from one with a `planted' disassoratative community structure. We will see that the behavior of this refutation scheme is consistent with the...   More >

Learning in Google Ads, Machines and People

Seminar: Neyman Seminar | October 17 | 4-5 p.m. | 1011 Evans Hall

Department of Statistics

This talk is in two parts, both of which discuss interesting uses of experiments in Google search ads. In part 1 I discuss how we can inject randomness into our system to get causal inference in a machine learning setting. In part 2. I talk about experiment designs to measure how users learn in response to ads on Google.com.

Friday, October 19, 2018

4th Annual CDAR Symposium 2018

Conference/Symposium: Risk Seminar | October 19 | 8:30 a.m.-6:30 p.m. | Memorial Stadium, University Club

Our conference will feature new developments in data science, highlighting applications to finance and risk management. Confirmed speakers include Jeff Bohn, Olivier Ledoit, Ulrike Malmendier, Steven Kou, Ezra Nahum, Roy Henriksson, and Ken Kroner.

or or by emailing Sang Oum at soum@berkeley.edu by October 12.

Tuesday, October 23, 2018

Seminar 217, Risk Management: Proliferation of Anomalies and Zoo of Factors – What does the Hansen–Jagannathan Distance Tell Us?

Seminar: Risk Seminar | October 23 | 11 a.m.-12:30 p.m. | 1011 Evans Hall

Speaker: Xiang Zhang, SWUFE

Recent research finds that prominent asset pricing models have mixed success in evaluating the cross-section of anomalies, which highlights proliferation of anomalies and zoo of factors. In this paper, I investigate that how is the relative pricing performance of these models to explain anomalies, when comparing their misspecification errors– the Hansen–Jagannathan (HJ) distance measure. I find...   More >

Optimal robot action for and around people: Berkeley Distinguished Lectures in Data Science

Lecture: Other Related Seminars | October 23 | 4:10-5 p.m. | 190 Doe Library

Anca Dragan, Professor, Electrical Engineering and Computer Sciences, UC Berkeley

Estimation, planning, control, and learning are giving us robots that can generate good behavior given a specified objective and set of constraints. What I care about is how humans enter this behavior generation picture, and study two complementary challenges: 1) how to optimize behavior when the robot is not acting in isolation, but needs to coordinate or collaborate with people; and 2) what to...   More >

Wednesday, October 24, 2018

Constructing (2+1)-dimensional KPZ evolutions

Seminar: Probability Seminar | October 24 | 3-4 p.m. | 1011 Evans Hall

Alex Dunlap, Stanford University

Department of Statistics

The (d+1)-dimensional KPZ equation
$\partial_t h = \nu \Delta h + \frac{\lambda}{2}|\nabla h|^2 + \sqrt{D}\dot{W},$
in which \dot{W} is a space--time white noise, is a natural model for the growth of d-dimensional random surfaces. These surfaces are extremely rough due to the white noise forcing, which leads to difficulties in interpreting the nonlinear term in the equation. In...   More >

Safe Learning in Robotics

Seminar: Neyman Seminar | October 24 | 4-5 p.m. | 1011 Evans Hall

Claire Tomlin, UC Berkeley

Department of Statistics

A great deal of research in recent years has focused on robot learning. In many applications, guarantees that specifications are satisfied throughout the learning process are paramount. For the safety specification, we present a controller synthesis technique based on the computation of reachable sets, using optimal control and game theory. In the first part of the talk, we will review these...   More >

Wednesday, October 31, 2018

Rigidity and tolerance for perturbed lattices

Seminar: Probability Seminar | October 31 | 3-4 p.m. | 1011 Evans Hall

Yuval Peres, Microsoft Research

Department of Statistics

Consider a perturbed lattice {v+Y_v} obtained by adding IID d-dimensional Gaussian variables {Y_v} to the lattice points in Z^d.
Suppose that one point, say Y_0, is removed from this perturbed lattice; is it possible for an observer, who sees just the remaining points, to detect that a point is missing?


text:
As was discussed in the Analytics in Action from Chapter 2, the U.S. Census Bureau is a leading... 1 answer below »

As was discussed in the Analytics in Action from Chapter 2, the U.S. Census Bureau is a leading source of quantitative data related to the people and economy of the United States. The cross tabulation below represents the number of households (1,000s) and the household income by the highest level of education for the head of household (U.S. Census Bureau web site, 2013). Use this cross tabulation to answer the following questions. a. Develop a joint probability table. b. What is the probability the head of one of these households has a master s degree or higher education? c. What is the probability a household is headed by someone with a high school diploma earning $100,000 or more? d. What is the probability one of these households has an income below$25,000? e. What is the probability a household is headed by someone with a bachelor s degree earning less than \$25,000? f. Are household income and educational level independent?

Ashish

Solution: a. Divide the entire values in the table by the total number of household which is 65,644. This
gives the joint...

Plagiarism Checker

Submit your documents and get free Plagiarism report

Free Plagiarism Checker

Looking for Something Else? Ask a Similar Question


text:
Next: Notch filter Up: Z-plane, causality, and feedback Previous: Laurent expansion

# INTRODUCTION TO ALL-PASS FILTERS

An all-pass filter'' is a filter whose spectral magnitude is unity.

Given an input X(Z) and an output Y(Z), we know that the spectra of the two are the same, i.e., .The existence of an infinitude of all-pass filters tells us that an infinitude of wavelets can have the same spectrum. Wave propagation without absorption is modeled by all-pass filters. All-pass filters yield a waveform distortion that can be corrected by methods discussed in chapter .

The simplest example of an all-pass filter is the delay operator itself. Its phase as a function of is simply .

A less trivial example of phase distortion can be constructed from a single root Zr, where Zr is an arbitrary complex number. The ratio of any complex number to its complex conjugate, say (x+iy)/(x-iy), is of unit magnitude, because, taking and ,the ratio is .Thus, given a minimum-phase filter ,we can take its conjugate and make an all-pass filter P(Z) from the ratio .A simple case is
 (45) (46)
The all-pass filter is not causal because of the presence of 1/Z in .We can repair that by multiplying by another all-pass operator, namely, Z. The resulting causal all-pass filter is
 (47)
Equation (47) can be raised to higher powers to achieve a stronger frequency-dispersion effect. Examples of time-domain responses of various all-pass filters are shown in Figure 13.

 disper Figure 13 Examples of causal all-pass filters with real poles and zeros. These have high frequencies at the beginning and low frequencies at the end.

The denominator of equation (47) tells us that we have a pole at Zr. Let this location be .The numerator vanishes at
 (48)
In conclusion, the pole is outside the unit circle, and the zero is inside. They face one another across the circle at the phase angle .

The all-pass filter (47) outputs a complex-valued signal, however. To see real outputs, we must handle the negative frequencies in the same way as the positive ones. The filter (47) should be multiplied by another like itself but with replaced by ; i.e., with Zr replaced by .The result of this procedure is shown in Figure 14.

allpass
Figure 14
All-pass filter with a complex pole-zero pair. The pole and zero are at equal logarithmic distances from the unit circle.

A general form for an all-pass filter is ,where A(Z) is an arbitrary minimum-phase filter. That this form is valid can be verified by checking that .

## EXERCISES:

1. Verify that for the general form of an all-pass filter P(Z) = .
2. Given an all-pass filter

with poles at Zp=2 and Zp=3, what are b, c, d, e, and f?

Next: Notch filter Up: Z-plane, causality, and feedback Previous: Laurent expansion
Stanford Exploration Project
10/21/1998


text:
# 19.2. Hyperparameter Optimization API¶ Open the notebook in Colab Open the notebook in Colab Open the notebook in Colab Open the notebook in Colab Open the notebook in SageMaker Studio Lab

Before we dive into the methodology, we will first discuss a basic code structure that allows us to efficiently implement various HPO algorithms. In general, all HPO algorithms considered here need to implement two decision making primitives, searching and scheduling. First, they need to sample new hyperparameter configurations, which often involves some kind of search over the configuration space. Second, for each configuration, an HPO algorithm needs to schedule its evaluation and decide how many resources to allocate for it. Once we start to evaluate a configuration, we will refer to it as a trial. We map these decisions to two classes, HPOSearcher and HPOScheduler. On top of that, we also provide a HPOTuner class that executes the optimization process.

This concept of scheduler and searcher is also implemented in popular HPO libraries, such as Syne Tune , Ray Tune or Optuna .

import time
from scipy import stats
from d2l import torch as d2l

## 19.2.1. Searcher¶

Below we define a base class for searchers, which provides a new candidate configuration through the sample_configuration function. A simple way to implement this function would be to sample configurations uniformly at random, as we did for random search in Section 19.1. More sophisticated algorithms, such as Bayesian optimization, will make these decisions based on the performance of previous trials. As a result, these algorithms are able to sample more promising candidates over time. We add the update function in order to update the history of previous trials, which can then be exploited to improve our sampling distribution.

class HPOSearcher(d2l.HyperParameters):  #@save
def sample_configuration() -> dict:
raise NotImplementedError

def update(self, config: dict, error: float, additional_info=None):
pass

The following code shows how to implement our random search optimizer from the previous section in this API. As a slight extension, we allow the user to prescribe the first configuration to be evaluated via initial_config, while subsequent ones are drawn at random.

class RandomSearcher(HPOSearcher):  #@save
def __init__(self, config_space: dict, initial_config=None):
self.save_hyperparameters()

def sample_configuration(self) -> dict:
if self.initial_config is not None:
result = self.initial_config
self.initial_config = None
else:
result = {
name: domain.rvs()
for name, domain in self.config_space.items()
}
return result

## 19.2.2. Scheduler¶

Beyond sampling configurations for new trials, we also need to decide when and for how long to run a trial. In practice, all these decisions are done by the HPOScheduler, which delegates the choice of new configurations to a HPOSearcher. The suggest method is called whenever some resource for training becomes available. Apart from invoking sample_configuration of a searcher, it may also decide upon parameters like max_epochs (i.e., how long to train the model for). The update method is called whenever a trial returns a new observation.

class HPOScheduler(d2l.HyperParameters):  #@save
def suggest(self) -> dict:
raise NotImplementedError

def update(self, config: dict, error: float, info=None):
raise NotImplementedError

To implement random search, but also other HPO algorithms, we only need a basic scheduler that schedules a new configuration every time new resources become available.

class BasicScheduler(HPOScheduler):  #@save
def __init__(self, searcher: HPOSearcher):
self.save_hyperparameters()

def suggest(self) -> dict:
return self.searcher.sample_configuration()

def update(self, config: dict, error: float, info=None):

## 19.2.3. Tuner¶

Finally, we need a component that runs the scheduler/searcher and does some book-keeping of the results. The following code implements a sequential execution of the HPO trials that evaluates one training job after the next and will serve as a basic example. We will later use Syne Tune for more scalable distributed HPO cases.

class HPOTuner(d2l.HyperParameters):  #@save
def __init__(self, scheduler: HPOScheduler, objective: callable):
self.save_hyperparameters()
# Bookeeping results for plotting
self.incumbent = None
self.incumbent_error = None
self.incumbent_trajectory = []
self.cumulative_runtime = []
self.current_runtime = 0
self.records = []

def run(self, number_of_trials):
for i in range(number_of_trials):
start_time = time.time()
config = self.scheduler.suggest()
print(f"Trial {i}: config = {config}")
error = self.objective(**config)
error = float(error.cpu().detach().numpy())
self.scheduler.update(config, error)
runtime = time.time() - start_time
self.bookkeeping(config, error, runtime)
print(f"    error = {error}, runtime = {runtime}")

## 19.2.4. Bookkeeping the Performance of HPO Algorithms¶

With any HPO algorithm, we are mostly interested in the best performing configuration (called incumbent) and its validation error after a given wall-clock time. This is why we track runtime per iteration, which includes both the time to run an evaluation (call of objective) and the time to make a decision (call of scheduler.suggest). In the sequel, we will plot cumulative_runtime against incumbent_trajectory in order to visualize the any-time performance of the HPO algorithm defined in terms of scheduler (and searcher). This allows us to quantify not only how well the configuration found by an optimizer works, but also how quickly an optimizer is able to find it.

@d2l.add_to_class(HPOTuner)  #@save
def bookkeeping(self, config: dict, error: float, runtime: float):
self.records.append({"config": config, "error": error, "runtime": runtime})
# Check if the last hyperparameter configuration performs better
# than the incumbent
if self.incumbent is None or self.incumbent_error > error:
self.incumbent = config
self.incumbent_error = error
# Add current best observed performance to the optimization trajectory
self.incumbent_trajectory.append(self.incumbent_error)
# Update runtime
self.current_runtime += runtime
self.cumulative_runtime.append(self.current_runtime)

## 19.2.5. Example: Optimizing the Hyperparameters of a Convolutional Neural Network¶

We now use our new implementation of random search to optimize the batch size and learning rate of the LeNet convolutional neural network from Section 7.6. We being by defining the objective function, which will once more be validation error.

def hpo_objective_lenet(learning_rate, batch_size, max_epochs=10):  #@save
model = d2l.LeNet(lr=learning_rate, num_classes=10)
trainer = d2l.HPOTrainer(max_epochs=max_epochs, num_gpus=1)
data = d2l.FashionMNIST(batch_size=batch_size)
trainer.fit(model=model, data=data)
validation_error = trainer.validation_error()
return validation_error

We also need to define the configuration space. Moreover, the first configuration to be evaluated is the default setting used in Section 7.6.

config_space = {
"learning_rate": stats.loguniform(1e-2, 1),
"batch_size": stats.randint(32, 256),
}
initial_config = {
"learning_rate": 0.1,
"batch_size": 128,
}

Now we can start our random search:

searcher = RandomSearcher(config_space, initial_config=initial_config)
scheduler = BasicScheduler(searcher=searcher)
tuner = HPOTuner(scheduler=scheduler, objective=hpo_objective_lenet)
tuner.run(number_of_trials=5)

    error = 0.23679041862487793, runtime = 53.025859355926514

Below we plot the optimization trajectory of the incumbent to get the any-time performance of random search:

board = d2l.ProgressBoard(xlabel="time", ylabel="error")
for time_stamp, error in zip(
tuner.cumulative_runtime, tuner.incumbent_trajectory
):
board.draw(time_stamp, error, "random search", every_n=1)

## 19.2.6. Comparing HPO Algorithms¶

Just as with training algorithms or model architectures, it is important to understand how to best compare different HPO algorithms. Each HPO run depends on two major sources of randomness: the random effects of the training process, such as random weight initialization or mini-batch ordering, and the intrinsic randomness of the HPO algorithm itself, such as the random sampling of random search. Hence, when comparing different algorithms, it is crucial to run each experiment several times and report statistics, such as mean or median, across a population of multiple repetitions of an algorithm based on different seeds of the random number generator.

To illustrate this, we compare random search (see Section 19.1.2) and Bayesian optimization on tuning the hyperparameters of a feed-forward neural network. Each algorithm was evaluated $$50$$ times with a different random seed. The solid line indicates the average performance of the incumbent across these $$50$$ repetitions and the dashed line the standard deviation. We can see that random search and Bayesian optimization perform roughly the same up to ~1000 seconds, but Bayesian optimization can make use of the past observation to identify better configurations and thus quickly outperforms random search afterwards.

Fig. 19.2.1 Example any-time performance plot to compare two algorithms A and B.

## 19.2.7. Summary¶

This section laid out a simple, yet flexible interface to implement various HPO algorithms that we will look at in this chapter. Similar interfaces can be found in popular open-source HPO frameworks. We also looked at how we can compare HPO algorithms, and potential pitfall one needs to be aware.

## 19.2.8. Exercises¶

1. The goal of this exercise is to implement the objective function for a slightly more challenging HPO problem, and to run more realistic experiments. We will use the two hidden layer MLP DropoutMLP implemented in Section 5.6.

1. Code up the objective function, which should depend on all hyperparameters of the model and batch_size. Use max_epochs=50. GPUs do not help here, so num_gpus=0. Hint: Modify hpo_objective_lenet.

2. Choose a sensible search space, where num_hiddens_1, num_hiddens_2 are integers in $$[8, 1024]$$, and dropout values lie in $$[0, 0.95]$$, while batch_size lies in $$[16, 384]$$. Provide code for config_space, using sensible distributions from scipy.stats.

3. Run random search on this example with number_of_trials=20 and plot the results. Make sure to first evaluate the default configuration of Section 5.6, which is initial_config = {'num_hiddens_1': 256, 'num_hiddens_2': 256, 'dropout_1': 0.5, 'dropout_2': 0.5, 'lr': 0.1, 'batch_size': 256}.

2. In this exercise, you will implement a new searcher (subclass of HPOSearcher) which makes decisions based on past data. It depends on parameters probab_local, num_init_random. Its sample_configuration method works as follows. For the first num_init_random calls, do the same as RandomSearcher.sample_configuration. Otherwise, with probability 1 - probab_local, do the same as RandomSearcher.sample_configuration. Otherwise, pick the configuration which attained the smallest validation error so far, select one of its hyperparameters at random, and sample its value randomly like in RandomSearcher.sample_configuration, but leave all other values the same. Return this configuration, which is identical to the best configuration so far, except in this one hyperparameter.

1. Code up this new LocalSearcher. Hint: Your searcher requires config_space as argument at construction. Feel free to use a member of type RandomSearcher. You will also have to implement the update method.

2. Re-run the experiment from the previous exercise, but using your new searcher instead of RandomSearcher. Experiment with different values for probab_local, num_init_random. However, note that a proper comparison between different HPO methods requires repeating experiments several times, and ideally considering a number of benchmark tasks.

Discussions