text:
# #014 Calculating Sparse Optical flow using Lucas Kanade method

## #014 Calculating Sparse Optical flow using Lucas Kanade method

Highlights: In this post, we will show how we can detect moving objects in a video using the Lucas Kanade method. This approach is based on tracking a set of distinctive feature points. Therefore, it is also known as a Sparse Optical Flow method. We will give a detailed theoretical understanding of the Lucas Kanade method and show how it can be implemented in Python using OpenCV.

Tutorial overview:

## 1. Understanding the Concept of Motion

Until now, we have covered many computer vision methods for object detection, object segmentation, and object tracking. However, in all these approaches one important piece of information is completely ignored. That information is the relationship between objects in two consecutive frames.

Let’s understand this using an example. Have a look at the GIF below that shows a sunrise motion. This GIF is nothing but a sequence of static frames combined together.

In examples such as above, our main objective is to capture the change that happens from one frame to another. In order to achieve that, we need to track the motion of objects across all frames, estimate their current position and then, predict their displacement in the subsequent frame.

Moreover, when we work with video sequences rather than static images, instead of using just space coordinates $$x$$, and $$y$$, we will also have to track a change of intensity of a pixel over time. Therefore, we will have one additional variable – time. This means that the intensity of a single-pixel can be represented as a function of space coordinates $$x$$, $$y$$, and time $$t$$.

This approach is popularly known as Optical Flow. Let’s understand this better along with the various categorizations of Optical Flow.

## 2. Optical Flow and its types

Optical Flow can be defined as a pattern of motion of pixels between two consecutive frames. The motion can be caused either by the movement of a scene or by the movement of the camera.

A vital ingredient in several computer vision and machine learning fields such as object tracking, object recognition, movement detection, and robot navigation, Optical Flow works by describing a dense vector field. In this field, each pixel is assigned a separate displacement vector that helps in estimating the direction and speed of each pixel of the moving object, in each frame of the input video sequence.

If we were to categorize the technique of Optical Flow, we can divide it into two main types: Sparse Optical Flow and Dense Optical Flow.

1. Sparse Optical Flow: This method processes the flow vectors of only a few of the most interesting pixels from the entire image, within a frame.
2. Dense Optical Flow: Here, the flow vectors of all pixels in the entire frame are processed which makes this technique a little slower.

Have a look at the two GIF images below. The image on the left shows Sparse Optical Flow in action and the image on the right shows Dense Optical Flow.

As you must have realized by now, that tracking motion of objects from one sequence to another is a complicated problem due to the sheer volume of pixels in each frame. In the following paragraphs, we will give the necessary theoretical concepts, and finally, we will derive the equations for Lucas Kanade optical flow method.

## 3. Optical Flow Constraint

In the Lucas Kanade method, an important assumption was made, that there isn’t any significant change in the lighting between two consecutive frames. This assumption is called the Brightness Constancy Assumption. This means that if the object in the image moves or the camera moves, then, the colors of that object will remain the same, regardless of the lighting.

Brightness constancy constraint: Let’s assume that a pixel is moving in the direction $$(u, v)$$. That is $$u$$ is the amount of movement in $$x$$ direction, and $$v$$ is the amount of movement in $$y$$ direction when we get to $$t+1$$. Here, $$t$$ represents the time instance of the first frame where the consecutive frame is represented as $$t+1$$.

The brightness constancy constraint equation can be written as follows:

$$I(x, y, t) = I(x+u, y+v, t+1)$$

In this equation, $$I(x, y, t)$$ represents the pixel intensity at time $$t$$ at location $$(x, y)$$. The Brightness Constancy Assumption states that the intensity at $$t+1$$ at location $$I(x+u, y+v)$$ is going to be the same as in the frame $$t$$. Here, $$u$$ and $$v$$ are displacements for wich the poin has mooved in $$x$$ and $$y$$ direction.

This can also be rewritten as:

$$0 = I(x+u, y+v, t+1) – I(x, y, t)$$

Small Motion: When a pixel moves between two consecutive frames we assume that a movement is relatively small. We can then use the Taylor expansion in order to approximate this equation:

$$0 \approx I(x, y, t+1)+I_{x} u+I_{y} v-I(x, y, t)$$

Here, we are substituting the value $$I(x+u, y+v, t+1)$$ with the Taylor expansion. So, we have the $$I(x,y,t+1)$$ plus the derivative part $$I_{x}u + I_{y}v$$. Note that $$I_{x}u$$ is the derivative in the $$x$$-direction, and $$I_{y}v$$ is the derivative in the $$y$$-direction.

In addition, $$I_{x} = \frac{\partial I}{x}$$ and $$I_{y} = \frac{\partial I}{y}$$ for both $$t$$ and $$t+1$$. Here, we are going to assume that the things are changing slowly, so the derivative at a particular point is going to be the same both at $$t$$ and $$t+1$$.

$$0 \approx [I(x,y,t+1) – I(x, y, t)]+ I_{x}u + I_{y}v$$

Now, when we rearrange equation terms:

$$0 \approx I_{t} + I_{x}u + I_{y}v$$

This $$I_{t}$$, is the difference between $$I(x,y,t+1) – I(x, y, t)$$. So $$I_{t}$$ is called the temporal derivative. In addition, $$I_{x}$$ is the derivative of $$I$$ in the $$x$$-direction and $$I_{y}$$ is the derivative of $$I$$ in the $$y$$-direction. Next, $$I_{t}$$ is the derivative of $$I$$ with respect to time. Our video is a function $$I(x,y,t)$$, so a derivative can be taken with respect to $$x$$, $$y$$, and $$t$$.

$$0 \approx I_{t} + \bigtriangledown I \cdot [u, v]$$

Here $$\bigtriangledown I \cdot [u, v]$$ is the gradient of the image, dotted with the vector $$[u, v]$$. We talked about Image Gradient before and you can check it out.

Finally, the brightness constancy constraint equation can be written as:

$$I_{x}u + I_{y}v + I_{t} = 0$$

This is an equation with two unknowns and as such cannot be solved. This is known as the aperture problem of optical flow algorithms. To find the optical flow another set of equations is needed to impose an additional constraint.

$$I_{x}u + I_{y}v = – I_{t}$$

Note that this can be written as a single vector equation:

$$\vec{\bigtriangledown}I \cdot \vec{u} = -I_{t}$$

where:

$$\vec{\bigtriangledown}I = \begin{bmatrix} I_{x}\\ I_{y} \end{bmatrix}$$, and $$\vec{u} = \begin{bmatrix} u\\ v \end{bmatrix}$$

## 4. Gradient Component of Flow

In the last paragraph we get to this equation, which is the brightness constancy constraint equation:

$$I_{x}u+I_{y}v+I_{t}= 0$$

A question is how many unknowns and how many equations per pixel do we have? Here, we have two unknowns $$u$$ and $$v$$ but only one equation per pixel.

The component of $$\left ( u,v \right )$$ that is in the direction of the gradient is something we can measure.

Here, we can see that this red line in the image above is in the direction of the gradient. We may suppose that we have a displacement vector $$\left ( u,v \right )$$ that needs to be determined. Also, we have a $$\left ( {u}’,{v}’ \right )$$ that is an extra component parallel to the edge. This new vector $$\left ( u+{u}’,v+{v}’ \right )$$ has the same amount perpendicular to the edge and in the direction of the gradient but a different amount along the edge. Locally we can only determine the amount of motion that is perpendicular to the edge in a local neighborhood. We can think of it as looking through a hole. That is called an aperture and this general problem is called the aperture problem.

### Aperture Problem

Now, let’s see this interesting example. It is a line with two parts. Notice that it has a corner. In the following example it is moving down and to the right:

Let us put an aperture over the line. If we can observe only the green area we will get a wrong impression that the line is moving in the direction perpendicular to the edge.

Next, if we are observing the movement of the line through a yellow area we can estimate the movement accurately.

That is the aperture problem. We can only tell the motion locally in the direction perpendicular to the edge.

### Solving the Aperture Problem

Now we are going to solve the aperture problem. To do this we have to impose additional local constraints in order to get more equations per pixel. For example, we will assume that in a local area of one pixel, the motion field is very smooth. In fact, we assume that in a small rectangular window around this pixel, the value is the same for every $$\left ( u,v \right )$$. For example, if we have a $$5\times 5$$ window, there are $$25$$ pixels in that window. Now, if we were assuming that there was one $$\left ( u,v \right )$$ for all of these the $$\left ( u,v \right )$$ for the center pixel, that would give us $$25$$ equations per pixel. Here they are:

$$0= I_{t}\left ( p_{i} \right )+\bigtriangledown I\left ( p_{i} \right )\cdot \begin{bmatrix}u & v \end{bmatrix}$$

$$\begin{bmatrix}I_{x}\left ( p_{1} \right ) & I_{y}\left ( p_{1} \right )\\ I_{x}\left ( p_{2} \right )& I_{y}\left ( p_{2} \right )\\\vdots & \vdots \\I_{x}\left ( p_{25} \right ) & I_{y}\left ( p_{25} \right )\end{bmatrix}\begin{bmatrix}u\\v\end{bmatrix}= -\begin{bmatrix}I_{t}\left ( p_{1} \right )\\I_{t}\left ( p_{2} \right )\\\vdots \\I_{t}\left ( p_{25} \right )\end{bmatrix}$$

So we have the gradients dotted with $$\begin{bmatrix}u\\v\end{bmatrix}$$ and that equals the negative of the temporal derivatives at each of those points. We can write this as:

$$Ad= b$$

where $$d$$ is this displacement vector $$\begin{bmatrix}u\\v\end{bmatrix}$$ and $$b$$ is just this $$25\times 1$$ vector that is essentially the negative of all the temporal derivatives. So we have $$25$$ equations and $$2$$ unknowns.

The question is how do we solve a system when we have more equations than unknowns? Well, we will apply the least-squares approach and in that way, we will minimize the squared difference.

$$Ad= b\rightarrow minimize\left \| Ad-b \right \|^{2}$$

$$\left ( A^{T}A \right )d= A^{T}b$$

The way we do that is by using the standard pseudo-inverse method. So, we multiply $$A$$ by $$A^{T}$$ and we end up with this equation:

$$\begin{bmatrix}\sum I_{x}I_{x} &\sum I_{x}I_{y} \\ \sum I_{x}I_{y}& \sum I_{y}I_{y}\end{bmatrix}\begin{bmatrix}u\\ v\end{bmatrix}= -\begin{bmatrix}\sum I_{x}I_{t}\\\sum I_{y}I_{t}\end{bmatrix}$$

These sums are calculated over the $$5 \times5$$ kernel window. This technique was first proposed by Bruce D. Lucas and Takeo Kanade way back in 1981.

Now, let’s first illustrate and visualize this solving method.

$$I_{x}u+I_{y}v+I_{t}= 0$$

$$\bigtriangledown I\cdot \vec{U}+I_{t}= 0$$

The idea is if we have a gradient in some direction (red arrows in the picture above) any $$\left ( u,v \right )$$ that’s along this blue line would be an acceptable solution.

### Combining Local Constraints

If we have a particular gradient in the $$\left ( u,v \right )$$ space, that gives us a single line. In the image below we can have a green line for the gradient vector 1. Next, we can have another gradient that is present in the same kernel window (5×5). For instance, it can be a gradient 2 – blue line. Moreover, we can have another gradient 3 that we connect with the red line. So, a solution for (u, v) should lie on these lines and it will be at the point of their intersection. This is illustrated in the image below.

### RGB Version

If we are actually working with $$RGB$$ images, we would have $$75$$ instead of $$25$$ equations. That is, we have $$5\times 5\times 3$$, where 3 is the number of channels.

$$0= I_{t}\left ( p_{i} \right )\left [ 0,1,2 \right ]+\bigtriangledown I\left ( p_{i} \right )\left [ 0,1,2 \right ]\cdot \left [ u,v \right ]$$

$$\begin{bmatrix}I_{x}\left ( p_{1} \right )\left [ 0 \right ]& I_{y}\left ( p_{1} \right )\left [ 0 \right ]\\ I_{x}\left ( p_{1} \right )\left [ 1 \right ]&I_{y}\left ( p_{1} \right )\left [ 1 \right ] \\ I_{x}\left ( p_{1} \right )\left [ 2 \right ]&I_{y}\left ( p_{1} \right )\left [ 2 \right ] \\\vdots & \vdots \\ I_{x}\left ( p_{25} \right )\left [ 0 \right ] &I_{y}\left ( p_{25} \right )\left [ 0 \right ] \\I_{x}\left ( p_{25} \right )\left [ 1 \right ] & I_{y}\left ( p_{25} \right )\left [ 1 \right ]\\ I_{x}\left ( p_{25} \right )\left [ 2 \right ] & I_{y}\left ( p_{25} \right )\left [ 2 \right ]\end{bmatrix}\begin{bmatrix}u\\ v\end{bmatrix}= \begin{bmatrix}I_{t}\left ( p_{1} \right )\left [ 0 \right ]\\I_{t}\left ( p_{1} \right )\left [ 1 \right ]\\I_{t}\left ( p_{1} \right )\left [ 2 \right ]\\\vdots \\I_{t}\left ( p_{25} \right )\left [ 0 \right ]\\I_{t}\left ( p_{25} \right )\left [ 1 \right ]\\I_{t}\left ( p_{25} \right )\left [ 2 \right ]\end{bmatrix}$$

We might say that our window was only a single pixel and then we had one equation and two unknowns but with $$RGB$$ we now have three equations and two unknowns. Well, we can’t solve it. The problem is that the $$RGB$$ images are quite correlated so we can’t just use the different color planes in order to solve it.

## 5. Lucas Kanade in Python

Now, after a lengthy theoretical overview, it is a perfect time to start with the code. We will show how to use Lucas Kanade using OpenCV in Python.

First, we will import the necessary libraries.

import cv2
import numpy as np

# params for ShiTomasi corner detection
feature_params = dict( maxCorners = 100,
qualityLevel = 0.3,
minDistance = 7,
blockSize = 7 )

# Parameters for lucas kanade optical flow
lk_params = dict( winSize  = (15,15),
maxLevel = 3,
criteria = (cv2.TERM_CRITERIA_EPS | cv2.TERM_CRITERIA_COUNT, 10, 0.03))

As the first step, we will need to detect feature points. We will detect them in the initial frame (prev), that is, in the grayscale image (prevgray – first frame of the video transformed to a grayscale image). To do this, we will use a function called cv2.goodFeaturesToTrack(). It is an implementation of the Shi-Tomasi corner detector (an extension of the Harris corner detector). A nice property of this function is that we can specify a maximal number of feature points that we want to detect and track. Here, we will detect a maximum of 100 points.

We can visualize them in the following image.

cap = cv2.VideoCapture('cars.mp4')

# Take first frame and find corners in it
fourcc = cv2.VideoWriter_fourcc('M','J','P','G')
out = cv2.VideoWriter('output.avi', fourcc, 29, (1280, 720))
prevgray = cv2.cvtColor(prev, cv2.COLOR_BGR2GRAY)
p0 = cv2.goodFeaturesToTrack(prevgray, mask = None, **feature_params)

# Create a mask image for drawing purposes

The next step is to use these points (p0), feed them to Lucas Kanade algorithm and track them (p1).

The function Lucas Kanade is implemented as cv2.calcOpticalFlowPyrLK(). It calculates an optical flow for a sparse feature set using the iterative Lucas-Kanade method with the pyramid. It uses the following parameters:

Parameters for the function cv2.calcOpticalFlowPyrLK(prevImg, nextImg, prevPts, nextPts):

• prevImg – The first 8-bit input image.
• nextImg – Second input image of the same size and the same type as prevImg.
• prevPts – Vector of 2D points for which the flow needs to be found.
• winSize – The size of the search window at each pyramid level.
• maxLevel – 0-based maximal pyramid level number; if set to 0, pyramids are not used (single-level). On the other hand, if set to 1, two levels are used. If pyramids are passed to input then the algorithm will use as many levels as pyramids have but no more than maxLevel.
• criteria – parameter, specifying the termination criteria of the iterative search algorithm.

Return:

• nextPts – Output vector of 2D points containing the calculated new positions of input features in the second image.
• status – Output status vector. Each element of the vector is set to 1 if the flow for the corresponding features has been found. Otherwise, it is set to 0.
• err – Status output vector of errors. Each element of the vector is set to an error for the corresponding feature. If the flow wasn’t found then the error is not defined (use the status parameter to find such cases).

This function accepts two grayscale images: prev and next. The set of detected data points are stored in the p0. Using indexing we can access the data points and check their shape.

# Note the shape of the p0 variable and how we can access the data points
print(p0.shape)
print(p0[0][0][0])
print(p0[0][0][1])

Output:

(100, 1, 2)

981.0

390.0

The goal of the function is to return the coordinates of the initial feature points that are detected and tracked in the subsequent image p1 within the next image frame.

while (cap.isOpened()):

if ret == True:

gray = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY)

# calculate optical flow
p1, st, err = cv2.calcOpticalFlowPyrLK(prevgray, gray, p0, None, **lk_params)

# Select good points
good_new = p1[st==1]
good_old = p0[st==1]
# drawing
for i,(new,old) in enumerate(zip(good_new,good_old)):
a,b = new.ravel()
c,d = old.ravel()
frame = cv2.circle(frame,(a,b),5, (0,0,255),-1)

#cv2_imshow(img)

# Now update the previous frame and previous points
prevgray = gray.copy()
p0 = good_new.reshape(-1,1,2)

out.write(img)
else:
break

out.release()
cap.release()

The image/video quality and the distinctiveness of the feature points will determine the accuracy of the tracking.

In case that we have a noisy video and feature points that are not distinctive (e.g. “not clear corners”), the LK algorithm can easily fail, so do not be surprised if that happens.

The final practical step of this experiment is to loop over the whole video and to iteratively call LK algorithm. In addition, it will be necessary to update a set of the tracked points. This is done within the statement p0 = good_new.reshape(-1,1,2) where we additionally adjust the shape of this array.

The other parts of the code are mainly used for visualizations. You can figure out on your own how we managed to add tracked points onto the final output video (e.g. dummy image mask)

At the end, we will visualize this process over the whole video sequence.

The connected points show the “movement of the car”. On the other hand, there are other detected points that are static. The LK detects that there are no displacements for these points.

## Summary

In this post, we explained how to apply the Lucas Kanade method to detect moving objects in a video. It is a commonly used differential method for optical flow estimation. This method assumes that the flow is a constant in a local neighbourhood of the pixel and solves the basic optical flow equations for all the pixels in that neighbourhood.

### References:

[1] Introduction to Motion Estimation with Optical Flow by Chuan-en Lin


text:
blog

# Fine-tuned LLMs and Distributed Training to elevate your Conversational AI game

Fri, Jan 27, 2023

Large Language Models (LLMs) are powerful tools in the field of artificial intelligence that can understand and respond to natural language. Recently, LLMs like GPT-3, OPT, or T5 have stolen the spotlight on AI. These huge deep learning models, which consist of billions of parameters, perform astonishingly well for an extensive set of natural language processing tasks, including text generation, summarization, translation, and many more. A great example of the flexibility and power of LLMs is the recently released ChatGPT, which can produce astounding human-like text responses for a wide range of prompts.

While these large models are great for general tasks, they may need to be fine-tuned to achieve optimal performance on specific downstream tasks or when dealing with new, unseen data. Fine-tuning is when a model's parameters are adjusted to fit a particular dataset better. This can help companies use the model for tasks specific to their business.

As a treat to our amazing readers, we fine-tuned an LLM to build a chatbot that can answer natural questions about the rich content published on our blog. This article will walk you through the fine-tuning process, from building our own dataset to optimizing inference time for the fine-tuned model!

## Say Hi!

Before diving into the details of our fine-tuning pipeline, we invite you to try out our chatbot for yourself! We’ve set up a 🤗 Hugging Face Space where you can ask the chatbot any questions you have about this blog post. Simply follow this link to access the space and start chatting! In addition, we’ve uploaded the fine-tuned model and its ONNX export to 🤗 Hugging Face so that you can explore them at will.

The model powering the chatbot was trained on the task of Conversational Question Answering, which means it can answer questions regarding a specific context (in this case, the content of this blog) or previous questions or answers from the current conversation thread. Try chatting with the bot in a conversational style, just as you would with one of Tryolabs’ tech experts!

### Caveats

• Remember that this is just a small demo, so the answers may not be as accurate as expected; in the Improvements section, we’ll discuss how we can enhance the model’s responses! Also, the content of this blog was not included in the training set, which means that the chatbot will give you answers about new, unseen data!
• Response time may take between 10 to 20 seconds due to the use of 🤗 Hugging Face’s free-tier space, which only has access to two CPU cores. This response time is slow for a chatbot being used in production, but it's fast for a CPU deployment and for such large inputs (since the model needs to process the entire blog to generate an answer). We'll discuss optimizing inference time in the Optimizing with ONNX section.

## The Boom of Foundation Models

Have you ever wondered how computers can understand and respond to human language? The answer lies in a new concept called ‘Foundation Models’. Popularized under this name by the Stanford University, these are machine learning models trained on immense amounts of data (over tens of terabytes, and growing) that can be adapted to a wide range of downstream tasks in fields such as image, text, and audio, among others.

LLMs, a type of Foundation Model, are particularly well-established in Natural Language Processing (NLP). These models are cutting-edge artificial intelligence, capable of producing human-like language with remarkable accuracy. They can be used to generate text for various tasks such as translation, summarization, paraphrasing, question answering, and even assisted coding.

These models come in different flavors and are often open-source. They can vary in size, the tasks they were pre-trained on, efficiency, and other characteristics. For example, the smallest LLMs have only a few million parameters, while the largest ones, such as the recently released Switch Transformers, have over a trillion.

Some of the most widely adopted LLMs are:

• BLOOM, developed by BigScience Workshop
• GPT-J, the open-source version of GPT-3 developed by OpenAI
• OPT, developed by Meta

A comprehensive list of open-source language models can be found on 🤗 Hugging Face’s list of supported models. Thanks to 🤗 Hugging Face and the ML community for providing this huge open-source repository!

One recent example of the impressive capabilities of Foundation Models is ChatGPT, arguably one of the most incredible advances in AI history. This model, developed by OpenAI, is a fine-tuned version of GPT-3.5 (one of the latest versions of the GPT-3 model family). ChatGPT can be used through a simple chat interface to perform various tasks, including summarization, text generation, code generation, and question-answering on virtually any topic. What sets ChatGPT apart is its ability to produce highly detailed, complete, and human-like responses, admit mistakes and adjust replies based on the user's needs.

As the name suggests, Foundation Models can serve as the foundation for many applications, but they require fine-tuning and adjustments to get the most out of them. So keep reading to learn how to get them to their full potential!

## Fine-tuning an LLM

### 1. Building a Dataset

There is a wide range of public datasets that you can use to fine-tune your model, but if you desire to improve the results for your specific task, you will probably need to build your own dataset. This might be a crucial task to achieve good results, albeit time-consuming.

Our goal was to build a chatbot that could answer questions about Tryolabs’ blog posts, so we created our own custom dataset, TryoCoQA, to fine-tune a Foundation Model that can interact with Tryolabs’ readers, just like yourself!

Like the CoQA dataset for conversational question answering, TryoCoQA consists of questions and answers about a specific context in a conversational manner, with some questions and answers referencing previous points in the conversation. We aimed for natural language questions with a variety of writing styles and vocabulary, and answers that can be short spans of text extracted from the context or free-form text, hoping for the model to produce more human-like responses with high-quality content.

The dataset and guidelines for building it are available in the following GitHub repository.

### 2. Choosing a Foundation Model

Selecting the right open-source LLM to fine-tune can be a tough choice. There’s a handful of them, and while they may perform quite well for a broad range of general tasks, it can be challenging to predict how well they will perform on our specific task before fine-tuning. Think of it like buying a new pair of dancing shoes - they may look great and feel comfortable, but you won't know how well they'll perform until you hit the dance floor.

In addition to wanting the model to perform well on our specific task, we also wanted to consider other factors, such as resource efficiency and the size of the dataset required for fine-tuning. We were looking for a model that could run on minimal resources and be fine-tuned with a small dataset.

Given our goal of building a QA chatbot for our blog posts and the constraints we have outlined, we zeroed in on T5 and its variants as a promising choice. T5 stands for “Text-To-Text Transfer Transformer.” Its philosophy is that it models every NLP task as a text-to-text problem. For example, in the task of Document Classification, T5 outputs a simple text containing the name of the predicted class for the document rather than outputting logits for all possible classes. In addition to this creative approach to NLP problems, we also liked that T5’s architecture is similar to the original transformer encoder-decoder architecture proposed in the ‘Attention Is All You Need’ paper.

One variant of T5 that stood out was FlanT5. It’s been fine-tuned on a wide range of downstream tasks and over 450 datasets, and it even performs well on zero-shot tasks, meaning it can obtain good results for a new task or dataset without training on it. Just what we needed! With a minimal dataset, one could fine-tune FlanT5 for a few epochs and obtain excellent results.

Of course, ML is not always that simple: our use case required processing whole blog posts, which can be very long. T5 and FlanT5 both use the popular self-attention mechanism, which has a quadratic increase in memory consumption with input size! In other words, to process a whole blog post — or worse, a batch of them — we would need an astronomical amount of memory.

Fortunately, another variant of T5, called LongT5, saved the day! LongT5, proposed by Google, is especially designed to process large inputs. It uses a different attention mechanism called TGlobal (Transient Global) Attention Mechanism, which requires far less memory and allows LongT5 to excel at numerous tasks that other transformer architectures can’t handle due to memory shortage, such as scientific paper summarization or QA about Wikipedia articles.

So LongT5 seemed like the right choice for efficient training and inference on our dataset, but it did pose a small problem. In contrast with FlanT5, LongT5’s available checkpoints weren’t fine-tuned on many tasks, so it didn’t perform very well on zero-shot scenarios. To address this, we fine-tuned LongT5 on a few publicly available datasets before training on our own data!

In summary

As you can see, selecting which model to train for your particular problem can be challenging as it generally involves many factors. So always try to consider the following:

• How well the model fits your specific task. You can dig deeper into the datasets and functions it was pre-trained on and do some zero-shot or few-shot rounds of evaluation on your own tasks and data.
• The size of your inputs and outputs. Some models may not scale well for large inputs and outputs due to high memory consumption or a substantial number of operations.
• The size of your dataset. If you have a small dataset, choose a more powerful model capable of zero-shot or few-shot learning. Nevertheless, the more data you have, the better results you will achieve.
• How much computing power is available for training and inference. This can be a significant factor in determining which models you can use, as larger models may not fit in your memory, or training may become painfully slow. You can use libraries like 🤗 Accelerate for distributed training to make the most out of your hardware.

### 3. Fine-tuning strategy

Once we selected the perfect Foundation Model, the next step was to prepare our data to be able to train on it.

One of the challenges we faced was that our dataset was relatively small, which could make it harder for the model to learn how to converse and answer questions about our blog posts.

But we had a plan! To give our model a head start, we first fine-tuned it on much larger and more general datasets. This way, the model was able to learn how to retrieve answers to general questions before focusing on the specific content of our blog posts.

We selected two available datasets, SQuAD2.0 and CoQA, and trained on them following two different schemes:

1. Fine-tuning the model sequentially on each dataset, which means fine-tuning first on the SQuAD2.0 dataset, then on CoQA, and finally, on our dataset.
2. Combining the datasets SQuAD2.0 and CoQA into one single dataset and fine-tuning on it, and when the training is over, fine-tuning sequentially on our dataset.

Combining the datasets resulted in slightly better performance, but both alternatives produced similar results.

In addition to deciding how to combine the datasets, we also needed to adapt our examples to T5's text-to-text input and output format. This involved restructuring and rewriting the context and questions in our inputs.

To refresh the reader’s memory, in the use-case of Conversational Question Answering, the goal of the model is to generate the answer to a question given a context and the previous questions and answers from the conversation. With this in mind, we formatted the inputs following this structure:

Here, the input is a text string containing the context (i.e., the content of one of Tryolabs blog posts) followed by the last two question-and-answer pairs in the conversation and the current target question, with the target output being the answer to the target question. We chose to add just the last two question-and-answer pairs to limit the amount of conversation history the model needs to pay attention to while still being able to generate coherent responses. Note that this is a hyper-parameter you can adjust when fine-tuning your own model.

With our data prepared and fine-tuning strategy determined, the final step was setting up our infrastructure environment and training the model.

### 4. 🤗 Accelerate

Fine-tuning a big Foundation Model can be computationally expensive, especially if you want to do it quickly. However, we can still train models with limited resources. There are various techniques to accommodate large models in small environments.

In our case, we used 2 x NVIDIA GeForce RTX 3090 GPUs, which had a total of 48GB VRAM. Although this setup seems to have excellent computing power and memory capacity, it was not enough to train the model independently. To accomplish the task, we had to use different techniques supported by 🤗 Hugging Face’s distributed training and inference library, 🤗 Accelerate.

The techniques that worked for us were:

• Using gradient accumulation, which lets you train on bigger batch sizes as the gradients get accumulated over several batches, and the optimization step is calculated after a certain number of them.
• Using gradient checkpointing to reduce memory consumption by forgetting the activations during the forward pass and recomputing them on the backward pass of each training round.
• Picking the right batch size to balance training speed and memory consumption.
• Choosing optimizers that consume less memory, such as Adafactor (the optimizer used in the original T5 and LongT5 papers).
• Tweaking parameters in the data loader, such as pinning the memory to the CPU and setting the right number of workers.
• Distributing the training across both GPUs to leverage the computing power available.

You can find more information on these techniques and how to use them in HuggingFace’s documentation, particularly in the “Efficient Training on a Single GPU” and “Efficient Training on Multiple GPUs” sections, as well as in 🤗 Accelerate’s documentation.

### 5. Evaluation

Apart from training the model, we wanted to evaluate what it was doing and how well it was performing.

Firstly, to correctly evaluate the training, we had to take a portion of the data to use as a validation split. Thankfully SQuAD2.0 and CoQA datasets already have a validation split. In the case of our dataset, we split our data into 85% training and 15% validation.

To assess its performance, we used the F1 Score by validating how many tokens appeared in common in both predictions and ground truth samples. We also used Exact match to see if the model was actually writing the same answer.

Since we had two different training steps, we also had two additional evaluation steps. The first training, on SQuAD2.0 and CoQa, resulted in a 74.29 F1 Score on the validation split after 3 epochs. The second training, on TryoCoQa, produced a 54.77 F1 Score after 166 epochs.

More than analyzing the quantitative metrics is required to evaluate these results and conversational models in general. It is essential to consider the qualitative aspect of the model's answers, like their grammatical correctness and coherence within the conversation context. Sometimes it is preferable to have better answers (qualitatively speaking) than a better F1. So we looked at some answers from the validation set to ensure that the model was correctly generating what we were looking for. Our analysis revealed that higher F1 scores were generally associated with greater-quality answers. As a result, we selected the checkpoint with the highest F1 score to use in constructing our demonstration chatbot.

If you want to play around with our fine-tuned model, you can find it on 🤗 Hugging Face with the ID tryolabs/long-t5-tglobal-base-blogpost-cqa!

## Faster inference with 🤗 Optimum and ONNX

After fine-tuning our model, we wanted to make it available to our awesome readers, so we deployed it on 🤗 Hugging Face Spaces, which offers a free tier with two CPU cores for running inference on the model. However, this setup can lead to slow inference times, and processing significant inputs like ours doesn’t make it any better. And a chatbot that takes a few minutes to answer a question doesn't strike anyone as being particularly chatty, does it? So, to improve the speed of our chatbot, we turned to 🤗 Optimum and the ONNX Runtime!

In our previous blog post, A guide to optimizing Transformer-based models for faster inference, we used 🤗 Optimum and ONNX to achieve an 8x speed-up on inference for a Transformer model. Be sure to check it out!

Using 🤗 Optimum’s recently released exporters feature, we were able to convert our PyTorch model to the ONNX format. This feature is handy for encoder-decoder models like the LongT5 model we trained, as it exports the three main components separately: the encoder, the decoder with the Language Modeling head, and the same decoder with pre-computed hidden states as additional inputs. According to 🤗 Optimum’s documentation, combining these three components can speed up sequential decoding, which results in faster text generation.

Our fine-tuned model, exported to ONNX into these three components, is also available on 🤗 Hugging Face with the ID tryolabs/long-t5-tglobal-base-blogpost-cqa-onnx!

Once our model was exported to ONNX, we used 🤗 Optimum’s integration with the ONNX Runtime to optimize our model and run inference on it by using the ORTModelForSeq2SeqLM class. This class can optimize and downcast the model using ONNX’s tools and then use ONNX Runtime to run inference with this new, faster model! You can even take it one step further and quantize the model for even shorter inference time on CPU and lower memory consumption.

With these improvements, we achieved a 2x speed-up on inference time! Although the model still takes between 10 to 20 seconds to answer, this is a reasonable speed for a CPU-only deployment and processing such large inputs.

Average inference time measured over various blogposts.

It’s worth noting that members of the ONNX community are actively working on tools for exporting and optimizing the latest ML architectures. The features mentioned in this section are fresh from the oven, thanks to the invaluable support of the ONNX team. Their work is crucial for unifying deep learning frameworks and optimizing models for faster and more cost-effective training and inference.

## Improvements

We’re just scratching the surface of what’s possible. There are numerous potential improvements to keep working on to enhance the user's overall experience and the chatbot's performance. Here are some ideas to keep working on:

• Fine-tune on more public datasets for different downstream tasks. By doing so, we hope that the model learns to respond in a more human-like manner. For example, we could fine-tune on context-free QA datasets or on free-form answers so that the model not only retrieves the answers from the context but also generates original answers. We could also fine-tune on summarizing or paraphrasing tasks so that the user can also ask the chatbot to rewrite certain parts of the blog or summarize entire sections!
• Increase the size of our dataset. We built a small dataset for this demo, so it's not surprising that the model doesn't generalize well to new unseen blogs. We could potentially train a more accurate model by providing it with more training data.
• Optimize training using ONNX Runtime. We could achieve better results in the same amount of time if we could train for more epochs or fit a larger version of LongT5 in the same amount of memory. To do this, we could leverage the optimization power of ONNX Runtime for training PyTorch models, which would allow us to accelerate training speeds and optimize memory usage. Thanks to the recently released 🤗 Optimum integration with ONNX Runtime for training, this can be done in just a few lines of code!

## Takeaways

With the ever-increasing popularity of LLMs, it can seem almost impossible to train these models without having access to millions of dollars in resources and tons of data. However, with the right skills and knowledge about Foundation Models, Deep Learning, and the Transformer architecture, we showed you that fine-tuning these huge models is possible, even with few resources and a small dataset!

Fine-tuning is the key to unlocking the full potential of Foundation Models for your business. It allows you to take a pre-trained model and adapt it to your specific needs without breaking the bank.

And the best part? We're here to help you every step of the way. If you're ready to see how fine-tuning can benefit your business, don't hesitate to reach out, and let's get started on your fine-tuning journey today!

Services
Resources
Company

format: plain


text:
# Newton's Algorithm for Implied Volatility

I was studying the implied volatility for European Vanilla Call option. My notes said that we can apply Newton's algorithm to calculate implied volatility numerically. I understand how the algorithm works and the updating part is straightforward. However, I am confused by the initial guess of $$\sigma$$: $$\sigma_0 = \sqrt{\frac{2\log(S_te^{r(T-t)}/K)}{T}}.$$ I don't understand why I have to choose the initial guess like this. Does a random guessed number affect the convergence of the algorithm?

• You need to start with a reasonable approximation to the vol. There are many "approximate call pricing" formulas available, that can be inverted to give an "approximate vol" formula, see for example here quant.stackexchange.com/questions/1150/… Oct 13, 2020 at 8:50

If you think of the red line as being the price of your option minus the observed market price against the implied vol, you'll see that no matter which initial guess you choose (as long as it's above $$0$$), you'll home in to the true value very quickly.
Given this, your initial guess above corresponds to $$d_- = 0$$, but you could just as easily choose an initial guess that makes $$d_+ = 0$$: \begin{align} \sigma_0 = \sqrt{{\frac {2 \log{{\frac K {S_t e^{r(T-t)}}}}} {T}}} \end{align} or almost any other value...


text:
# ITEM:CONSENT CALENDAR

3.         AUTHORIZE FUNDS FOR 2004 SEASIDE BASIN INJECTION TESTING PROGRAM

## Meeting Date:December 15, 2003Budgeted:Yes

Program/Line No.:  1.2 Water Supply

Staff Contact:            Joe Oliver                               Projects, Objective 1-2-1 A. 1

Cost Estimate: $77,500 General Counsel Approval: N/A Committee Recommendation: The Administrative Committee reviewed this item at its December 9, 2003 meeting and recommended approval. CEQA Compliance: N/A SUMMARY: The Board will consider whether or not to amend an existing contract with Padre Associates, Inc. to assist staff with implementation of the planned Water Year (WY) 2004 Seaside Basin ground water injection testing program (also know as aquifer storage and recovery, or ASR). Specifically, this authorization will allow for a continuation of the injection testing at the District’s Santa Margarita Test Injection Well (SMTIW), located on former Fort Ord adjacent to General Jim Moore Boulevard. The focus of injection testing during the previous two seasons at the SMTIW has been on evaluation of injection well hydraulics and the basin’s response to injection. While these remain important issues, the focus of the WY 2004 testing will be primarily on issues of water quality. A detailed description of the planned WY 2004 testing and monitoring activities is provided in Exhibit 3-A. It should be noted that the total cost estimate for work that is desired to be undertaken during WY 2004 is approximately$104,000, which exceeds the $78,000 (including contingencies) that was approved for the Fiscal Year (FY) 2003-2004 District Budget. To remain within the budgeted amount, several work tasks were removed and are shown as optional tasks. These tasks would only be undertaken if alternate funding sources are identified and become available, subject to separate future authorization from the Board. RECOMMENDATION: Staff recommends that the Board authorize the General Manager to amend the Padre contract for assistance in conducting WY 2004 ASR testing in an amount not-to-exceed$77,484.  At its December 9, 2003 meeting, the Administrative Committee voted 2 to 0 to recommend that approval.

BACKGROUND AND DISCUSSION:  The SMTIW was installed in 2001 and improvements to the Cal-Am system to deliver injection water to the well were completed in 2002.  The amount of water injected during testing in WY 2002 and 2003 totaled 343 acre-feet (AF) at this facility.  In August 2003, the California Department of Health Services (CDHS) issued approval to recover the injected water back into the Cal-Am distribution system for delivery to users on the Monterey Peninsula.  Recovery testing commenced on September 3, 2003 and ended on November 4, 2003.  A total of approximately 440 AF was recovered from the SMTIW during this period, which is about 130% of the volume injected since the well was completed.  Extensive water quality sampling was conducted during both injection and recovery phases during WY 2003, as a means to better evaluate recovery efficiency, chemical interactions with the native ground water, and to respond to concerns regarding the stability and fate of disinfection by-products (DBPs) in the injected and recovered waters.  Preliminary results indicate that DBPs are present in the Carmel River system “injectate” water and DBP levels can change during aquifer storage due to the availability of DBP “precursors”, aquifer mixing/dilution and/or biodegradation.  DBP levels exhibited a general decline during recovery operations and were well below established limits.  In addition, it was found that the recovered water was a blend of the Carmel River system injectate and native ground water, and that the recovered water retained some chemical imprints of the Carmel River system water even after 100% of the injected volume was removed.  This suggests that injection in the Seaside Basin is capable of “conditioning” the aquifer even after a greater volume is removed than was injected, and that injection reduces the occurrence of hydrogen sulfide present in the native ground water, which is an ancillary benefit of the ASR program.  All water quality results from the WY 2003 recovery testing have not yet been received and reviewed.  Once received, they will be included in the summary report of the WY 2003 ASR testing results, which should be available for Board review in January 2004.

IMPACT ON STAFF/RESOURCES:  A significant staff effort has been expended planning, coordinating, and overseeing work on the District’s ASR project in the Seaside Basin.  It is planned to continue this level of effort during the WY 2004 season.  The Fiscal Year 2003-2004 Budget includes a total of $78,000 to conduct injection testing (Summary of Project Expenditures, 2003-2004 Budget, Goal No. 1, Objective 1-2-1 A. 1, Page 45). The estimated project cost for assistance from Padre for WY 2004 injection testing (with 10% contingency) is$77,484.  This cost is within the budgeted amount (i.e., \$78,000).

U:\staff\word\boardpacket\2003\2003boardpacket\20031215\ConsentCalendar\3\item3.doc


text:
g02df deletes an independent variable from a general linear regression model.

# Syntax

C#
```public static void g02df(
int ip,
double[,] q,
int indx,
out int ifail
)```
Visual Basic
```Public Shared Sub g02df ( _
ip As Integer, _
q As Double(,), _
indx As Integer, _
<OutAttribute> ByRef ifail As Integer _
)```
Visual C++
```public:
static void g02df(
int ip,
array<double,2>^ q,
int indx,
[OutAttribute] int% ifail
)```
F#
```static member g02df :
ip : int *
q : float[,] *
indx : int *
ifail : int byref -> unit
```

#### Parameters

ip
Type: System..::..Int32
On entry: $p$, the number of independent variables already in the model.
Constraint: ${\mathbf{ip}}\ge 1$.
q
Type: array<System..::..Double,2>[,](,)[,][,]
An array of size [dim1, ${\mathbf{ip}}+1$]
Note: dim1 must satisfy the constraint: $\mathrm{dim1}\ge {\mathbf{ip}}$
On entry: the results of the $QR$ decomposition as returned by methods g02da g02dc g02de (G02EEF not in this release), or previous calls to g02df.
On exit: the updated $QR$ decomposition.
indx
Type: System..::..Int32
On entry: indicates which independent variable is to be deleted from the model.
Constraint: $1\le {\mathbf{indx}}\le {\mathbf{ip}}$.
Type: System..::..Double%
On entry: the residual sum of squares for the full regression.
Constraint: ${\mathbf{rss}}\ge 0.0$.
On exit: the residual sum of squares with the (indx)th variable removed. Note that the residual sum of squares will only be valid if the regression is of full rank, otherwise the residual sum of squares should be obtained using g02dd.
ifail
Type: System..::..Int32%
On exit: ${\mathbf{ifail}}={0}$ unless the method detects an error or a warning has been flagged (see [Error Indicators and Warnings]).

# Description

When selecting a linear regression model it is sometimes useful to drop independent variables from the model and to examine the resulting sub-model. g02df updates the $QR$ decomposition used in the computation of the linear regression model. The $QR$ decomposition may come from g02da or g02de, or a previous call to g02df.
For the general linear regression model with $p$ independent variables fitted g02da or g02de compute a $QR$ decomposition of the (weighted) independent variables and form an upper triangular matrix $R$ and a vector $c$. To remove an independent variable $R$ and $c$ have to be updated. The column of $R$ corresponding to the variable to be dropped is removed and the matrix is then restored to upper triangular form by applying a series of Givens rotations. The rotations are then applied to $c$. Note only the first $p$ elements of $c$ are affected.
The method used means that while the updated values of $R$ and $c$ are computed an updated value of $Q$ from the $QR$ decomposition is not available so a call to g02de cannot be made after a call to g02df.
g02dd can be used to calculate the parameter estimates, $\stackrel{^}{\beta }$, from the information provided by g02df.

# References

Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore
Hammarling S (1985) The singular value decomposition in multivariate statistics SIGNUM Newsl. 20(3) 2–25

# Error Indicators and Warnings

Errors or warnings detected by the method:
Some error messages may refer to parameters that are dropped from this interface (LDQ) In these cases, an error in another parameter has usually caused an incorrect value to be inferred.
${\mathbf{ifail}}=1$
 On entry, ${\mathbf{ip}}<1$, or ${\mathbf{indx}}<1$, or ${\mathbf{indx}}>{\mathbf{ip}}$, or ${\mathbf{rss}}<0.0$.
${\mathbf{ifail}}=2$
 On entry, a diagonal element of $R$ is zero.
${\mathbf{ifail}}=-9000$
An error occured, see message report.
${\mathbf{ifail}}=-6000$
Invalid Parameters $〈\mathit{\text{value}}〉$
${\mathbf{ifail}}=-4000$
Invalid dimension for array $〈\mathit{\text{value}}〉$
${\mathbf{ifail}}=-8000$
Negative dimension for array $〈\mathit{\text{value}}〉$
${\mathbf{ifail}}=-6000$
Invalid Parameters $〈\mathit{\text{value}}〉$

# Accuracy

There will inevitably be some loss in accuracy in fitting a model by dropping terms from a more complex model rather than fitting it afresh using g02da.

None.


text:
# DFA for $L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$

$$L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$$

Any idea? I have problem with this kind of task.

• Have you studied the reference question and answers How to prove that a language is not regular?? – Apass.Jack Feb 11 at 22:08
• Please don't change your question in a way that invalidates existing answers. If you asked the wrong question, please ask a new question -- and take more care with future questions to avoid wasting people's time on something that wasn't what you really wanted to know about. – D.W. Feb 11 at 23:28
• Unfortunately or fortunately, the updated question is much easier. We can always choose $y$ to be the empty word. So, $L$ is the language of all words. May I rollback the question to its previous version? – Apass.Jack Feb 11 at 23:38
• @Apass.Jack yes – PoliteMan Feb 11 at 23:42

I am afraid that you cannot construct a DFA for $$L$$ since it is not regular.
Intuitively, a finite automaton cannot even make sure the number of $$a$$'s and the number of $$b$$'s are the same since its finite memory cannot keep track of the number of the $$a$$'s in the initial part of $$a^nb^n$$ when $$n$$ become sufficient large.
• Use the pumping lemma. For example, what about a word that barely satisfies the condition such as $$a^pb^{p+10}$$?
• Use Myhill–Nerode theorem. How about elements $$a^n$$ for all $$n$$? Does any of two of them belong to the same Myhill–Nerode class?
Exercise 1. Let $$\lfloor x\rfloor_a$$ be the minimum number of consecutive $$a$$'s in $$x$$ and $$\lceil x\rceil_a$$ be the maximum number of consecutive $$a$$'s in $$x$$, where $$x\in\{a,b\}^*$$ contains $$a$$. $$\lfloor x\rfloor_a=\lceil x\rceil_a=0$$ if $$x$$ does not contain $$a$$. Is the following language regular? $$L = \{x \in \{a, b\}^* \mid \lceil x\rceil_a - \lfloor x\rfloor_a \le 10 \}$$ Exercise 2. Is the following language regular? $$L = \{xy \mid x,y\in \{a,b\}^* \wedge ||x|_a - |y|_a| \leq 10 \}$$


text:
Wang Z, Zhang B, Tan DZ, Qiu JR. Ostensibly perpetual optical data storage in glass with ultra-high stability and tailored photoluminescence. Opto-Electron Adv 6, 220008 (2023). doi: 10.29026/oea.2023.220008
 Citation: Wang Z, Zhang B, Tan DZ, Qiu JR. Ostensibly perpetual optical data storage in glass with ultra-high stability and tailored photoluminescence. Opto-Electron Adv 6, 220008 (2023).

Original Article Open Access

# Ostensibly perpetual optical data storage in glass with ultra-high stability and tailored photoluminescence

• Long-term optical data storage (ODS) technology is essential to break the bottleneck of high energy consumption for information storage in the current era of big data. Here, ODS with an ultralong lifetime of 2$\text{×}$107 years is attained with single ultrafast laser pulse induced reduction of Eu3+ ions and tailoring of optical properties inside the Eu-doped aluminosilicate glasses. We demonstrate that the induced local modifications in the glass can stand against the temperature of up to 970 K and strong ultraviolet light irradiation with the power density of 100 kW/cm2. Furthermore, the active ions of Eu2+ exhibit strong and broadband emission with the full width at half maximum reaching 190 nm, and the photoluminescence (PL) is flexibly tunable in the whole visible region by regulating the alkaline earth metal ions in the glasses. The developed technology and materials will be of great significance in photonic applications such as long-term ODS.
•  Supplementary information for Ostensibly perpetual optical data storage in glass with ultra-high stability and tailored photoluminescence
###### 通讯作者: 陈斌, bchen63@163.com
• 1.

沈阳化工大学材料科学与工程学院 沈阳 110142

Figures(5)


text:
# Proper Integer Heronian Triangle whose Area is 24

## Theorem

There exists exactly one proper integer Heronian triangle whose area equals $24$.

That is, the obtuse triangle whose sides are of length $4$, $13$ and $15$.

## Proof

First we show that the $\tuple {4, 13, 15}$ triangle is actually Heronian.

Heron's Formula gives us that:

$\AA = \sqrt {s \paren {s - a} \paren {s - b} \paren {s - c} }$

where:

$\AA$ denotes the area of the triangle
$a$, $b$ and $c$ denote the lengths of the sides of the triangle
$s = \dfrac {a + b + c} 2$ denotes the semiperimeter of the triangle.

Hence:

 $\ds s$ $=$ $\ds \frac {4 + 13 + 15} 2$ $\ds$ $=$ $\ds 16$ $\ds \leadsto \ \$ $\ds \sqrt {s \paren {s - a} \paren {s - b} \paren {s - c} }$ $=$ $\ds \sqrt {16 \paren {16 - 4} \paren {16 - 13} \paren {16 - 15} }$ $\ds$ $=$ $\ds \sqrt {16 \times 12 \times 3 \times 1}$ $\ds$ $=$ $\ds \sqrt {576}$ $\ds$ $=$ $\ds 24$

It can be constructed by taking a $9-12-15$ Pythagorean triangle and removing a $5-12-13$ Pythagorean triangle from it:

Let $\tuple {a, b, c}$ be the sides of such a triangle.

Using Heron's Formula, we have:

 $\ds 24$ $=$ $\ds \sqrt {s \paren {s - a} \paren {s - b} \paren {s - c} }$ $\ds \leadsto \ \$ $\ds 576$ $=$ $\ds s \paren {s - a} \paren {s - b} \paren {s - c}$

Note that:

$\paren {s - a} + \paren {s - b} + \paren {s - c} = 3 s - a - b - c = s$

Hence by substituting $x = s - a$, $y = s - b$, $z = s - c$:

$x y z \paren {x + y + z} = 576$

Hence $s, x, y, z \in \N_{>0}$.

Without loss of generality suppose $x \le y \le z$.

Then:

 $\ds 576$ $=$ $\ds x y z \paren {x + y + z}$ $\ds$ $\ge$ $\ds x^3 \paren {3 x}$ $\ds$ $=$ $\ds 3 x^4$ $\ds \leadsto \ \$ $\ds x$ $\le$ $\ds \sqrt [4] {\frac {576} 3}$ $\ds$ $\approx$ $\ds 3.72$

so we need to check $1 \le x \le 3$.

Note that for fixed $x$:

 $\ds 576$ $=$ $\ds x y z \paren {x + y + z}$ $\ds$ $>$ $\ds x y^2 \paren {2 y}$ $\ds$ $=$ $\ds 2 x y^3$ $\ds \leadsto \ \$ $\ds y$ $\le$ $\ds \sqrt [3] {\frac {576} {2 x} }$

For $x = 1$:

$1 \le y \le \sqrt [3] {\frac {576} 2} \approx 6.60$

For $x = 2$:

$2 \le y \le \sqrt [3] {\frac {576} 4} \approx 5.24$

For $x = 3$:

$3 \le y \le \sqrt [3] {\frac {576} 6} \approx 4.58$

Finally, for fixed $x$, $y$:

 $\ds x y z \paren {x + y + z}$ $=$ $\ds 576$ $\ds \leadsto \ \$ $\ds z^2 + \paren {x + y} z - \frac {576} {x y}$ $=$ $\ds 0$ $\ds \leadsto \ \$ $\ds z$ $=$ $\ds \frac {- x - y + \sqrt {\paren {x + y}^2 + \frac {2304} {x y} } } 2$ Quadratic Formula

Since $z \in \Z$:

$\sqrt {\paren {x + y}^2 + \dfrac {2304} {x y} } = 2 z + x + y \in \Z$

We check the value of $\sqrt {\paren {x + y}^2 + \dfrac {2304} {x y} }$ for the valid values of $x, y$.

We do not need to check $y = 5$ since $5 \nmid 576$.

We have:

$\tuple {1, 1}: \sqrt {\paren {1 + 1}^2 + \dfrac {2304} {1 \times 1} } = \sqrt {2308} \notin \Z$
$\tuple {1, 2}: \sqrt {\paren {1 + 2}^2 + \dfrac {2304} {1 \times 2} } = \sqrt {1161} \notin \Z$
$\tuple {1, 3}: \sqrt {\paren {1 + 3}^2 + \dfrac {2304} {1 \times 3} } = \sqrt {784} = 28$
$\tuple {1, 4}: \sqrt {\paren {1 + 4}^2 + \dfrac {2304} {1 \times 4} } = \sqrt {601} \notin \Z$
$\tuple {1, 6}: \sqrt {\paren {1 + 6}^2 + \dfrac {2304} {1 \times 6} } = \sqrt {433} \notin \Z$
$\tuple {2, 2}: \sqrt {\paren {2 + 2}^2 + \dfrac {2304} {2 \times 2} } = \sqrt {592} \notin \Z$
$\tuple {2, 3}: \sqrt {\paren {2 + 3}^2 + \dfrac {2304} {2 \times 3} } = \sqrt {409} \notin \Z$
$\tuple {2, 4}: \sqrt {\paren {2 + 4}^2 + \dfrac {2304} {2 \times 4} } = \sqrt {324} = 18$
$\tuple {3, 3}: \sqrt {\paren {3 + 3}^2 + \dfrac {2304} {3 \times 3} } = \sqrt {292} \notin \Z$
$\tuple {3, 4}: \sqrt {\paren {3 + 4}^2 + \dfrac {2304} {3 \times 4} } = \sqrt {241} \notin \Z$

Now we calculate $z$ for $\tuple {x, y} = \tuple {1, 3}, \tuple {2, 4}$.

$\tuple {1, 3}: z = \dfrac {- 1 - 3 + 28} 2 = 12$
$\tuple {2, 4}: z = \dfrac {- 2 - 4 + 18} 2 = 6$

Using:

$a = s - x = x + y + z - x = y + z$
$b = s - y = x + z$
$c = s - z = x + y$

the possible sets of side lengths are:

$\tuple {15, 13, 4}, \tuple {10, 8, 6}$

But note that the $\tuple {6, 8, 10}$ triangle is right-angled, and hence not a proper Heronian Triangle.

Hence the result.

$\blacksquare$


text:
# Numerical partial derivative of a composite function

I have found the two similar questions:

but don't know how to combine them properly.

I have

$$x=[x_1,x_2]^T$$

and

$$F(x) = g(f_1(x), f_2(x)) = g(f_1(x_1,x_2), f_2(x_1, x_2))$$

The goal is to compute $$\frac{\partial F}{\partial x_1}$$

My assumption is: $$\frac{\partial F}{\partial x_1} =\frac{F(x_1+h)-F(x_1-h)}{2h}=\frac{g(f_1(x_1+h,x_2),f_2(x_1+h,x_2))-g(f_1(x_1-h,x_2),f_2(x_1-h,x_2))}{2h}$$, given the fact that $$x_2$$ is constant while $$F$$ is being differentiated by $$x_1$$.

Is this formula correct?

• $∂F/∂𝑥_1$ = $∂g/∂f*∂f/∂𝑥_1$ – Äres Dec 24 '19 at 12:14
• Sure but i need numerical solution while you provide analytical. – Elia Dec 24 '19 at 12:24

Your formular is correct, you are using central finite differences applied to $$F(x)$$.
In some applications, when the derivatives of $$f$$ and $$g$$ are known functions, it is useful to employ $$\frac{d F}{d x_1} = \frac{\partial g}{ \partial y_1} \frac{\partial f_1}{ \partial x_1} + \frac{\partial g}{ \partial y_2} \frac{\partial f_2}{ \partial x_1}$$ Here I use the notation $$g(y_1,y_2)$$. Using this chain rule iteratively allows to get exact derivatives in the computer and it is called automatic differentiation.)


text:
Renormalization Multigrid (RMG): Statistically Optimal Renormalization Group Flow and Coarse-to-Fine Monte Carlo Acceleration

Achi Brandt and Dorit Ron
Department of Applied Math
The Weizmann Inst. of Science
Rehovot, 76100, Israel

Abstract

New renormalization-group algorithms are developed with adaptive representations of the renormalized action which automatically express only significant interactions. As the amount of statistics grows, more interactions enter, thereby systematically reducing the truncation error. This allows statistically optimal calculation of thermodynamic limits, in the sense that it achieves accuracy e in just O(1/(e*e)) random number generations. There are practically no finite-size effects and the renormalization transformation can be repeated arbitrarily many times. Consequently, the desired fixed point is obtained and the correlation-length critical exponent $\nu$ is extracted.In addition, we introduce a new multiscale coarse-to-fine acceleration method, based on a multigrid-like approach. This general (non-cluster) algorithm generates independent equilibrium configurations without slow down. A particularly simple version of it can be used at criticality. The methods are of great generality; here they are demonstrated on the 2D Ising model.

Key words. Ising model, Renormalization Multigrid, P+ probabilities, neighborhoods, criticalization, coarse-to-fine Monte Carlo acceleration, Compatible Monte Carlo, Post Relaxation.

Contributed July 15, 1999.


text:
# [tex-live] Bug#668562: Interoperability problem of frenchb.ldf and xeCJK.sty

Daniel Flipo daniel.flipo at free.fr
Tue May 1 21:36:28 CEST 2012

Hi Sun, hi all,

A bug report (see http://bugs.debian.org/668562) was made a fortnight
ago.  The origin of the problem is that xeCJK assigns "\XeTeXcharclass"
4 to 6 to various ASCII characters instead of creating its own classes
with "\newXeTeXintercharclass".

A minimal example of the bug follows:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass{article}
\usepackage{xeCJK}
\usepackage[french]{babel}
\begin{document}
anti\-atomique
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Yet another test file that shows a problem (the origin is the same)
between polyglossia/french and xeCJK.sty:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass{article}
\usepackage{xeCJK}
\usepackage{polyglossia}
\setdefaultlanguage{french}
\begin{document}
% A spurious space is added before the 4 chars , . ] )
a,b.c x[z]y  u(v)w
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The fix I suggested on April 19th was to define 3 named
"\newXeTeXintercharclass" and to use them instead of raw 4, 5, 6
classes, but I got no feedback from Sun.

Sun, please tell us if you are willing to fix this issue, thanks in advance.

I can fix it on frenchb.ldf side, but polyglossia or any package making
use of XeTeXinterchartokens' mecanism will have to add the same fix
also, IMHO it is not the right way to go.

Best wishes,
--
Daniel Flipo


text:
# garage.sampler.vec_worker¶

Worker that “vectorizes” environments.

class VecWorker(*, seed, max_episode_length, worker_number, n_envs=DEFAULT_N_ENVS)

Worker with a single policy and multiple environments.

Alternates between taking a single step in all environments and asking the policy for an action for every environment. This allows computing a batch of actions, which is generally much more efficient than computing a single action when using neural networks.

Parameters
• seed (int) – The seed to use to intialize random number generators.

• max_episode_length (int or float) – The maximum length of episodes which will be sampled. Can be (floating point) infinity.

• worker_number (int) – The number of the worker this update is occurring in. This argument is used set a different seed for each worker.

• n_envs (int) – Number of environment copies to use.

DEFAULT_N_ENVS = 8
update_agent(self, agent_update)

Update an agent, assuming it implements Policy.

Parameters

agent_update (np.ndarray or dict or Policy) – If a tuple, dict, or np.ndarray, these should be parameters to agent, which should have been generated by calling Policy.get_param_values. Alternatively, a policy itself. Note that other implementations of Worker may take different types for this parameter.

update_env(self, env_update)

Update the environments.

If passed a list (inside this list passed to the Sampler itself), distributes the environments across the “vectorization” dimension.

Parameters

env_update (Environment or EnvUpdate or None) – The environment to replace the existing env with. Note that other implementations of Worker may take different types for this parameter.

Raises
• TypeError – If env_update is not one of the documented types.

• ValueError – If the wrong number of updates is passed.

start_episode(self)

Begin a new episode.

step_episode(self)

Take a single time-step in the current episode.

Returns

True iff at least one of the episodes was completed.

Return type

bool

collect_episode(self)

Collect all completed episodes.

Returns

A batch of the episodes completed since the last call

to collect_episode().

Return type

EpisodeBatch

shutdown(self)

Close the worker’s environments.

worker_init(self)

Initialize a worker.

rollout(self)

Sample a single episode of the agent in the environment.

Returns

The collected episode.

Return type

EpisodeBatch


text:
# finding explicit solution to PDE with given initial conditions

A solution to a PDE of my interest is

$u(x,y)=2\left(F''(x)-G''(y)\right)(x-y)^{2}-12\left(F'(x)+G'(y)\right)(x-y)+24\left(F(x)-G(y)\right)$

where $F(x)$ and $G(y)$ are arbitrary functions to be determined from initial conditions. In this case, I know

$u(x,y_{0})=\frac{u_{0}(x-y_{0})^{2}}{(x_{0}-y_{0})^{2}}$,

$u(x_{0},y)=\frac{u_{0}(x_{0}-y)^{2}}{(x_{0}-y_{0})^{2}}$.

I tried all sorts of things to find $F(x)$ and $G(y)$. I tried all sorts of things to no avail; any suggestions what steps/approaches I should take?

I made some progress on this so I thought I would share it. First let $u(x_{0},y_{0})=u_{0}$ then one can write the following

$u(x_{0},y_{0})=2\left(F''(x_{0}-G''(y_{0})\right)(x_{0}-y_{0})^{2}-12\left(F'(x_{0})+G'(y_{0})\right)(x_{0}-y_{0})+24\left(F(x_{0}-G(y_{0}\right)=u_{0}$

Now choose five values arbitrarily and the 6th value will be determined. I made the following choices: $F''(x_{0})=1\quad F'(x_{0})=1\quad F(x_{0})=1 \quad G''(y_{0})=?\quad G'(y_{0})=-1 \quad G(y_{0})=1$

Then find $G''(y_{0})$ as follows:

$u_{0}=2(1-G''(y_{0}))(x_{0}-y_{0})^{2}$ and this gives $G''(y_{0})=1-k$ where

$k=\frac{1}{2}\frac{u_{0}}{(x_{0}-y_{0})^{2}}$

$u(x,y_{0})=\frac{u_{0}(x-y_{0})^{2}}{(x_{0}-y_{0})^{2}}$
$(x-y_{0})^{2}F''(x)-6(x-y_{0})F'(x)+12F(x)=H(x)$
$H(x)=(x-y_{0})^{2}+6(x-y_{0})+12$


text:
Home > MC1 > Chapter 9 > Lesson 9.2.5 > Problem9-114

9-114.

Copy the number line shown below and label the following numbers at their approximate place on the number line.

1. $\frac { 1 } { 7 }$

1. $65\%$

1. $0.87$

1. $\frac { 8 } { 9 }$

For parts (a) through (d), try first estimating if the portions are greater than or less than one half ($50\%$ or $0.5$).

Parts (c) and (d) are placed in their approximate place on the number line above. Can you place the portions in parts (a) and (b)?


text:
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp018336h191n

 Title: The Chorus in Dialogue: Reading Lyric Exchanges in Greek Tragedy Authors: Andujar, Rosa Margarita Advisors: Ford, Andrew L. Contributors: Classics Department Keywords: Greek chorusGreek TragedyMourning Subjects: Classical literatureTheater historyClassical studies Issue Date: 2011 Publisher: Princeton, NJ : Princeton University Abstract: From the "Ode to Man" to songs of praise, the Greek tragic chorus are readily associated with the odes that they sing. Critical accounts, however, overlook their performances in a different mode: lyric dialogues in which they engage with actors through song or a lyrical mixture blending speech. In this dissertation, I argue that these exchanges were sites of active and self-conscious experimentation in fifth-century Athenian tragedy, in which tragedians not only tested the performative capabilities of both chorus and actor but also explored the conditions under which interactions between a group and an individual succeeded or failed. In addition to defining and providing a taxonomy of lyric dialogues, I show that these exchanges, which blend choral and solo voices in song at critical junctures in the plot, tend either to dramatize reactions to horrific revelations or to reenact ritual laments for the dead. In both cases the tragedians stretch the boundaries of dialogue, often by staging curious exchanges that blend song and speech, at times even reversing the fundamental tragic pattern of speaking actor and singing chorus. These highly emotionally charged dialogues provide an opportunity to study how tragedy represents the strains placed on interpersonal communication, in particular the expression of strong emotion in a communal setting, while at the same time allowing us to see the experimental and self-reflexive nature of the genre. Combining philological attention to the theatrical and metrical qualities of these moments with the insights of social theory and performance studies, I argue that their frequency and dramatic sophistication suggest a persistent interest among the tragedians in the conditions under which a group and an individual are able to communicate and successfully perform rituals. I contend that the questions of communicative and ritualized action explored in these moments capture tensions fundamental both to Greek theatre and to the emerging Athenian democracy. URI: http://arks.princeton.edu/ark:/88435/dsp018336h191n Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog: http://catalog.princeton.edu/ Type of Material: Academic dissertations (Ph.D.) Language: en Appears in Collections: Classics

Files in This Item:

File Description SizeFormat


text:
# Chapter 10 - Quadratic Equations - 10.1 - Quadratic Equations - Problem Set 10.1: 83

10.8 cm

#### Work Step by Step

First, we must find the length of the diagonal along the bottom of the cube: $a^2 + b^2 = c^2 \\ c = \sqrt{a^2 + b^2} \\ c = \sqrt{6^2 + 8^2} =10$ We now find the length of the diagonal from the lower to the upper corner: $c = \sqrt{a^2 + b^2} \\ c = \sqrt{10^2 + 4^2} = 10.8$

After you claim an answer you’ll have 24 hours to send in a draft. An editor will review the submission and either publish your submission or provide feedback.


text:
# How do you identify all asymptotes for f(x)=1/(x-1)?

Apr 2, 2017

vertical asymptote at x = 1
horizontal asymptote at y = 0

#### Explanation:

The denominator of f(x) cannot be zero as this would make f(x) undefined. Equating the denominator to zero and solving gives the value that x cannot be and if the numerator is non-zero for this value then it is a vertical asymptote.

$\text{solve "x-1=0rArrx=1" is the asymptote}$

Horizontal asymptotes occur as

${\lim}_{x \to \pm \infty} , f \left(x\right) \to c \text{ ( a constant)}$

divide terms on numerator/denominator by x

$f \left(x\right) = \frac{\frac{1}{x}}{\frac{x}{x} - \frac{1}{x}} = \frac{\frac{1}{x}}{1 - \frac{1}{x}}$

as $x \to \pm \infty , f \left(x\right) \to \frac{0}{1 - 0}$

$\Rightarrow y = 0 \text{ is the asymptote}$
graph{1/(x-1) [-10, 10, -5, 5]}


text:
# The angle of elevation of the top of a tower at a point on the line through the foot of the tower is 45^@. After walking a distance towards the foot of the tower along the same horizontal line elevation of the top of the tower changes to 60^@. Find the height of tower.

Step by step solution by experts to help you in doubt clearance & scoring excellent marks in exams.

Updated On: 22-2-2020

Apne doubts clear karein ab Whatsapp par bhi. Try it now.

With the given details, we can create a diagram.
 Please refer to video to see the diagram.
 From the digram,
 In Delta OBC,
 h/x = tan60^@ = sqrt3
 =>x = h/sqrt3->(1)
 In Delta OAC,
 h/(80+x) = tan45^@ = 1
 => h = 80+x
 From (1),
 =>h = 80+h/sqrt3
 =>sqrt3h-h = 80sqrt3
 =>h = (80sqrt3)/(sqrt3-1)**(sqrt3+1)/(sqrt3+1)
 =>h = 40sqrt3(sqr3+1)m
 So,the height of the tower is 40sqrt3(sqrt3+1)m.


text:
# IP (complexity)

In computational complexity theory, the class IP (which stands for Interactive Polynomial time) is the class of problems solvable by an interactive proof system. It is equal to the class PSPACE.[1] The result is a famous example where the proof does not relativize.[2]

The concept of an interactive proof system was first introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in 1985. An interactive proof system consists of two machines, a prover, P, which presents a proof that a given string n is a member of some language, and a verifier, V, that checks that the presented proof is correct. The prover is assumed to be infinite in computation and storage, while the verifier is a probabilistic polynomial-time machine with access to a random bit string whose length is polynomial on the size of n. These two machines exchange a polynomial number, p(n), of messages and once the interaction is completed, the verifier must decide whether or not n is in the language, with only a 1/3 chance of error. (So any language in BPP is in IP, since then the verifier could simply ignore the prover and make the decision on its own.)

General representation of an interactive proof protocol.

## Definition

A language L belongs to IP if there exist V, P such that for all Q, w:

${\displaystyle w\in L\Rightarrow \Pr[V\leftrightarrow P{\text{ accepts }}w]\geq {\tfrac {2}{3}}}$
${\displaystyle w\not \in L\Rightarrow \Pr[V\leftrightarrow Q{\text{ accepts }}w]\leq {\tfrac {1}{3}}}$

The Arthur–Merlin protocol, introduced by László Babai, is similar in nature, except that the number of rounds of interaction is bounded by a constant rather than a polynomial.

Goldwasser et al. have shown that public-coin protocols, where the random numbers used by the verifier are provided to the prover along with the challenges, are no less powerful than private-coin protocols. At most two additional rounds of interaction are required to replicate the effect of a private-coin protocol. The opposite inclusion is straightforward, because the verifier can always send to the prover the results of their private coin tosses, which proves that the two types of protocols are equivalent.

In the following section we prove that IP = PSPACE, an important theorem in computational complexity, which demonstrates that an interactive proof system can be used to decide whether a string is a member of a language in polynomial time, even though the traditional PSPACE proof may be exponentially long.

## Proof of IP = PSPACE

The proof can be divided in two parts, we show that IPPSPACE and PSPACEIP.

### IP ⊆ PSPACE

In order to demonstrate that IPPSPACE, we present a simulation of an interactive proof system by a polynomial space machine. Now, we can define:

${\displaystyle \Pr[V{\text{ accepts }}w{\text{ starting at }}M_{j}]=\max \nolimits _{P}\Pr \left[V\leftrightarrow P{\text{ accepts }}w{\text{ starting at }}M_{j}\right]}$

and for every 0 ≤ jp and every message history Mj, we inductively define the function NMj:

${\displaystyle N_{M_{j}}={\begin{cases}0&j=p{\text{ and }}m_{p}={\text{reject}}\\1&j=p{\text{ and }}m_{p}={\text{accept}}\\\max _{m_{j+1}}N_{M_{j+1}}&j

where:

${\displaystyle {\text{wt-avg}}_{m_{j+1}}N_{M_{j+1}}:=\sum \nolimits _{m_{j+1}}\Pr \nolimits _{r}[V(w,r,M_{j})]}$

where Prr is the probability taken over the random string r of length p. This expression is the average of NMj+1, weighted by the probability that the verifier sent message mj+1.

Take M0 to be the empty message sequence, here we will show that NM0 can be computed in polynomial space, and that NM0 = Pr[V accepts w]. First, to compute NM0, an algorithm can recursively calculate the values NMj for every j and Mj. Since the depth of the recursion is p, only polynomial space is necessary. The second requirement is that we need NM0 = Pr[V accepts w], the value needed to determine whether w is in A. We use induction to prove this as follows.

We must show that for every 0 ≤ jp and every Mj, NMj = Pr[V accepts w starting at Mj], and we will do this using induction on j. The base case is to prove for j = p. Then we will use induction to go from p down to 0.

The base case of j = p is fairly simple. Since mp is either accept or reject, if mp is accept, NMp is defined to be 1 and Pr[V accepts w starting at Mj] = 1 since the message stream indicates acceptance, thus the claim is true. If mp is reject, the argument is very similar.

For the inductive hypothesis, we assume that for some j+1 ≤ p and any message sequence Mj+1, NMj = Pr[V accepts w starting at j+1] and then prove the hypothesis for j and any message sequence Mj.

If j is even, mj+1 is a message from V to P. By the definition of NMj,

${\displaystyle N_{M_{j}}=\sum \nolimits _{m_{j+1}}\Pr \nolimits _{r}\left[V(w,r,M_{j})=m_{j+1}\right]N_{M_{j+1}}.}$

Then, by the inductive hypothesis, we can say this is equal to

${\displaystyle \sum \nolimits _{m_{j+1}}\Pr \nolimits _{r}\left[V(w,r,M_{j})=m_{j+1}\right]*\Pr \left[V{\text{ accepts }}w{\text{ starting at }}M_{j+1}\right].}$

Finally, by definition, we can see that this is equal to Pr[V accepts w starting at Mj].

If j is odd, mj+1 is a message from P to V. By definition,

${\displaystyle N_{M_{j}}=\max \nolimits _{m_{j+1}}N_{M_{j+1}}.}$

Then, by the inductive hypothesis, this equals

${\displaystyle \max \nolimits _{m_{j+1}}*\Pr[V{\text{ accepts }}w{\text{ starting at }}M_{j+1}].}$

This is equal to Pr[V accepts w starting at Mj] since:

${\displaystyle \max \nolimits _{m_{j+1}}\Pr[V{\text{ accepts }}w{\text{ starting at }}M_{j+1}]\leq \Pr[V{\text{ accepts w starting at }}M_{j}]}$

because the prover on the right-hand side could send the message mj+1 to maximize the expression on the left-hand side. And:

${\displaystyle \max \nolimits _{m_{j+1}}\Pr \left[V{\text{ accepts }}w{\text{ starting at }}M_{j+1}\right]\geq \Pr \left[V{\text{ accepts }}w{\text{ starting at }}M_{j}\right]}$

Since the same Prover cannot do any better than send that same message. Thus, this holds whether i is even or odd and the proof that IPPSPACE is complete.

Here we have constructed a polynomial space machine that uses the best prover P for a particular string w in language A. We use this best prover in place of a prover with random input bits because we are able to try every set of random input bits in polynomial space. Since we have simulated an interactive proof system with a polynomial space machine, we have shown that IPPSPACE, as desired.

### PSPACE ⊆ IP

In order to illustrate the technique that will be used to prove PSPACEIP, we will first prove a weaker theorem, which was proven by Lund, et al.: #SAT ∈ IP. Then using the concepts from this proof we will extend it to show that TQBF ∈ IP. Since TQBF ∈ PSPACE-complete, and TQBF ∈ IP then PSPACEIP.

#### #SAT is a member of IP

We begin by showing that #SAT is in IP, where:

${\displaystyle \#{\text{SAT}}=\left\{\langle \varphi ,k\rangle \ :\ \varphi {\text{ is a CNF-formula with exactly }}k{\text{ satisfying assignments}}\right\}.}$

Note that this is different from the normal definition of #SAT, in that it is a decision problem, rather than a function.

First we use arithmetization to map the boolean formula with n variables, φ(b1, ..., bn) to a polynomial pφ(x1, ..., xn), where pφ mimics φ in that pφ is 1 if φ is true and 0 otherwise provided that the variables of pφ are assigned Boolean values. The Boolean operations ∨, ∧ and ¬ used in φ are simulated in pφ by replacing the operators in φ as shown in the table below.

 a ∧ b ab a ∨ b a ∗ b := 1 − (1 − a)(1 − b) ¬a 1 − a

As an example, φ = ab ∨ ¬c would be converted into a polynomial as follows:

{\displaystyle {\begin{aligned}p_{\varphi }&=a\wedge b\vee \neg c\\&=a\wedge \left(b*(1-c)\right)\\&=a\wedge \left(1-(1-b)(1-(1-c))\right)\\&=a\left(1-(1-b)(1-(1-c))\right)\\&=a-(ac-abc)\end{aligned}}}

The operations ab and ab each result in a polynomial with a degree bounded by the sum of the degrees of the polynomials for a and b and hence, the degree of any variable is at most the length of φ.

Now let F be a finite field with order q > 2n; also demand that q be at least 1000. For each 0 ≤ in, define a function fi on F, having parameters ${\displaystyle a_{1},\dots ,a_{i-1}\in F}$, and a single variable ai in F: For 0 ≤ in and for ${\displaystyle a_{1},\dots ,a_{i}\in F}$ let

${\displaystyle f_{i}(a_{1},\dots ,a_{i})=\sum \nolimits _{a_{i+1},\dots ,a_{n}\in \{0,1\}}p(a_{1},\dots ,a_{n}).}$

Note that the value of f0 is the number of satisfying assignments of φ. f0 is a void function, with no variables.

Now the protocol for #SAT works as follows:

• Phase 0: The prover P chooses a prime q > 2n and computes f, it then sends q and f0 to the verifier V. V checks that q is a prime greater than max(1000, 2n) and that f0() = k.
• Phase 1: P sends the coefficients of f1(z) as a polynomial in z. V verifies that the degree of f1 is less than n and that f0 = f1(0) + f1(1). (If not V rejects). V now sends a random number r1 from F to P.
• Phase i: P sends the coefficients of ${\displaystyle f_{i}(r_{1},\dots ,r_{i-1},z)}$ as a polynomial in z. V verifies that the degree of fi is less than n and that ${\displaystyle f_{i-1}(r_{1},\dots ,r_{i-1})=f_{i}(r_{1},\dots ,r_{i-1},0)+f_{i}(r_{1},\dots ,r_{i-1},1)}$. (If not V rejects). V now sends a random number ri from F to P.
• Phase n+1: V evaluates ${\displaystyle p(r_{1},\dots ,r_{n})}$ to compare to the value ${\displaystyle f_{n}(r_{1},\dots ,r_{n})}$. If they are equal V accepts, otherwise V rejects.

Note that this is a public-coin algorithm.

If φ has k satisfying assignments, clearly V will accept. If φ does not have k satisfying assignments we assume there is a prover ${\displaystyle {\tilde {P}}}$ that tries to convince V that φ does have k satisfying assignments. We show that this can only be done with low probability.

To prevent V from rejecting in phase 0, ${\displaystyle {\tilde {P}}}$ has to send an incorrect value ${\displaystyle {\tilde {f}}_{0}()}$ to P. Then, in phase 1, ${\displaystyle {\tilde {P}}}$ must send an incorrect polynomial ${\displaystyle {\tilde {f}}_{1}}$ with the property that ${\displaystyle {\tilde {f}}_{1}(0)+{\tilde {f}}_{1}(1)={\tilde {f}}_{0}()}$. When V chooses a random r1 to send to P,

${\displaystyle \Pr \left[{\tilde {f}}_{1}(r_{1})=f_{1}(r_{1})\right]<{\tfrac {1}{n^{2}}}.}$

This is because a polynomial in a single variable of degree at most d can have no more than d roots (unless it always evaluates to 0). So, any two polynomials in a single variable of degree at most d can be equal only in d places. Since |F| > 2n the chances of r1 being one of these values is at most ${\displaystyle n/2^{n} if n > 10, or at most (n/1000) ≤ (n/n3) if n ≤ 10.

Generalizing this idea for the other phases we have for each 1 ≤ in if

${\displaystyle {\tilde {f}}_{i-1}(r_{1},\dots ,r_{i-1})\neq f_{i-1}(r_{1},\dots ,r_{i-1}),}$

then for ri chosen randomly from F,

${\displaystyle \Pr \left[{\tilde {f}}(r_{1},\dots ,r_{i})=f_{i}(r_{1},\dots ,r_{i})\right]\leq {\tfrac {1}{n^{2}}}.}$

There are n phases, so the probability that ${\displaystyle {\tilde {P}}}$ is lucky because V selects at some stage a convenient ri is at most 1/n. So, no prover can make the verifier accept with probability greater than 1/n. We can also see from the definition that the verifier V operates in probabilistic polynomial time. Thus, #SAT ∈ IP.

#### TQBF is a member of IP

In order to show that PSPACE is a subset of IP, we need to choose a PSPACE-complete problem and show that it is in IP. Once we show this, then it clear that PSPACEIP. The proof technique demonstrated here is credited to Adi Shamir.

We know that TQBF is in PSPACE-Complete. So let ψ be a quantified boolean expression:

${\displaystyle \psi ={\mathsf {Q}}_{1}x_{1}\dots {\mathsf {Q}}_{m}x_{m}[\varphi ]}$

where φ is a CNF formula. Then Qi is a quantifier, either ∃ or ∀. Now fi is the same as in the previous proof, but now it also includes quantifiers.

${\displaystyle f_{i}(a_{1},\dots ,a_{i})={\begin{cases}f_{i}(a_{1},\dots ,a_{m})=1&{\mathsf {Q}}_{i+1}x_{i+1}\dots {\mathsf {Q}}_{m}x_{m}[\varphi (a_{1},\dots ,a_{i})]{\text{ is true}}\\0&{\text{otherwise}}\end{cases}}}$

Here, φ(a1, ..., ai) is φ with a1 to ai substituted for x1 to xi. Thus f0 is the truth value of ψ. In order to arithmetize ψ we must use the following rules:

${\displaystyle f_{i}(a_{1},\dots ,a_{i})={\begin{cases}f_{i+1}(a_{1},\dots ,a_{i},0)\cdot f_{i+1}(a_{1},\dots ,a_{i},1)&{\mathsf {Q}}_{i+1}=\forall \\f_{i+1}(a_{1},\dots ,a_{i},0)*f_{i+1}(a_{1},\dots ,a_{i},1)&{\mathsf {Q}}_{i+1}=\exists \end{cases}}}$

where as before we define xy = 1 − (1 − x)(1 − y).

By using the method described in #SAT, we must face a problem that for any fi the degree of the resulting polynomial may double with each quantifier. In order to prevent this, we must introduce a new reduction operator R which will reduce the degrees of the polynomial without changing their behavior on Boolean inputs.

So now before we arithmetize ${\displaystyle \psi ={\mathsf {Q}}_{1}x_{1}\dots {\mathsf {Q}}_{m}x_{m}[\varphi ]}$ we introduce a new expression:

${\displaystyle \psi '={\mathsf {Q}}_{1}\mathrm {R} x_{1}{\mathsf {Q}}_{2}\mathrm {R} x_{1}\mathrm {R} x_{2}\dots {\mathsf {Q}}_{m}\mathrm {R} x_{1}\dots \mathrm {R} x_{m}[\varphi ]}$

or put another way:

${\displaystyle \psi '={\mathsf {S}}_{1}y_{1}\dots {\mathsf {S}}_{k}y_{k}[\varphi ],\qquad {\text{ where }}{\mathsf {S}}_{i}\in \{\forall ,\exists ,\mathrm {R} \},\ y_{i}\in \{x_{1},\dots ,x_{m}\}}$

Now for every ik we define the function fi. We also define ${\displaystyle f_{k}(x_{1},\dots ,x_{m})}$ to be the polynomial p(x1, ..., xm) which is obtained by arithmetizing φ. Now in order to keep the degree of the polynomial low, we define fi in terms of fi+1:

${\displaystyle {\text{If }}{\mathsf {S}}_{i+1}=\forall ,\quad f_{i}(a_{1},\dots ,a_{i})=f_{i+1}(a_{1},\dots ,a_{i},0)\cdot f_{i+1}(a_{1},\dots ,a_{i},1)}$
${\displaystyle {\text{If }}{\mathsf {S}}_{i+1}=\exists ,\quad f_{i}(a_{1},\dots ,a_{i})=f_{i+1}(a_{1},\dots ,a_{i},0)*f_{i+1}(a_{1},\dots ,a_{i},1)}$
${\displaystyle {\text{If }}{\mathsf {S}}_{i+1}=\mathrm {R} ,\quad f_{i}(a_{1},\dots ,a_{i},a)=(1-a)f_{i+1}(a_{1},\dots ,a_{i},0)+af_{i+1}(a_{1},\dots ,a_{i},1)}$

Now we can see that the reduction operation R, doesn't change the degree of the polynomial. Also it is important to see that the Rx operation doesn't change the value of the function on boolean inputs. So f0 is still the truth value of ψ, but the Rx value produces a result that is linear in x. Also after any ${\displaystyle {\mathsf {Q}}_{i}x_{i}}$ we add ${\displaystyle \mathrm {R} _{x_{1}}\dots \mathrm {R} _{x_{i}}}$ in ψ′ in order to reduce the degree down to 1 after arithmetizing ${\displaystyle {\mathsf {Q}}_{i}}$.

Now let's describe the protocol. If n is the length of ψ, all arithmetic operations in the protocol are over a field of size at least n4 where n is the length of ψ.

• Phase 0: PV: P sends f0 to V. V checks that f0= 1 and rejects if not.
• Phase 1: PV: P sends f1(z) to V. V uses coefficients to evaluate f1(0) and f1(1). Then it checks that the polynomial's degree is at most n and that the following identities are true:
${\displaystyle f_{0}(\varnothing )={\begin{cases}f_{1}(0)\cdot f_{1}(1)&{\text{ if }}{\mathsf {S}}=\forall \\f_{1}(0)*f_{1}(1)&{\text{ if }}{\mathsf {S}}=\exists .\\(1-r)f_{1}(0)+rf_{1}(1)&{\text{ if }}{\mathsf {S}}=\mathrm {R} .\end{cases}}}$
If either fails then reject.
• Phase i: PV: P sends ${\displaystyle f_{i}(r_{1},\dots ,r_{i-1},z)}$ as a polynomial in z. r1 denotes the previously set random values for ${\displaystyle r_{1},\dots ,r_{i-1}}$

V uses coefficients to evaluate ${\displaystyle f_{i}(r_{1},\dots ,r_{i-1},0)}$ and ${\displaystyle f_{i}(r_{1},\dots ,r_{i-1},1)}$. Then it checks that the polynomial degree is at most n and that the following identities are true:

${\displaystyle f_{i-1}(r_{1},\dots ,r_{i-1})={\begin{cases}f_{i}(r_{1},\dots ,r_{i-1},0)\cdot f_{i}(r_{1},\dots ,r_{i-1},1)&{\mathsf {S}}=\forall \\f_{i}(r_{1},\dots ,r_{i-1},0)*f_{i}(r_{1},\dots ,r_{i-1},1)&{\mathsf {S}}=\exists .\end{cases}}}$
${\displaystyle f_{i-1}(r_{1}\dots r)=(1-r)f_{i}(r_{1},\dots ,r_{i-1},0)+rf_{i}(r_{1},\dots ,r_{i-1},1){\text{ if }}{\mathsf {S}}=\mathrm {R} .}$

If either fails then reject.

VP: V picks a random r in F and sends it to P. (If ${\displaystyle {\mathsf {S}}=\mathrm {R} }$ then this r replaces the previous r).

Goto phase i + 1 where P must persuade V that ${\displaystyle f_{i}(r_{1},\dots ,r)}$ is correct.

• Phase k + 1: V evaluates ${\displaystyle p(r_{1},\dots ,r_{m})}$. Then it checks if ${\displaystyle p(r_{1},\dots ,r_{m})=f_{k}(r_{1},\dots ,r_{m})}$ If they are equal then V accepts, otherwise V rejects.

This is the end of the protocol description.

If ψ is true then V will accept when P follows the protocol. Likewise if ${\displaystyle {\tilde {P}}}$ is a malicious prover which lies, and if ψ is false, then ${\displaystyle {\tilde {P}}}$ will need to lie at phase 0 and send some value for f0. If at phase i, V has an incorrect value for ${\displaystyle f_{i-1}(r_{1},\dots )}$ then ${\displaystyle f_{i}(r_{1},\dots ,0)}$ and ${\displaystyle f_{i}(r_{1},\dots ,1)}$ will likely also be incorrect, and so forth. The probability for ${\displaystyle {\tilde {P}}}$ to get lucky on some random r is at most the degree of the polynomial divided by the field size: ${\displaystyle n/n^{4}}$. The protocol runs through O(n2) phases, so the probability that ${\displaystyle {\tilde {P}}}$ gets lucky at some phase is ≤ 1/n. If ${\displaystyle {\tilde {P}}}$ is never lucky, then V will reject at phase k+1.

Since we have now shown that both IPPSPACE and PSPACEIP, we can conclude that IP = PSPACE as desired. Moreover, we have shown that any IP algorithm may be taken to be public-coin, since the reduction from PSPACE to IP has this property.

## Variants

There are a number of variants of IP which slightly modify the definition of the interactive proof system. We summarize some of the better-known ones here.

### dIP

A subset of IP is the deterministic Interactive Proof class, which is similar to IP but has a deterministic verifier (i.e. with no randomness). This class is equal to NP.

### Perfect Completeness

An equivalent definition of IP replaces the condition that the interaction succeeds with high probability on strings in the language with the requirement that it always succeeds:

${\displaystyle w\in L\Rightarrow \Pr[V\leftrightarrow P{\text{ accepts }}w]=1}$

This seemingly stronger criterion of "perfect completeness" does not change the complexity class IP, since any language with an interactive proof system may be given an interactive proof system with perfect completeness.[3]

### MIP

In 1988, Goldwasser et al. created an even more powerful interactive proof system based on IP called MIP in which there are two independent provers. The two provers cannot communicate once the verifier has begun sending messages to them. Just as it's easier to tell if a criminal is lying if he and his partner are interrogated in separate rooms, it's considerably easier to detect a malicious prover trying to trick the verifier if there is another prover it can double-check with. In fact, this is so helpful that Babai, Fortnow, and Lund were able to show that MIP = NEXPTIME, the class of all problems solvable by a nondeterministic machine in exponential time, a very large class. Moreover, all languages in NP have zero-knowledge proofs in an MIP system, without any additional assumptions; this is only known for IP assuming the existence of one-way functions.

### IPP

IPP (unbounded IP) is a variant of IP where we replace the BPP verifier by a PP verifier. More precisely, we modify the completeness and soundness conditions as follows:

• Completeness: if a string is in the language, the honest verifier will be convinced of this fact by an honest prover with probability at least 1/2.
• Soundness: if the string is not in the language, no prover can convince the honest verifier that it is in the language, except with probability less than 1/2.

Although IPP also equals PSPACE, IPP protocols behaves quite differently from IP with respect to oracles: IPP=PSPACE with respect to all oracles, while IPPSPACE with respect to almost all oracles.[4]

### QIP

QIP is a version of IP replacing the BPP verifier by a BQP verifier, where BQP is the class of problems solvable by quantum computers in polynomial time. The messages are composed of qubits.[5] In 2009, Jain, Ji, Upadhyay, and Watrous proved that QIP also equals PSPACE,[6] implying that this change gives no additional power to the protocol. This subsumes a previous result of Kitaev and Watrous that QIP is contained in EXPTIME because QIP = QIP[3], so that more than three rounds are never necessary.[7]

### compIP

Whereas IPP and QIP give more power to the verifier, a compIP system (competitive IP proof system) weakens the completeness condition in a way that weakens the prover:

• Completeness: if a string is in the language L, the honest verifier will be convinced of this fact by an honest prover with probability at least 2/3. Moreover, the prover will do so in probabilistic polynomial time given access to an oracle for the language L.

Essentially, this makes the prover a BPP machine with access to an oracle for the language, but only in the completeness case, not the soundness case. The concept is that if a language is in compIP, then interactively proving it is in some sense as easy as deciding it. With the oracle, the prover can easily solve the problem, but its limited power makes it much more difficult to convince the verifier of anything. In fact, compIP isn't even known or believed to contain NP.

On the other hand, such a system can solve some problems believed to be hard. Somewhat paradoxically, though such a system is not believed to be able to solve all of NP, it can easily solve all NP-complete problems due to self-reducibility. This stems from the fact that if the language L is not NP-hard, the prover is substantially limited in power (as it can no longer decide all NP problems with its oracle).

Additionally, the graph nonisomorphism problem (which is a classical problem in IP) is also in compIP, since the only hard operation the prover has to do is isomorphism testing, which it can use the oracle to solve. Quadratic non-residuosity and graph isomorphism are also in compIP.[8] Note, Quadratic non-residuosity (QNR) is likely an easier problem than graph isomorphism as QNR is in UP intersect co-UP.[9]

## Notes

1. ^ Shamir, Adi. "Ip= pspace." Journal of the ACM 39.4 (1992): 869-877.
2. ^ Chang Richard; et al. (1994). "The random oracle hypothesis is false". Journal of Computer and System Sciences. 49 (1): 24–39. doi:10.1016/s0022-0000(05)80084-4.
3. ^ Furer Martin, Goldreich Oded, Mansour Yishay, Sipser Michael, Zachos Stathis (1989). "On Completeness and Soundness in Interactive Proof Systems". Advances in Computing Research: A Research Annual. 5: 429–442.
4. ^ R. Chang, B. Chor, Oded Goldreich, J. Hartmanis, J. Håstad, D. Ranjan, and P. Rohatgi. The random oracle hypothesis is false. Journal of Computer and System Sciences, 49(1):24-39. 1994.
5. ^ J. Watrous. PSPACE has constant-round quantum interactive proof systems. Proceedings of IEEE FOCS'99, pp. 112-119. 1999.
6. ^ Rahul Jain; Zhengfeng Ji; Sarvagya Upadhyay; John Watrous (2009). "QIP = PSPACE". arXiv: [quant-ph].
7. ^ A. Kitaev and J. Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. Proceedings of the 32nd ACM Symposium on Theory of Computing, pp. 608-617. 2000.
8. ^ Shafi Goldwasser and Mihir Bellare. The Complexity of Decision versus Search. SIAM Journal on Computing, Volume 23, No. 1. February 1994.
9. ^ Cai JY, Threlfall RA (2004). "A note on quadratic residuosity and UP". Information Processing Letters. 92 (3): 127–131. doi:10.1016/j.ipl.2004.06.015.


text:
sdf_describe

0th

Percentile

Compute summary statistics for columns of a data frame

Compute summary statistics for columns of a data frame

Usage
sdf_describe(x, cols = colnames(x))
Arguments
x

An object coercible to a Spark DataFrame

cols

Columns to compute statistics for, given as a character vector

• sdf_describe


text:
# Is there other way to prove that unit sphere in Euclidean space is a infinite set?

Let $S=\{x\in \mathbb{R}^n;|x|=1\}$ the unit sphere in Euclidean space, where $n>1$ and $|\cdot|:\mathbb{R}^n\rightarrow\mathbb{R}$ is a arbitrary norm.

The problem is to prove that $S$ is a infinit set. One way to prove it, is to show that there is a infinit set $X\subset \mathbb{R}^n$ such as $|x|=1$ for all $x\in X$. For example, $$X=\left \{\frac{(m,1,...,1)}{|(m,1,...,1)|}\in\mathbb{R}^n;m\in\mathbb{N}\right\}$$

Is there other way?

-
Your set $X$ is not a subset of $\mathbb R$. Why don't you start by understanding why the unit circle in $\mathbb R^2$ has infinitely many points? –  Ted Shifrin Jun 19 '13 at 13:58
Actually, $X$ is a subset of $\mathbb{R}^n$. Sorry. –  Pedro Jun 19 '13 at 14:05
Your definition of $X$ still has an $\mathbb R$ in it. Also, $n$ is fixed, so use a different letter for the elements of $\mathbb N$. –  Ted Shifrin Jun 19 '13 at 14:12

First, try to do it for $\|\cdot\|_2$:

$$f:\begin{array}{ll}[0,1]\to S\\t\mapsto \left(t,\sqrt{1-t^2},0,\dots,0\right)\end{array}$$

$f$ is injective since $\forall t_1,t_2 \in [0,1], f(t_1)=f(t_2) \implies \left(t_1,\sqrt{1-t_1^2},0,\dots,0\right) = \left(t_2,\sqrt{1-t_2^2},0,\dots,0\right) \implies t_1 = t_2$. This tells you that there are more elements in $S$ than in $[0,1]$. Since you know that $[0,1]$ is infinite, youcan therefore conclude that $S$ is.

But for another norm, this can't work since our function was made specifically for $\|\cdot\|_2$.

Let's start by taking $\alpha = \cfrac{1}{\|(1,0,\dots,0)\|}$. We have $\|(\alpha,0,\dots,0)\|=1$.

Now for any $x\in [0,\alpha],$ define

$$g_x:\begin{array}{ll}\Bbb R_+\to \Bbb R_+\\t\mapsto \left\|\left(x,t,0,\dots,0\right)\right\|\end{array}$$

$g_x(0)=\cfrac{x}{\alpha}\le 1$ and $\lim\limits_{t\to +\infty}g_x(t)=+\infty$ so by the mean value theorem, we have $t_0 \in \Bbb R_+,g_x(t_0)=1$. For any $x\in[0,\alpha]$, we'll call that $t_0$ $h(x)$.

Now define $$f:\begin{array}{ll}[0,1]\to S\\t\mapsto \left(t,h(t),0,\dots,0\right)\end{array}$$

It is properly defined since we chose the $h(t)$ so that the vector is in $S$ and it is still injective for the same reason as for $\|\cdot\|_2$. So $S$ is infinite.

-