text:
# 机器学习::文本特征提取（TF-IDF） - 第二部分

Read the first part of this tutorial:Text feature extraction (tf-idf) – Part I

Since a lot of people liked the first part of this tutorial, this second part is a little longer than the first.

### Introduction

In the first post, we learned how to use theterm-frequencyto represent textual information in the vector space. However, the main problem with the term-frequency approach is that it scales up frequent terms and scales down rare terms which are empirically more informative than the high frequency terms. The basic intuition is that a term that occurs frequently in many documents is not a good discriminator, and really makes sense (at least in many experimental tests); the important question here is: why would you, in a classification problem for instance, emphasize a term which is almost present in the entire corpus of your documents ?

To overcome this problem, the term frequency$\ mathrm {TF}（T，d）$of a document on a vector space is usually also normalized. Let’s see how we normalize this vector.

### Vector normalization

Suppose we are going to normalize the term-frequency vector$\ {VEC V_ {D_4}}$that we have calculated in the first part of this tutorial. The document$d4$从本教程的第一部分中有这样的文字表示：

D4：我们可以看到闪亮的阳光，明亮的阳光下。

$\ {VEC V_ {D_4}} =（0,2,1,0）$

To normalize the vector, is the same as calculating theUnit Vector矢量，而他们使用的是“帽子”符号表示：$\帽子{V}$。The definition of the unit vector$\帽子{V}$一个向量的$\ VEC {V}$is:

$\的DisplayStyle \帽子{V} = \压裂{\ vec的{V}} {\ | \ vec的{V} \ | _p}$

Where the$\帽子{V}$is the unit vector, or the normalized vector, the$\ VEC {V}$在矢量将被归一化和$\|\vec{v}\|_p$is the norm (magnitude, length) of the vector$\ VEC {V}$in the$L^p$空间（别担心，我将所有的解释）。

The unit vector is actually nothing more than a normalized version of the vector, is a vector which the length is 1.

But the important question here is how the length of the vector is calculated and to understand this, you must understand the motivation of the$L^p$spaces, also calledLebesgue spaces

### Lebesgue spaces

Usually, the length of a vector$\vec{u} = (u_1, u_2, u_3, \ldots, u_n)$is calculated using theEuclidean norma norm is a function that assigns a strictly positive length or size to all vectors in a vector space-, which is defined by:

$\|\vec{u}\| = \sqrt{u^2_1 + u^2_2 + u^2_3 + \ldots + u^2_n}$

But this isn’t the only way to define length, and that’s why you see (sometimes) a number$p$符合规范的符号，就像在了一起$\|\vec{u}\|_p$。That’s because it could be generalized as:

$\displaystyle \|\vec{u}\|_p = ( \left|u_1\right|^p + \left|u_2\right|^p + \left|u_3\right|^p + \ldots + \left|u_n\right|^p )^\frac{1}{p}$

$\的DisplayStyle \ | \ VEC【U} \ | _p =（\总和\ limits_ {I = 1} ^ {N} \左| \ VEC {U】_i \右| ^ P）^ \压裂{1} {P}$

So when you read about aL2-norm, you’re reading about theEuclidean norm, a norm with$p = 2$, the most common norm used to measure the length of a vector, typically called “magnitude”; actually, when you have an unqualified length measure (without the$p$number), you have theL2-norm(Euclidean norm).

When you read about aL1-norm, you’re reading about the norm with$p=1$, defined as:

$\的DisplayStyle \ | \ VEC【U} \ | _1 =（\左| U_1 \右| + \左| U_2 \右| + \左| U_3 \右| + \ ldots + \左| u_n \右|）$

Which is nothing more than a simple sum of the components of the vector, also known as出租汽车距离，也被称为曼哈顿距离。

Taxicab geometry versus Euclidean distance: In taxicab geometry all three pictured lines have the same length (12) for the same route. In Euclidean geometry, the green line has length$6 \times \sqrt{2} \approx 8.48$, and is the unique shortest path.
Source:维基百科::出租车几何

### 返回矢量归

$\帽子{V}= \frac{\vec{v}}{\|\vec{v}\|_p} \\ \\ \hat{v_{d_4}} = \frac{\vec{v_{d_4}}}{||\vec{v_{d_4}}||_2} \\ \\ \\ \hat{v_{d_4}} = \frac{(0,2,1,0)}{\sqrt{0^2 + 2^2 + 1^2 + 0^2}} \\ \\ \hat{v_{d_4}} = \frac{(0,2,1,0)}{\sqrt{5}} \\ \\ \small \hat{v_{d_4}} = (0.0, 0.89442719, 0.4472136, 0.0)$

And that is it ! Our normalized vector$\ {帽子V_ {D_4}}$has now a L2-norm$\ | \帽子{V_ {D_4}} \ | _2 = 1.0$

### 术语频率 - 逆文档频率（TF-IDF）重量

Now you have understood how the vector normalization works in theory and practice, let’s continue our tutorial. Suppose you have the following documents in your collection (taken from the first part of tutorial):

火车文档集：D1：天空是蓝色的。D2：阳光灿烂。测试文档集：D3：在天空，阳光灿烂。D4：我们可以看到闪亮的阳光，明亮的阳光下。

Let’s see now, how idf (inverse document frequency) is then defined:

$\的DisplayStyle \ mathrm {IDF}（T）= \日志{\压裂{\左| d \右|} {1+ \左| \ {d：吨\在d \} \右|}}$

$\ mathrm {TF \ MBOX { - } IDF}（T）= \ mathrm {TF}（T，d）\倍\ mathrm {IDF}（t）的$

and this formula has an important consequence: a high weight of the tf-idf calculation is reached when you have a high term frequency (tf) in the given document (local parameter) and a low document frequency of the term in the whole collection (global parameter).

Now let’s calculate the idf for each feature present in the feature matrix with the term frequency we have calculated in the first tutorial:

$M_{train} = \begin{bmatrix} 0 & 1 & 1 & 1\\ 0 & 2 & 1 & 0 \end{bmatrix}$

Since we have 4 features, we have to calculate$\mathrm{idf}(t_1)$,$\mathrm{idf}(t_2)$,$\mathrm{idf}(t_3)$,$\mathrm{idf}(t_4)$:

$\ mathrm {IDF}（T_1）= \日志{\压裂{\左| d \右|} {1+ \左| \ {d：T_1 \在d \} \右|}} = \日志{\压裂{2} {1}} = 0.69314718$

$\mathrm{idf}(t_2) = \log{\frac{\left|D\right|}{1+\left|\{d : t_2 \in d\}\right|}} = \log{\frac{2}{3}} = -0.40546511$

$\mathrm{idf}(t_3) = \log{\frac{\left|D\right|}{1+\left|\{d : t_3 \in d\}\right|}} = \log{\frac{2}{3}} = -0.40546511$

$\mathrm{idf}(t_4) = \log{\frac{\left|D\right|}{1+\left|\{d : t_4 \in d\}\right|}} = \log{\frac{2}{2}} = 0.0$

These idf weights can be represented by a vector as:

$\ {VEC {idf_列车}}= (0.69314718, -0.40546511, -0.40546511, 0.0)$

$M_{idf} = \begin{bmatrix} 0.69314718 & 0 & 0 & 0\\ 0 & -0.40546511 & 0 & 0\\ 0 & 0 & -0.40546511 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix}$

$M_{tf\mbox{-}idf} = M_{train} \times M_{idf}$

Please note that the matrix multiplication isn’t commutative, the result of$A \乘以B$will be different than the result of the$乙\一个时代$, and this is why the$M_{idf}$is on the right side of the multiplication, to accomplish the desired effect of multiplying each idf value to its corresponding feature:

$\begin{bmatrix} \mathrm{tf}(t_1, d_1) & \mathrm{tf}(t_2, d_1) & \mathrm{tf}(t_3, d_1) & \mathrm{tf}(t_4, d_1)\\ \mathrm{tf}(t_1, d_2) & \mathrm{tf}(t_2, d_2) & \mathrm{tf}(t_3, d_2) & \mathrm{tf}(t_4, d_2) \end{bmatrix} \times \begin{bmatrix} \mathrm{idf}(t_1) & 0 & 0 & 0\\ 0 & \mathrm{idf}(t_2) & 0 & 0\\ 0 & 0 & \mathrm{idf}(t_3) & 0\\ 0 & 0 & 0 & \mathrm{idf}(t_4) \end{bmatrix} \\ = \begin{bmatrix} \mathrm{tf}(t_1, d_1) \times \mathrm{idf}(t_1) & \mathrm{tf}(t_2, d_1) \times \mathrm{idf}(t_2) & \mathrm{tf}(t_3, d_1) \times \mathrm{idf}(t_3) & \mathrm{tf}(t_4, d_1) \times \mathrm{idf}(t_4)\\ \mathrm{tf}(t_1, d_2) \times \mathrm{idf}(t_1) & \mathrm{tf}(t_2, d_2) \times \mathrm{idf}(t_2) & \mathrm{tf}(t_3, d_2) \times \mathrm{idf}(t_3) & \mathrm{tf}(t_4, d_2) \times \mathrm{idf}(t_4) \end{bmatrix}$

Let’s see now a concrete example of this multiplication:

$M_{tf\mbox{-}idf} = M_{train} \times M_{idf} = \\ \begin{bmatrix} 0 & 1 & 1 & 1\\ 0 & 2 & 1 & 0 \end{bmatrix} \times \begin{bmatrix} 0.69314718 & 0 & 0 & 0\\ 0 & -0.40546511 & 0 & 0\\ 0 & 0 & -0.40546511 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix} \\ = \begin{bmatrix} 0 & -0.40546511 & -0.40546511 & 0\\ 0 & -0.81093022 & -0.40546511 & 0 \end{bmatrix}$

And finally, we can apply our L2 normalization process to the$M_{tf\mbox{-}idf}$矩阵。Please note that this normalization is“row-wise”因为我们要处理矩阵的每一行作为一个分离向量进行归一化，而不是矩阵作为一个整体：

$M_ {TF \ MBOX { - } IDF} = \压裂{M_ {TF \ MBOX { - } IDF}} {\ | M_ {TF \ MBOX { - } IDF} \ | _2}$ $= \begin{bmatrix} 0 & -0.70710678 & -0.70710678 & 0\\ 0 & -0.89442719 & -0.4472136 & 0 \end{bmatrix}$

And that is our pretty normalized tf-idf weight of our testing document set, which is actually a collection of unit vectors. If you take the L2-norm of each row of the matrix, you’ll see that they all have a L2-norm of 1.

### Python的实践

Environment Used:Python的v.2.7.2,Numpy 1.6.1,Scipy v.0.9.0,Sklearn (Scikits.learn) v.0.9

Now the section you were waiting for ! In this section I’ll use Python to show each step of the tf-idf calculation using theScikit.learn特征提取模块。

从sklearn.feature_extraction.text进口CountVectorizer train_set =（“天空是蓝色的。”，“阳光灿烂”。）TEST_SET =（“在天空中的太阳是光明的。”，“我们可以看到闪耀的太阳，。明亮的太阳“）count_vectorizer = CountVectorizer（）count_vectorizer.fit_transform（train_set）打印 ”词汇“，count_vectorizer.vocabulary＃词汇：{ '蓝'：0， '太阳'：1， '鲜艳'：2 '天空'：3} freq_term_matrix = count_vectorizer.transform（TEST_SET）打印freq_term_matrix.todense（）＃[[0 1 1 1]＃[0 2 1 0]]

Now that we have the frequency term matrix (calledfreq_term_matrix），我们可以实例化TfidfTransformer，这将是负责来计算我们的词频矩阵TF-IDF权重：

from sklearn.feature_extraction.text import TfidfTransformer tfidf = TfidfTransformer(norm="l2") tfidf.fit(freq_term_matrix) print "IDF:", tfidf.idf_ # IDF: [ 0.69314718 -0.40546511 -0.40546511 0. ]

Note that I’ve specified the norm as L2, this is optional (actually the default is L2-norm), but I’ve added the parameter to make it explicit to you that it it’s going to use the L2-norm. Also note that you can see the calculated idf weight by accessing the internal attribute calledidf_。Now thatfit()method has calculated the idf for the matrix, let’s transform thefreq_term_matrixto the tf-idf weight matrix:

tf_idf_matrix = tfidf.transform(freq_term_matrix) print tf_idf_matrix.todense() # [[ 0. -0.70710678 -0.70710678 0. ] # [ 0. -0.89442719 -0.4472136 0. ]]

And that is it, thetf_idf_matrixis actually our previous$M_{tf\mbox{-}idf}$矩阵。您可以通过使用达到相同的效果矢量器Scikit的类。学习是一个vectorizer that automatically combines theCountVectorizerTfidfTransformer给你。看到这个例子要知道如何使用它的文本分类过程。

I really hope you liked the post, I tried to make it simple as possible even for people without the required mathematical background of linear algebra, etc. In the next Machine Learning post I’m expecting to show how you can use the tf-idf to calculate the cosine similarity.

Cite this article as: Christian S. Perone, "Machine Learning :: Text feature extraction (tf-idf) – Part II," in亚洲金博宝未知领域, 03/10/2011,//www.cpetem.com/2011/10/machine-learning-text-feature-extraction-tf-idf-part-ii/

### 参考

Understanding Inverse Document Frequency: on theoretical arguments for IDF

Wikipedia :: tf-idf

Sklearn text feature extraction code

13 Mar 2015Formating, fixed images issues.
03 Oct 2011添加了有关使用Python示例环境信息

## 103个想法“机器学习::文本特征提取（TF-IDF） - 第二部分”

1. Severtcev says:

Wow!
完美的前奏在TF-IDF，非常感谢你！亚洲金博宝亚洲金博宝很有意思，我想学这个领域很长一段时间，你的职位是一个真正的礼物。这将是非常有趣的阅读更多亚洲金博宝关于该技术的使用情况。而且可能是你有兴趣，请，摆脱对文本语料库表示的其他方法的一些光，如果他们存在？
(sorry for bad English, I’m working to improve it, but there is still a lot of job to do)

2. Excellent work Christian! I am looking forward to reading your next posts on document classification, clustering and topics extraction with Naive Bayes, Stochastic Gradient Descent, Minibatch-k-Means and Non Negative Matrix factorization

而且，scikit学习的文档上的文本特征提取部分（我是罪魁祸首？）真的很差。如果你想给一个手并改善目前的状况，不要犹豫，加入邮件列表。

1. 十分感谢奥利弗。我真的想帮助sklearn，我只是得到一些更多的时间来做到这一点，你们都做了伟大的工作，我真的在lib中已经实现的算法量折服，保持良好的工作！

3. I like this tutorial better for the level of new concepts i am learning here.
That said, which version of scikits-learn are you using?.
最新通过的easy_install安装似乎有不同的模块层次结构（即没有找到sklearn feature_extraction）。如果你能提到你使用的版本，我只是尝试用这些例子。

1. 您好阿南德，我很高兴你喜欢它。我已经增加了大约只用一节“的Python惯例”之前，我使用的是scikits.learn 0.9（发布在几个星期前）环境的信息。

4. siamii says:

哪里是第3部分？我必须提交在4天内向量空间模型的分配。把它在周末的希望吗？

1. I’ve no date to publish it since I haven’t got any time to write it =(

5. Niu says:

再次感谢这个完整和明确的教程和我在等待即将到来的部分。

6. Jason Wu says:

由于基督徒！与s亚洲金博宝klearn向量空间很不错的工作。我只有一个问题，假设我已经计算了“tf_idf_matrix”，我想计算成对余弦相似性（每行之间）。我是有问题的稀疏矩阵格式，你可以请给出这样的例子？也是我的基质是相当大的，由60K说25K。非常感谢！

7. Khalid says:

Great post… I understand what tf-idf and how to implement it with a concrete example. But I caught 2 things that I’m not sure about:
1- You called the 2 dimensional matrix M_train, but it has the tf values of the D3 and D4 documents, so you should’ve called that matrix M_test instead of M_train. Because D3 and D4 are our test documents.
2- When you calculate the idf value for the t2 (which is ‘sun’) it should be log(2/4). Because number of the documents is 2. D3 has the word ‘sun’ 1 time, D4 has it 2 times. Which makes it 3 but we also add 1 to that value to get rid of divided by 0 problem. And this makes it 4… Am I right or am I missing something?
Thank you.

1. Victoria says:

你是正确的：这些都是优秀的博客文章，但作者真的有责任/责任回去和纠正错误，这样的（和其他人，例如，第1部分; ...）：缺席训练下划线;设置STOP_WORDS参数;还我的电脑上，词汇索引是不同的。

正如我们赞赏的努力（荣誉的作者！），它也是一个显著伤害那些谁斗争过去在原有材料的（未修正）的错误。

1. Victoria says:

回复：我“你是正确的注释”（上），我应该补充：

“......还注意到康斯登Passot的评论（下同）关于分母：

‘… what we are using is really the number of documents in which a term occurs, regardless of the number of times the term occurs in any given document. In this case, then, the denominator in the idf value for t2 (‘sun’) is indeed 2+1 (2 documents have the term ‘sun’, +1 to avoid a potential zero division error).’ “

2. Yeshwant says:

Khalid,
This is a response to a very old question. However, I still want to respond to communicate what I understand from the article.
Your question 2: “When you calculate the idf value for the t2 (which is ‘sun’) it should be log(2/4)”
我的理解：在数项的分母应该是（一些文件，其中术语出现+ 1），而不是长期的频率。术语“太阳”出现的文件的数目是2（1次在D3和D4中的2倍 - 完全出现3次在两个文件3是频率和2是文件号）。因此，分母为2 + 1 = 3。

8. 阿尔苏 says:

感谢...优良的帖子...

9. 插口 says:

excellent post!
I have some question. From the last tf-idf weight matrix, how can we get the importance of term respectively(e.g. which is the most important term?). How can we use this matrix to classify documents

10. Thanuj says:

Thank You So Much. You explained it in such a simple way. It was really useful. Once again thanks a lot.

11. Thanuj says:

我有同样的疑问，杰克（最后的评论）。从上个TF-IDF权重矩阵，我们怎么能拿到各自任期的重要性（例如，这是最重要的用语？）。我们如何利用这个矩阵来区分文档。

12. 丁丁 says:

I have a question..
After the tf-idf operation, we get a numpy array with values. Suppose we need to get the highest 50 values from the array. How can we do that?

1. ashwin sudhini says:

F（IDF）的高值，表示特定载体（或文件）具有较高的局部强度和低全球实力，在这种情况下，你可以假设，在它的条款具有很高的重要性本地和不能忽视的。针对funtion（TF），其中只有长期重复大量的时间给予更多重视的那些，其中大部分时间是不正确的建模技术比较。

13. Vikram Bakhtiani says:

Hey ,
Thanx fr d code..was very helpful indeed !

1.For document clustering,after calculating inverted term frequency, shud i use any associativity coefficient like Jaccards coefficient and then apply the clustering algo like k-means or shud i apply d k-means directly to the document vectors after calculating inverted term frequency ?

2. How do u rate inverted term frequency for calcuating document vectors for document clustering ?

谢谢a ton fr the forth coming reply!

14. @Khalid：你在1-指出什么让我困惑过了一分钟（M_train VS M_test）。我想你误会了你的第二点，不过，因为我们用的是什么是真正发生的一个术语，无论任何给定的文档中出现的术语次数的文件数量。在这种情况下，那么，在为T2（“太阳”）的IDF值分母确实2 + 1（2个文件具有的术语“太阳”，1以避免潜在的零分割误差）。

我喜欢阅读本系列的第三批呢！我特别想了解更多有关特征选择。是否有一个惯用的方式来获得最高的分数TF.IDF条款的排序列表？你将如何确定这些方面的整体？你将如何得到这是最负责高或低的余弦相似度（逐行）的条款？

谢谢你的帖子_美好的_！

1. Bonnie Varghese says:

如果IDF（T2）进行登录2/4？

15. Matthys Meintjes says:

Excellent article and a great introduction to td-idf normalization.

You have a very clear and structured way of explaining these difficult concepts.

谢谢!

1. 谢谢for the feedback Matthys, I’m glad you liked the tutorial series.

1. PARAM says:

very good & infomative tutorial…. please upload more tutorials related to documents clustering process.

16. Laurent says:

Excellent article ! Thank you Christian. You did a great job.

17. Gavin Igor says:

您可以为使用TFIDF所以我们有TFIDF的矩阵，我们怎么可以用它来计算余弦做余弦相似度任何引用。感谢神奇的物品。

18. lavender says:

谢谢so much for this and for explaining the whole tf-idf thing thoroughly.

19. 请纠正我，如果我拨错
与启动后的公式“我们在第一个教程中计算出的频率：”应该不MTEST Mtrain。也开始“这些IDF权重可以由矢量作为表示后：”应该是不idf_test idf_train。

Btw great series, can you give an simple approach for how to implement classification?

20. Divya says:

优秀它真的帮助我度过VSM的概念和TF-IDF得到。由于基督教

21. Sergio says:

Very good post. Congrats!!

Showing your results, I have a question:

The tf-idf value increases proportionally to the number of times a word appears in the document, but is offset by the frequency of the word in the corpus, which helps to control for the fact that some words are generally more common than others.

当我看到它，我明白，如果一个字中的所有文档apperars就是一个字只出现在一个文档中不太重要的：

However, in the results, the word “sun” or “bright” are most important than “sky”.

I’m not sure of understand it completly.

22. Awesome! Explains TF-IDF very well. Waiting eagerly for your next post.

23. 有一个明确的解释真棒工作。即使是外行人容易理解的主题..

24. 苏珊 says:

Terrific! I was familiar with tf-idf before but I found your scikits examples helpful as I’m trying to learn that package.

25. Thank you for writing such a detailed post. I learn allot.

26. Eugene Chinveeraphan says:

Excellent post! Stumbled on this by chance looking for more information on CountVectorizer, but I’m glad I read through both of your posts (part 1 and part 2).

1. Great thanks for the feedback Eugene, I’m really glad you liked the tutorial series.

27. me says:

似乎没有fit_transform（）为你描述..
Any idea why ?
>>> ts
（“天空是蓝色的”，“阳光灿烂”）
>>> V7 = CountVectorizer（）
>>> v7.fit_transform(ts)
<2×2 sparse matrix of type '’
用4个存储元件在坐标格式>
>>> print v7.vocabulary_
{u’is’: 0, u’the’: 1}

1. says:

其实，还有第一个Python样本中的两个小错误。
1. CountVectorizer应该被实例化，如下所示：
count_vectorizer = CountVectorizer(stop_words='english')
This will make sure the ‘is’, ‘the’ etc are removed.

2. To print the vocabulary, you have to add an underscore at the end.
print "Vocabulary:", count_vectorizer.vocabulary_

Excellent tutorial, just small things. hoep it helps others.

1. Drogo says:

谢谢ash. although the article was rather self explanatory, your comment made the entire difference.

28. Kelvin John says:

29. I’m using scikit learn v .14. Is there any reason my results for running the exact same code would result in different results?

30. Karthik says:

感谢您抽出时间来写这篇文章。发现它非常有用。亚洲金博宝

31. 维杰 says:

Its useful…..thank you explaining the TD_IDF very elaborately..

32. Mike says:

感谢伟大的解释。

我有一个关于IDF（T＃）的计算问题。
在第一种情况下，你写的IDF（T1）=日志（2/1），因为我们没有我们收集此类条款，因此，我们添加1分母。现在，在T2的情况下，你写的日志（2/3），所以分母等于3，而不是4（= 1 + 2 + 1）？万一t3时，你写：日志（2/3），从而分母等于3（= 1 + 1 + 1）。我在这里看到的那种不一致性。你能不能，请解释一下，你是怎么计算的分母值。

谢谢。

1. Hello Mike, thanks for the feedback. You’re right, I just haven’t fixed it yet due to lack of time to review it and recalculate the values.

2. xpsycho says:

You got it wrong, in the denominator you don’t put the sum of the term in each document, you just sum all the documents that have at least one aparition of the term.

3. MIK says:

是的，我有同样的问题...

33. 胡达 says:

This is good post

34. 胡达 says:

it is good if you can provide way to know how use ft-idf in classification of document. I see that example (python code) but if there is algorithm that is best because no all people can understand this language.

谢谢

35. Ganesh says:

Great post, really helped me understand the tf-idf concept!

36. Samuel Kahn says:

漂亮的文章

37. Nice. An explanation helps put things into perspective. Is tf-idf a good way to do clustering (e.g. use Jaccard analysis or variance against the average set from a known corpus)?

继续写：）

38. 尼Prem says:

Hi Christian,

It makes me very excited and lucky to have read this article. The clarity of your understanding reflects in the clarity of the document. It makes me regain my confidence in the field of machine learning.

由于一吨为美丽的解释。

Would like to read more from you.

谢谢,

1. 大感谢那种wors尼！我很高兴亚洲金博宝你喜欢本系列教程。

39. esra'a OK says:

谢谢very very much,very wonderful and useful.

40. Arne says:

Thank you for the good wrap up. You mention a number of papers which compare L1 and L2 norm, I plan to study that a bit more in depth. You still know their names?

41. seher says:

how can i calculate tf idf for my own text file which is located some where in my pc?

42. Shubham says:

Brilliant article.

By far the easiest and most sound explanation of tf-tdf I’ve read. I really liked how you explained the mathematics behind it.

43. mehrab says:

精湛的文章新手

1. Dayananda says:

Excellent material. Excellent!!!

44. Derrick says:

嗨，great post! I’m using the TfidVectorizer module in scikit learn to produce the tf-idf matrix with norm=l2. I’ve been examining the output of the TfidfVectorizer after fit_transform of the corpora which I called tfidf_matrix. I’ve summed the rows but they do not sum to 1. The code is vect = TfidfVectorizer(use_idf=True, sublunar_tf=True, norm=”l2). tfidf_matrix = vect.fit_transform(data). When I run tfidf_matrix.sum(axis=1) the vectors are larger than 1. Perhaps I’m looking at the wrong matrix or I misunderstand how normalisation works. I hope someone can clarify this point! Thanks

45. Chris says:

Can I ask when you calculated the IDF, for example, log(2/1), did you use log to base 10 (e) or some other value? I’m getting different calculations!

46. 贡萨洛·g ^ says:

伟大的教程,刚开始一份新工作在毫升和this explains things very clearly as it should be.

47. Harsimranpal says:

Execellent帖子...。！非常感谢这篇文章。

But I need more information, As you show the practical with python, Can you provide it with JAVA language..

48. 塞巴斯蒂安 says:

我有点困惑为什么tf-idf negative numbers in this case? How do we interpret them? Correct me if I am wrong, but when the vector has a positive value, it means that the magnitude of that component determines how important that word is in that document. If the it is negative, I don’t know how to interpret it. If I were to take the dot product of a vector with all positive components and one with negative components, it would mean that some components may contribute negatively to the dot product even though on of the vectors has very high importance for a particular word.

49. 嗨，
谢谢so much for this detailed explanation on this topic, really great. Anyway, could you give me a hint what could be the source of my error that I am keep on seeing:

freq_term_matrix = count_vectorizer.transform(test_set)
AttributeError: ‘matrix’ object has no attribute ‘transform’

Am I using a wrong version of sklearn?

50. 莫希特古普塔 says:

谢谢

51. Alexandro says:

谢谢克里斯，你是唯一一个谁是明确了对角矩阵在网络上。

52. ishpreet says:

伟大的教程TF-IDF。优秀作品 。请添加对余弦相似性也:)

53. sherlockatsz says:

I understood the tf-idf calculation process. But what does that matrix mean and how can we use the tfidf matrix to calculate the similarity confuse me. can you explain that how can we use the tfidf matrix .thanks

54. lightningstrike says:

55. 匿名 says:

谢谢，好贴，我想它了

56. 匿名 says:

Thank you so much for such an amazing detailed explanation!

57. Akanksha Pande says:

best explanation.. Very helpful. Can you please tell me how to plot vectors in text classification in svm.. I am working on tweets classification. I am confused please help me.

58. 科希克 says:

I learned so many things. Thanks Christian. Looking forward for your next tutorial.

59. MHR says:

嗨，I’m sorry if i have mistaken but i could not understand how is ||Vd4||2 = 1.
the value of d4 = (0.0 ,0.89,0.44,0.0) so the normalization will be = sqrt( square(.89)+square(.44))=sqrt(.193) = .44
所以我有没有遗漏了什么？请帮我明白了。

60. Cuiqing Li says:

嗨，it is a great blog!
If I need to do bi-gram cases, how can I use sklearn to finish it?

61. 阿里 says:

这是非常大的亚洲金博宝。我喜欢你教。亚洲金博宝非常非常棒

62. 仅限Ritesh says:

我没有得到相同的结果，当我执行相同的脚本。
print (“IDF:”, tfidf.idf_) : IDF: [ 2.09861229 1. 1.40546511 1. ]

我的Python版本：3.5
Scikit Learn version is: o.18.1

什么我需要改变？可能是什么可能的错误？

thanks,

1. 它可以很多东西,因为你正在使用一个不同ent Python interpreter version and also a different Scikit-Learn version, you should expect differences in the results since they may have changed default parameters, algorithms, rounding, etc.

1. Ravithej Chikkala says:

I am also getting: IDF: [2.09861229 1. 1.40546511 1. ]

63. Victor says:

Perfect introduction!
No hocus pocus. Clear and simple, as technology should be.
Thank you very much.
请发帖！

64. Hitesh Nankani says:

Why is |D| = 2, in the idf equation. Shouldn’t it be 4 since |D| denotes the number of documents considered, and we have 2 from test, 2 from train.

65. 黎文禅师 says:

This post is interesting. I like this post…

66. Bren says:

clear cut and to the point explanations….great

67. Shipika Singh says:

hey , hii Christian
您的文章是真正帮助我了解从基础TFD-IDF。我在分类的一个项目，其中我使用向量空间模型，这导致在确定类别在我的测试文档应该存在。机器学习的一部分。如果你认为我有关的东西这将是巨大的。我被困在这一点上。
谢谢

68. Eshwar期基于g says:

看到这个例子要知道如何使用它的文本分类过程。“This” link does not work any more. Can you please provide a relevant link for the example.

谢谢

69. amanda says:

这样一个伟大的解释！谢谢！

70. alternative investing says:

哇，真棒post.Much再次感谢。将阅读

Say, you got a nice post.Really thank you! Fantastic.

72. togel online says:

Wow, great article post.Much thanks again. Awesome.

73. 手机电脑 says:

当然有很大的了解这个问题。我真的很喜欢所有的点，你做。

74. chocopie says:

1vbXlh你提出了一个非常美妙的细节，欣赏它的职位。亚洲金博宝

75. I know this site provides quality based articles or
评论和其他数据，还有没有其他的网页呈现这类
在质量信息？

76. 鲁塞 says:

In the first example. idf(t1), the log (2/1) = 0.3010 by the calculator. Why they obtained 0.69.. Please What is wrong?

This site uses Akismet to reduce spam.Learn how your comment data is processed


text:
# Molar conductivity and conductivity of an electrolyte

if ∧m = ∧mo - A√c
then till where is this formula ∧m = κ/c applicable because if for infinite dilution c = 0 it gives molar conductivity infinite.

Please explain how conductivity and molar conductivity varies with concentration of electrolyte.

format: plain


text:
# Beyond Python¶

This is a small collection of thoughts related to the inclusion of code written in languages other than Python. Currently, the only option for languages other than Python that is explicitly documented is Cython.

Can I use a programming language other than Python to speed up my code?

Yes. The languages used in SciPy are Python, Cython, C, C++, and Fortran. All of these have their pros and cons. If Python really doesn’t offer enough performance, one of those languages can be used. Important concerns when using compiled languages are maintainability and portability. For maintainability, Cython is clearly preferred over C/C++/Fortran. Cython and C are more portable than C++/Fortran. A lot of the existing C and Fortran code in SciPy is older, battle-tested code that was only wrapped in (but not specifically written for) Python/SciPy. Therefore, the basic advice is: use Cython. If there are specific reasons why C/C++/Fortran should be preferred, please discuss those reasons first.

Can I use Numba or Pythran?

Not yet, but we’re considering it for the future.

How do I debug code written in C/C++/Fortran inside SciPy?

The easiest way to do this is to first write a Python script that invokes the C code whose execution you want to debug. For instance mytest.py:

from scipy.special import hyp2f1
print(hyp2f1(5.0, 1.0, -1.8, 0.95))

Now, you can run:

gdb --args python runtests.py -g --python mytest.py

If you didn’t compile with debug symbols enabled before, remove the build directory first. While in the debugger:

(gdb) break cephes_hyp2f1
(gdb) run

The execution will now stop at the corresponding C function and you can step through it as usual. Instead of plain gdb you can, of course, use your favorite alternative debugger; run it on the python binary with arguments runtests.py -g --python mytest.py.


text:
Algebra: A Combined Approach (4th Edition)

$a^{2}$ + 9a + 20
( a + 5 ) ( a + 4 ) use the commutative and associative properties multiply (a)(a) +(a)(4) +( 5)(a) + (5)(4) FOIL method $a^{2}$ + 4a + 5a + 20 $a^{2}$ + 9a + 20


text:
All notes
Logrota

# Configuration

sharedscripts: the postrotate script will only be run once, not once for each log which is rotated.
notifempty: Do not rotate the log if it is empty (this overrides the ifempty option).

/var/log/warn /var/log/messages /var/log/allmessages /var/log/localmessages
/var/log/firewall /var/log/acpid /var/log/NetworkManager
/var/log/mail /var/log/mail.info /var/log/mail.warn /var/log/mail.err
/var/log/news/news.crit /var/log/news/news.err /var/log/news/news.notice
{
compress
dateext
maxage 365
rotate 99
missingok
notifempty
size +4096k
create 640 root root
sharedscripts
postrotate
endscript
}

## wildcards

/var/log/httpd/*.log /var/log/httpd/*/*.log {
# ... same as above
}

You can test your file without performing the actual rotations by doing this:

logrotate -d -f /etc/logrotate.conf
# -d = Turns on debug mode. In debug mode, no changes will be made to the logs or to the logrotate state file.
# -f = Tells logrotate to force the rotation, even if it doesn’t think this is necessary.

## daily

### How does logrotate handle daily

It uses the status file "/var/lib/logrotate.status", with content like:

"/var/log/dracut.log" 2016-12-8-2:0:0

From the logrotate man page:

Normally, logrotate is run as a daily cron job. It will not modify a log more than once in one day unless the criterion for that log is based on the log's size and logrotate is being run more than once each day, or unless the -f or -force option is used.

## dateext, dateformat

dateext
dateformat -%Y%m%d-%s

dateext: rotate by appending a date extension like YYYYMMDD. The extension may be configured using the "dateformat" and "dateyesterday" options.

dateformat format_string: Use the notation similar to strftime(3) function.
Only %Y %m %d and %s specifiers are allowed. The default value is -%Y%m%d. The system clock must be set past Sep 9th 2001 for %s to work correctly. %s: The number of seconds since the Epoch, 1970-01-01.
Note that also the character separating log name from the extension is part of the dateformat string.
Note that the datestamps generated by this format must be lexically sortable (i.e., first the year, then the month then the day. e.g., 2001/12/01 is ok, but 01/12/2001 is not, since 01/11/2002 would sort lower while it is later). This is because when using the rotate option, logrotate sorts all rotated filenames to find out which logfiles are older and should be removed.

dateyesterday: Use yesterday's instead of today's date to create the dateext extension, so that the rotated log file has a date in its name that is the same as the timestamps within it.

## delaycompress

delaycompress: compression is delayed until the next rotation.

## rotate

When using the rotate option, logrotate sorts all rotated filenames to find out which logfiles are older and should be removed.

"rails.debug.1" will always be the second newest. Then rails.debug.2.bz2, .... 所以它是每次把所有文件重命名一下？

# if "rotate 10"

-rw-r--r-- 1 root root 52 Aug 30 18:05 /var/log/rails.debug.10.bz2
-rw-r--r-- 1 root root 52 Aug 30 18:05 /var/log/rails.debug.9.bz2
-rw-r--r-- 1 root root 52 Aug 30 18:05 /var/log/rails.debug.8.bz2
-rw-r--r-- 1 root root 52 Aug 30 18:05 /var/log/rails.debug.7.bz2
-rw-r--r-- 1 root root 52 Aug 30 18:05 /var/log/rails.debug.6.bz2
-rw-r--r-- 1 root root 52 Aug 30 18:05 /var/log/rails.debug.5.bz2
-rw-r--r-- 1 root root 52 Aug 30 18:05 /var/log/rails.debug.4.bz2
-rw-r--r-- 1 root root 58 Aug 30 18:05 /var/log/rails.debug.3.bz2
-rw-r--r-- 1 root root 58 Aug 30 18:06 /var/log/rails.debug.2.bz2
-rw-r--r-- 1 root root 19 Aug 30 18:13 /var/log/rails.debug.1
-rw-r--r-- 1 root root  0 Aug 30 18:13 /var/log/rails.debug

## size, minsize, maxsize

size:
Log files are rotated only if they grow bigger then size bytes.
It is mutually exclusive with the time interval options, and it causes log files to be rotated without regard for the last rotation time.

minsize:
Log files are rotated when they grow bigger than size bytes, but not before the additionally specified time interval (daily, weekly, monthly, or yearly).
Both the size and timestamp of a log file are considered.

maxsize:
Log files are rotated when they grow bigger than size bytes even before the additionally specified time interval (daily, weekly, monthly, or yearly).
Both the size and timestamp of a log file are considered.

size 200G / 50M / 100K

See SO, esp "Matt"'s comment is good written.

## maxage

logrotate maxage option for log keeping dates?

"maxage count". Remove rotated logs older than "count" days. The age is only checked if the logfile is to be rotated.

# Best practices

## Hourly logrotation

TODO: it's not hourly logrotation?

/tmp/hr_logs {
daily
rotate 4
}
// With this config, /tmp/hr_logs will rotate on daily basis and system will keep 4 copies of the log file appended with date [format: -YYYYMMDD].

## How to handle with old logs if config is changed?

For example, dateformat is changed from "-%Y%m%d-%s" to "-%Y%m%d". How to handle with old logs?

Rename old logs from e.g. "syslog-20160109" to "syslog-20160109-123456789".

What if rotation frequency is changed, e.g. from daily to 6hourly?

Daily has 1 log saved each day, while 6hourly has 4 logs.
Solution: Add 3 extra small bogus logs with the same naming style.


text:
# Summations manipulation: is this one right?

I've got a summation like this:

$\sum_{l=1}^L \sum_{i=1}^I p_l c_l^i = \sum_{l=1}^L \sum_{i=1}^I p_l w_l^i$

Is it right to bring $p_l$ out of the symbol $\sum_{i=1}^I$ such that:

$\sum_{l=1}^L p_l \sum_{i=1}^I c_l^i = \sum_{l=1}^L p_l \sum_{i=1}^I w_l^i$ ?

Thank you in advance

-
Since the $p_l$ is not dependent on the innermost summation index, it should be fine... –  Ｊ. Ｍ. Jul 7 '12 at 14:18

Yes that is correct. Since the $p_l$ does not depend on $i$, you can bring it out. For a fixed $l$ the $p_l$ is just a common factor of all the terms in the sum $\sum_{i=1}^I$ where $i$ varies.


text:
# The $p^k$-rank of a subgroup is no greater than the $p^k$-rank of the group.

Recently I was given a handout containing (roughly) the following text:

Let $A$ be a finite abelian group, and $p^k$ a prime power. The $p^k$-rank of $A$ is defined to be $$\operatorname{rank}_{p^k}(A):=\operatorname{dim}_{\mathbb{F}_p}(p^{k-1}A/p^kA).$$ It is immediate from the definition that for any subgroup $B\subseteq A$ and any prime power $p^k$ $$\operatorname{rank}_{p^k}(B)\leq\operatorname{rank}_{p^k}(A).$$

However, I do not see how this follows from the definition. Any suggestions?

-

For the sake of simplicity we consider only the case $k=1$. We have to show $\dim_{\mathbb F_p}(B/pB) \leq \dim_{\mathbb F_p}(A/pA)$. Note that this is equivalent to $|B/pB| \leq |A/pA|$. Consider the exact sequence $$0 \to {}_pA \to A \to pA \to 0$$ where $A \to pA$ is multiplication by $p$ and ${}_p A = \{ a \in A : pa = 0 \}$ is its kernel. The exactness implies $|A| = |{}_pA| |pA|$ and similarly $|B| = |{}_pB| |pB|$. Since ${}_p B \subseteq {}_p A$, we get $$|B/pB| = |B|/|pB| = |{}_pB| \leq |{}_p A| = |A|/|pA| = |A/pA|.$$


text: dc.date.accessioned 2020-10-29T11:54:33Z dc.date.available 2020-10-29T11:54:33Z dc.date.issued 2020-10-29 dc.identifier.uri http://hdl.handle.net/123456789/31852 dc.title Two results on the essential self-adjointness of the Schrödinger operator en ethesis.discipline none und ethesis.department none und ethesis.faculty Matemaattis-luonnontieteellinen tiedekunta fi ethesis.faculty Faculty of Science en ethesis.faculty Matematisk-naturvetenskapliga fakulteten sv ethesis.faculty.URI http://data.hulib.helsinki.fi/id/8d59209f-6614-4edd-9744-1ebdaf1d13ca ethesis.university.URI http://data.hulib.helsinki.fi/id/50ae46d8-7ba9-4821-877c-c994c78b0d97 ethesis.university Helsingin yliopisto fi ethesis.university University of Helsinki en ethesis.university Helsingfors universitet sv dct.creator Nyberg, Jonne dct.issued 2020 dct.language.ISO639-2 eng dct.abstract Spectral theory is a powerful tool when applied to differential equations. The fundamental result being the spectral theorem of Jon Von Neumann, which allows us to define the exponential of an unbounded operator, provided that the operator in question is self-adjoint. The problem we are considering in this thesis, is the self-adjointness of the Schr\"odinger operator $T = -\Delta + V$, a linear second-order partial differential operator that is fundamental to non-relativistic quantum mechanics. Here, $\Delta$ is the Laplacian and $V$ is some function that acts as a multiplication operator. en We will study $T$ as a map from the Hilbert space $H = L^2(\mathbb{R}^d)$ to itself. In the case of unbounded operators, we are forced to restrict them to some suitable subspace. This is a common limitation when dealing with differential operators such as $T$ and the choice of the domain will usually play an important role. Our aim is to prove two theorems on the essential self-adjointness of $T$, both originally proven by Tosio Kato. We will start with some necessary notation fixing and other preliminaries in chapter 2. In chapter 3 basic concepts and theorems on operators in Hilbert spaces are presented, most importantly we will introduce some characterisations of self-adjointness. In chapter 4 we construct the test function space $D(\Omega)$ and introduce distributions, which are continuous linear functionals on $D(\Omega).$ These are needed as the domain for the adjoint of a differential operator can often be expressed as a subspace of the space of distributions. In chapter 5 we will show that $T$ is essentially self-adjoint on compactly supported smooth functions when $d=3$ and $V$ is a sum consisting of an $L^2$ term and a bounded term. This result is an application of the Kato-Rellich theorem which pertains to operators of the form $A+B$, where $B$ is bounded by $A$ in a suitable way. Here we will also need some results from Fourier analysis that will be revised briefly. In chapter 6 we introduce some mollification methods and prove Kato's distributional inequality, which is important in the proof of the main theorem in the final chapter and other results of similar nature. The main result of this thesis, presented in chapter 7, is a theorem originally conjectured by Barry Simon which says that $T$ is essentially self-adjoint on $C^\infty_c(\mathbb{R}^d)$, when $V$ is a non-negative locally square integrable function and $d$ is an arbitrary positive integer. The proof is based around mollification methods and the distributional inequality proven in the previous chapter. This last result, although fairly unphysical, is somewhat striking in the sense that usually for $T$ to be (essentially) self-adjoint, the dimension $d$ restricts the integrability properties of $V$ significantly. dct.subject Hilbert spaces dct.subject Schrödinger operators dct.subject Self-adjointness dct.subject Distribution theory dct.subject Kato's inequality dct.language en ethesis.isPublicationLicenseAccepted true ethesis.language.URI http://data.hulib.helsinki.fi/id/languages/eng ethesis.language englanti fi ethesis.language English en ethesis.language engelska sv ethesis.thesistype pro gradu -tutkielmat fi ethesis.thesistype master's thesis en ethesis.thesistype pro gradu-avhandlingar sv ethesis.thesistype.URI http://data.hulib.helsinki.fi/id/thesistypes/mastersthesis dct.identifier.ethesis E-thesisID:2b78f918-cf01-45bb-b5ea-e5bb6d167e06 dct.identifier.urn URN:NBN:fi:hulib-202010294365 dc.type.dcmitype Text ethesis.facultystudyline Matematiikka fi ethesis.facultystudyline Mathematics en ethesis.facultystudyline Matematik sv ethesis.facultystudyline.URI http://data.hulib.helsinki.fi/id/SH50_050 ethesis.mastersdegreeprogram Matematiikan ja tilastotieteen maisteriohjelma fi ethesis.mastersdegreeprogram Master's Programme in Mathematics and Statistics en ethesis.mastersdegreeprogram Magisterprogrammet i matematik och statistik sv ethesis.mastersdegreeprogram.URI http://data.hulib.helsinki.fi/id/MH50_001


text:
### Home > CC2MN > Chapter 10 > Lesson 10.2.1 > Problem10-25

10-25.

Copy the axes below and complete the scales.

Remember that where the $x\text{-}$ and $y\text{-axes}$ intersect is always $0$. To scale the $x\text{-axis}$ in part (a), you should try dividing $12$ by $3$, since that is the number of spaces between $0$ and $12$.

The $x\text{-axes}$ for parts (a) and (b) are labeled below. Were you able to scale the $y\text{-axes}$?


text:
Segmentation fault with HOMER
0
0
Entering edit mode
7 months ago
pixie@bioinfo ★ 1.4k

Hello, I am analyzing captureHiC data with HOMER by using the findHiCInteractionsByChr.pl module. I am running it as an sbatch script with the following parameters:

findHiCInteractionsByChr.pl $folder/ -res 2000 -pvalue 0.05 -zscore 0.5 -cpu 24 >$output/basename \$folder_Interactions_byChr.txt"

However, I keep getting these segmentation faults in my error file. Although it gives me a list of significant loops, I do not know if the list is complete. Can anyone throw some light on this issue ? Is it because of memory problem ?

Average interaction count in regions = 153.4 +/- 180.2 (143.4 without outliers)
Chr6 (avg coverage: 143.4, coverage ratio=1.051)

Regions with too many or too few reads: 2.43%
Total Significant Interactions: 6354
Reporting log2 values
Segmentation fault
Regions with too many or too few reads: 8.09%
Total Significant Interactions: 3350
Reporting log2 values
Segmentation fault

homer HiC • 228 views


text:
h2o.downloadAllLogs downloads all H2O log files to local disk in .zip format. Generally used for debugging purposes.

h2o.downloadAllLogs(dirname = ".", filename = NULL)

## Arguments

dirname (Optional) A character string indicating the directory that the log file should be saved in. (Optional) A character string indicating the name that the log file should be saved to. Note that the saved format is .zip, so the file name must include the .zip extension.

## Examples

# NOT RUN {
# }


text:
# Differentiate the functions with respect to x.

Question:

Differentiate the functions with respect to x.

$\frac{\sin (a x+b)}{\cos (c x+d)}$

Solution:

The given function is $f(x)=\frac{\sin (a x+b)}{\cos (c x+d)}=\frac{g(x)}{h(x)}$, where $g(x)=\sin (a x+b)$ and

$h(x)=\cos (c x+d)$

$\therefore f^{\prime}=\frac{g^{\prime} h-g h^{\prime}}{h^{2}}$

Consider $g(x)=\sin (a x+b)$

Let $u(x)=a x+b, v(t)=\sin t$

Then, $(v o u)(x)=v(u(x))=v(a x+b)=\sin (a x+b)=g(x)$

∴ is a composite function of two functions, u and v.

Put $t=u(x)=a x+b$

$\frac{d v}{d t}=\frac{d}{d t}(\sin t)=\cos t=\cos (a x+b)$

$\frac{d t}{d x}=\frac{d}{d x}(a x+b)=\frac{d}{d x}(a x)+\frac{d}{d x}(b)=a+0=a$

Therefore, by chain rule, we obtain

$g^{\prime}=\frac{d g}{d x}=\frac{d v}{d t} \cdot \frac{d t}{d x}=\cos (a x+b) \cdot a=a \cos (a x+b)$

Consider $h(x)=\cos (c x+d)$

Let $p(x)=c x+d, q(y)=\cos y$

Then, $(q o p)(x)=q(p(x))=q(c x+d)=\cos (c x+d)=h(x)$

h is a composite function of two functions, p and q.

Put y = p (x) = cx d

$\frac{d q}{d y}=\frac{d}{d y}(\cos y)=-\sin y=-\sin (c x+d)$

$\frac{d y}{d x}=\frac{d}{d x}(c x+d)=\frac{d}{d x}(c x)+\frac{d}{d x}(d)=c$

Therefore, by chain rule, we obtain

$h^{\prime}=\frac{d h}{d x}=\frac{d q}{d y} \cdot \frac{d y}{d x}=-\sin (c x+d) \times c=-c \sin (c x+d)$

$\therefore f^{\prime}=\frac{a \cos (a x+b) \cdot \cos (c x+d)-\sin (a x+b)\{-c \sin (c x+d)\}}{[\cos (c x+d)]^{2}}$

$=\frac{a \cos (a x+b)}{\cos (c x+d)}+c \sin (a x+b) \cdot \frac{\sin (c x+d)}{\cos (c x+d)} \times \frac{1}{\cos (c x+d)}$

$=a \cos (a x+b) \sec (c x+d)+c \sin (a x+b) \tan (c x+d) \sec (c x+d)$


text:
Minimum steps to spread stones on a grid

Revision en4, by cuom1999, 2020-11-12 00:36:35

Here is an interesting problem for Vietnam Informatics Competition for Youth:

Given a board $m \times n \ (m, n \leq 10^6)$. You know $q (q \leq 10^6)$ information: square $(x_i, y_i)$ contains $a_i \ (a_i \leq 10^9)$ stones. Other unlisted squares contain $0$ stones. In one step, you could move one stone to an adjacent square, which shares an edge with the current square. The task is to spread stones equally to every square. For example, it takes 2 steps to make [[0, 0], [2, 2]] become [[1, 1], [1, 1]].

I could only model this as a min-cost max-flow problem and solve for small $m, n$. How to solve the full problem?

#### History

Revisions

Rev. Lang. By When Δ Comment
en4 cuom1999 2020-11-12 00:36:35 14 Tiny change: 'ou know $q$ informat' -> 'ou know $q (q \leq 10^6)$ informat'
en3 cuom1999 2020-11-11 22:41:20 8
en2 cuom1999 2020-11-11 22:40:46 9 Tiny change: 'es. Other squares c' -> 'es. Other unlisted squares c'
en1 cuom1999 2020-11-11 22:40:05 638 Initial revision (published)


text:
# If you were out in space, motionless

1. May 6, 2010

### taybot

If you were in a spaceship going the speed of light you wouldn't travel through time because you would be traveling through space instead. I got that.

So if you were to sit out in space completely free from gravity, motionless, and you were wearing a watch, does that mean time would go faster?

Since you aren't traveling through space at all, wouldn't that mean you are traveling through time at light speed and wouldn't that mean your watch would go faster?

2. May 6, 2010

### Staff: Mentor

No, you wouldn't be going the speed of light because you have mass.

In in any inertial frame the rate of any watch's proper time wrt coordinate time would be given by:
$$\frac{d\tau}{dt}=\frac{1}{\gamma}=\sqrt{1-\frac{v^2}{c^2}}$$

This expression indeed achieves a maximum of 1 for v=0.

3. May 6, 2010

### taybot

not sure what that formula means but since you wrote indeed, I take it that the watch will tick faster if you are out in space, motionless...

So how much faster? I figure it wouldn't be that much faster than normal time that passes for us, right?

Because already if you are sitting somewhere, you're accelerating through space, just not accelerating that much I figure, so probably your watch wouldn't tick that much faster if you were out in space, motionless.

Is that right?

4. May 6, 2010

### Staff: Mentor

Sorry, I don't know I can answer you in a satisfactory manner then. The answer to "how much faster" is given by the formula.

5. May 6, 2010

### Mentz114

What do you mean by motionless ? I think you are failing to take into account that phenomena like clocks slowing refer to observations from different frames of reference. You would not notice anything as long as your motion is uniform ( unaccelerated).

But someone travelling at uniform velocity relative to you would notice your clock apparently slowing.

6. May 6, 2010

### Matterwave

You can never be motionless with respect to every reference frame. In some reference frame you are motionless, and in others you are moving. I don't think your question can obtain a satisfactory answer because one of your assumptions is wrong.

7. May 6, 2010

### taybot

I read this book, The Fabric of the Cosmos and he says you can be motionless if you jump into a shaft that has air removed from it.

Even if you can't be motionless, you would be falling, pretty much motionless. Closer to motionless than when you are sitting in front of your computer, because if you're doing that, you're accelerating.

Anyways, let's say you jump into that airless shaft and you are falling, motionless, or almost motionless. And if you're wearing a watch, would it tick faster, or wouldn't it?

Edit:

I looked at Dale's answer again and he says:

"The answer to "how much faster" is given by the formula."

So at least I know your watch would indeed tick faster. I was just wondering if it would tick twice as fast, or less. I don't know how to do that equation. Thanks!

8. May 7, 2010

### yuiop

The watch on your wrist always appears to tick at the same rate whether you are motionless far out in space or on the surface of a neutron star or in a rocket travelling at 0.999c relative to the Earth. It is the rate of other clocks moving relative to you or located at different heights in a gravitational field that appear to be running faster or slower than your own watch.

Using the equation given by Dale, the rate of a clock moving at at 0.866c relative to you is:

$$\frac{d\tau}{dt}=\frac{1}{\gamma}=\sqrt{1-\frac{v^2}{c^2}} = \sqrt{1-0.866^2} \approx 1/2$$

In other words the clock moving at 0.866c relative to you appears to be ticking twice as slow as your watch, but this factor of 2 only happens at this precise velocity relative to you. If the other clock was moving at 0.99498c relative to you, then the other clock would appear to be running 10 times slower than your own watch because:

$$\frac{d\tau}{dt}=\frac{1}{\gamma}=\sqrt{1-\frac{v^2}{c^2}} = \sqrt{1-0.99498^2} \approx 1/10$$


text:
Definitions

# computer-graphics

Rendering is the process of generating an image from a model, by means of computer programs. The model is a description of three dimensional objects in a strictly defined language or data structure. It would contain geometry, viewpoint, texture, lighting, and shading information. The image is a digital image or raster graphics image. The term may be by analogy with an "artist's rendering" of a scene. 'Rendering' is also used to describe the process of calculating effects in a video editing file to produce final video output.

It is one of the major sub-topics of 3D computer graphics, and in practice always connected to the others. In the graphics pipeline, it is the last major step, giving the final appearance to the models and animation. With the increasing sophistication of computer graphics since the 1970s onward, it has become a more distinct subject.

Rendering has uses in architecture, video games, simulators, movie or TV special effects, and design visualization, each employing a different balance of features and techniques. As a product, a wide variety of renderers are available. Some are integrated into larger modeling and animation packages, some are stand-alone, some are free open-source projects. On the inside, a renderer is a carefully engineered program, based on a selective mixture of disciplines related to: light physics, visual perception, mathematics, and software development.

In the case of 3D graphics, rendering may be done slowly, as in pre-rendering, or in real time. Pre-rendering is a computationally intensive process that is typically used for movie creation, while real-time rendering is often done for 3D video games which rely on the use of graphics cards with 3D hardware accelerators.

## Usage

When the pre-image (a wireframe sketch usually) is complete, rendering is used, which adds in bitmap textures or procedural textures, lights, bump mapping, and relative position to other objects. The result is a completed image the consumer or intended viewer sees.

For movie animations, several images (frames) must be rendered, and stitched together in a program capable of making an animation of this sort. Most 3D image editing programs can do this.

## Features

A rendered image can be understood in terms of a number of visible features. Rendering research and development has been largely motivated by finding ways to simulate these efficiently. Some relate directly to particular algorithms and techniques, while others are produced together.

• shading — how the color and brightness of a surface varies with lighting
• texture-mapping — a method of applying detail to surfaces
• bump-mapping — a method of simulating small-scale bumpiness on surfaces
• fogging/participating medium — how light dims when passing through non-clear atmosphere or air
• shadows — the effect of obstructing light
• soft shadows — varying darkness caused by partially obscured light sources
• reflection — mirror-like or highly glossy reflection
• transparency, transparency or opacity — sharp transmission of light through solid objects
• translucency — highly scattered transmission of light through solid objects
• refraction — bending of light associated with transparency
• diffraction — bending, spreading and interference of light passing by an object or aperture that disrupts the ray
• indirect illumination — surfaces illuminated by light reflected off other surfaces, rather than directly from a light source (also known as global illumination)
• caustics (a form of indirect illumination) — reflection of light off a shiny object, or focusing of light through a transparent object, to produce bright highlights on another object
• depth of field — objects appear blurry or out of focus when too far in front of or behind the object in focus
• motion blur — objects appear blurry due to high-speed motion, or the motion of the camera
• non-photorealistic rendering — rendering of scenes in an artistic style, intended to look like a painting or drawing

## Techniques

Many rendering algorithms have been researched, and software used for rendering may employ a number of different techniques to obtain a final image.

Tracing every ray of light in a scene is impractical and would take an enormous amount of time. Even tracing a portion large enough to produce an image takes an inordinate amount of time if the sampling is not intelligently restricted.

Therefore, four loose families of more-efficient light transport modelling techniques have emerged: rasterisation, including scanline rendering, geometrically projects objects in the scene to an image plane, without advanced optical effects; ray casting considers the scene as observed from a specific point-of-view, calculating the observed image based only on geometry and very basic optical laws of reflection intensity, and perhaps using Monte Carlo techniques to reduce artifacts; radiosity uses finite element mathematics to simulate diffuse spreading of light from surfaces; and ray tracing is similar to ray casting, but employs more advanced optical simulation, and usually uses Monte Carlo techniques to obtain more realistic results at a speed that is often orders of magnitude slower.

Most advanced software combines two or more of the techniques to obtain good-enough results at reasonable cost.

### Scanline rendering and rasterisation

A high-level representation of an image necessarily contains elements in a different domain from pixels. These elements are referred to as primitives. In a schematic drawing, for instance, line segments and curves might be primitives. In a graphical user interface, windows and buttons might be the primitives. In 3D rendering, triangles and polygons in space might be primitives.

If a pixel-by-pixel approach to rendering is impractical or too slow for some task, then a primitive-by-primitive approach to rendering may prove useful. Here, one loops through each of the primitives, determines which pixels in the image it affects, and modifies those pixels accordingly. This is called rasterization, and is the rendering method used by all current graphics cards.

Rasterization is frequently faster than pixel-by-pixel rendering. First, large areas of the image may be empty of primitives; rasterization will ignore these areas, but pixel-by-pixel rendering must pass through them. Second, rasterization can improve cache coherency and reduce redundant work by taking advantage of the fact that the pixels occupied by a single primitive tend to be contiguous in the image. For these reasons, rasterization is usually the approach of choice when interactive rendering is required; however, the pixel-by-pixel approach can often produce higher-quality images and is more versatile because it does not depend on as many assumptions about the image as rasterization.

The older form of rasterization is characterized by rendering an entire face (primitive) as a single color. Alternatively, rasterization can be done in a more complicated manner by first rendering the vertices of a face and then rendering the pixels of that face as a blending of the vertex colors. This version of rasterization has overtaken the old method as it allows the graphics to flow without complicated textures (a rasterized image when used face by face tends to have a very block-like effect if not covered in complex textures; the faces aren't smooth because there is no gradual color change from one primitive to the next). This newer method of rasterization utilizes the graphics card's more taxing shading functions and still achieves better performance because the simpler textures stored in memory use less space. Sometimes designers will use one rasterization method on some faces and the other method on others based on the angle at which that face meets other joined faces, thus increasing speed and not hurting the overall effect.

### Ray casting

Ray casting is primarily used for realtime simulations, such as those used in 3D computer games and cartoon animations, where detail is not important, or where it is more efficient to manually fake the details in order to obtain better performance in the computational stage. This is usually the case when a large number of frames need to be animated. The resulting surfaces have a characteristic 'flat' appearance when no additional tricks are used, as if objects in the scene were all painted with matte finish.

The geometry which has been modeled is parsed pixel by pixel, line by line, from the point of view outward, as if casting rays out from the point of view. Where an object is intersected, the color value at the point may be evaluated using several methods. In the simplest, the color value of the object at the point of intersection becomes the value of that pixel. The color may be determined from a texture-map. A more sophisticated method is to modify the colour value by an illumination factor, but without calculating the relationship to a simulated light source. To reduce artifacts, a number of rays in slightly different directions may be averaged.

Rough simulations of optical properties may be additionally employed: a simple calculation of the ray from the object to the point of view is made. Another calculation is made of the angle of incidence of light rays from the light source(s), and from these as well as the specified intensities of the light sources, the value of the pixel is calculated. Another simulation uses illumination plotted from a radiosity algorithm, or a combination of these two.

Radiosity, also known as Global Illumination, is a method which attempts to simulate the way in which directly illuminated surfaces act as indirect light sources that illuminate other surfaces. This produces more realistic shading and seems to better capture the 'ambience' of an indoor scene. A classic example is the way that shadows 'hug' the corners of rooms.

The optical basis of the simulation is that some diffused light from a given point on a given surface is reflected in a large spectrum of directions and illuminates the area around it.

The simulation technique may vary in complexity. Many renderings have a very rough estimate of radiosity, simply illuminating an entire scene very slightly with a factor known as ambiance. However, when advanced radiosity estimation is coupled with a high quality ray tracing algorithim, images may exhibit convincing realism, particularly for indoor scenes.

In advanced radiosity simulation, recursive, finite-element algorithms 'bounce' light back and forth between surfaces in the model, until some recursion limit is reached. The colouring of one surface in this way influences the colouring of a neighbouring surface, and vice versa. The resulting values of illumination throughout the model (sometimes including for empty spaces) are stored and used as additional inputs when performing calculations in a ray-casting or ray-tracing model.

Due to the iterative/recursive nature of the technique, complex objects are particularly slow to emulate. Advanced radiosity calculations may be reserved for calculating the ambiance of the room, from the light reflecting off walls, floor and celiing, without examining the contribution that complex objects make to the radiosity -- or complex objects may be replaced in the radiosity calculation with simpler objects of similar size and texture.

If there is little rearrangement of radiosity objects in the scene, the same radiosity data may be reused for a number of frames, making radiosity an effective way to improve on the flatness of ray casting, without seriously impacting the overall rendering time-per-frame.

Because of this, radiosity has become the leading real-time rendering method, and has been used from beginning-to-end to create a large number of well-known recent feature-length animated 3D-cartoon films.

### Ray tracing

Ray tracing is an extension of the same technique developed in scanline rendering and ray casting. Like those, it handles complicated objects well, and the objects may be described mathematically. Unlike scanline and casting, ray tracing is almost always a Monte Carlo technique, that is one based on averaging a number of randomly generated samples from a model.

In this case, the samples are imaginary rays of light intersecting the viewpoint from the objects in the scene. It is primarily beneficial where complex and accurate rendering of shadows, refraction or reflection are issues.

In a final, production quality rendering of a ray traced work, multiple rays are generally shot for each pixel, and traced not just to the first object of intersection, but rather, through a number of sequential 'bounces', using the known laws of optics such as "angle of incidence equals angle of reflection" and more advanced laws that deal with refraction and surface roughness.

Once the ray either encounters a light source, or more probably once a set limiting number of bounces has been evaluated, then the surface illumination at that final point is evaluated using techniques described above, and the changes along the way through the various bounces evaluated to estimate a value observed at the point of view. This is all repeated for each sample, for each pixel.

In some cases, at each point of intersection, multiple rays may be spawned.

As a brute-force method, ray tracing has been too slow to consider for real-time, and until recently too slow even to consider for short films of any degree of quality, although it has been used for special effects sequences, and in advertising, where a short portion of high quality (perhaps even photorealistic) footage is required.

However, efforts at optimizing to reduce the number of calculations needed in portions of a work where detail is not high or does not depend on ray tracing features have led to a realistic possibility of wider use of ray tracing. There is now some hardware accelerated ray tracing equipment, at least in prototype phase, and some game demos which show use of real-time software or hardware ray tracing.

## Optimisation

### Optimisations used by an artist when a scene is being developed

Due to the large number of calculations, a work in progress is usually only rendered in detail appropriate to the portion of the work being developed at a given time, so in the initial stages of modelling, wireframe and ray casting may be used, even where the target output is ray tracing with radiosity. It is also common to render only parts of the scene at high detail, and to remove objects that are not important to what is currently being developed.

### Common optimisations for real time rendering

For real-time, it is appropriate to simplify one or more common approximations, and tune to the exact parameters of the scenery in question, which is also tuned to the agreed parameters to get the most 'bang for the buck'.

## Sampling and filtering

One problem that any rendering system must deal with, no matter which approach it takes, is the sampling problem. Essentially, the rendering process tries to depict a continuous function from image space to colors by using a finite number of pixels. As a consequence of the Nyquist theorem, the scanning frequency must be twice the dot rate, which is proportional to image resolution. In simpler terms, this expresses the idea that an image cannot display details smaller than one pixel.

If a naive rendering algorithm is used, high frequencies in the image function will cause ugly aliasing to be present in the final image. Aliasing typically manifests itself as jaggies, or jagged edges on objects where the pixel grid is visible. In order to remove aliasing, all rendering algorithms (if they are to produce good-looking images) must filter the image function to remove high frequencies, a process called antialiasing.

The implementation of a realistic renderer always has some basic element of physical simulation or emulation — some computation which resembles or abstracts a real physical process.

The term "physically-based" indicates the use of physical models and approximations that are more general and widely accepted outside rendering. A particular set of related techniques have gradually become established in the rendering community.

The basic concepts are moderately straightforward, but intractable to calculate; and a single elegant algorithm or approach has been elusive for more general purpose renderers. In order to meet demands of robustness, accuracy, and practicality, an implementation will be a complex combination of different techniques.

Rendering research is concerned with both the adaptation of scientific models and their efficient application.

### The rendering equation

This is the key academic/theoretical concept in rendering. It serves as the most abstract formal expression of the non-perceptual aspect of rendering. All more complete algorithms can be seen as solutions to particular formulations of this equation.

$L_o\left(x, vec w\right) = L_e\left(x, vec w\right) + int_Omega f_r\left(x, vec w\text{'}, vec w\right) L_i\left(x, vec w\text{'}\right) \left(vec w\text{'} cdot vec n\right) dvec w\text{'}$
Meaning: at a particular position and direction, the outgoing light (Lo) is the sum of the emitted light (Le) and the reflected light. The reflected light being the sum of the incoming light (Li) from all directions, multiplied by the surface reflection and incoming angle. By connecting outward light to inward light, via an interaction point, this equation stands for the whole 'light transport' — all the movement of light — in a scene.

### The Bidirectional Reflectance Distribution Function

The Bidirectional Reflectance Distribution Function (BRDF) expresses a simple model of light interaction with a surface as follows:

$f_r\left(x, vec w\text{'}, vec w\right) = frac\left\{dL_r\left(x, vec w\right)\right\}\left\{L_i\left(x, vec w\text{'}\right)\left(vec w\text{'} cdot vec n\right) dvec w\text{'}\right\}$

Light interaction is often approximated by the even simpler models: diffuse reflection and specular reflection, although both can be BRDFs.

### Geometric optics

Rendering is practically exclusively concerned with the particle aspect of light physics — known as geometric optics. Treating light, at its basic level, as particles bouncing around is a simplification, but appropriate: the wave aspects of light are negligible in most scenes, and are significantly more difficult to simulate. Notable wave aspect phenomena include diffraction — as seen in the colours of CDs and DVDs — and polarisation — as seen in LCDs. Both types of effect, if needed, are made by appearance-oriented adjustment of the reflection model.

### Visual perception

Though it receives less attention, an understanding of human visual perception is valuable to rendering. This is mainly because image displays and human perception have restricted ranges. A renderer can simulate an almost infinite range of light brightness and color, but current displays — movie screen, computer monitor, etc. — cannot handle so much, and something must be discarded or compressed. Human perception also has limits, and so doesn't need to be given large-range images to create realism. This can help solve the problem of fitting images into displays, and, furthermore, suggest what short-cuts could be used in the rendering simulation, since certain subtleties won't be noticeable. This related subject is tone mapping.

Mathematics used in rendering includes: linear algebra, calculus, numerical mathematics, signal processing, monte carlo.

Rendering for movies often takes place on a network of tightly connected computers known as a render farm.

The current state of the art in 3-D image description for movie creation is the Mental Ray scene description language designed at mental images and the RenderMan shading language designed at Pixar. (compare with simpler 3D fileformats such as VRML or APIs such as OpenGL and DirectX tailored for 3D hardware accelerators).

Other renderers (including proprietary ones) can and are sometimes used, but most other renderers tend to miss one or more of the often needed features like good texture filtering, texture caching, programmable shaders, highend geometry types like hair, subdivision or nurbs surfaces with tesselation on demand, geometry caching, raytracing with geometry caching, high quality shadow mapping, speed or patent-free implementations. Other highly sought features these days may include IPR and hardware rendering/shading.

## Chronology of important published ideas

• 1968 Ray casting (Appel, A. (1968). Some techniques for shading machine renderings of solids. Proceedings of the Spring Joint Computer Conference 32, 37–49.)
• 1970 Scanline rendering (Bouknight, W. J. (1970). A procedure for generation of three-dimensional half-tone computer graphics presentations. Communications of the ACM)
• 1971 Gouraud shading (Gouraud, H. (1971). Computer display of curved surfaces. IEEE Transactions on Computers 20 (6), 623–629.)
• 1974 Texture mapping (Catmull, E. (1974). A subdivision algorithm for computer display of curved surfaces. PhD thesis, University of Utah.)
• 1974 Z-buffering (Catmull, E. (1974). A subdivision algorithm for computer display of curved surfaces. PhD thesis)
• 1975 Phong shading (Phong, B-T. (1975). Illumination for computer generated pictures. Communications of the ACM 18 (6), 311–316.)
• 1976 Environment mapping (Blinn, J.F., Newell, M.E. (1976). Texture and reflection in computer generated images. Communications of the ACM 19, 542–546.)
• 1977 Shadow volumes (Crow, F.C. (1977). Shadow algorithms for computer graphics. Computer Graphics (Proceedings of SIGGRAPH 1977) 11 (2), 242–248.)
• 1978 Shadow buffer (Williams, L. (1978). Casting curved shadows on curved surfaces. Computer Graphics (Proceedings of SIGGRAPH 1978) 12 (3), 270–274.)
• 1978 Bump mapping (Blinn, J.F. (1978). Simulation of wrinkled surfaces. Computer Graphics (Proceedings of SIGGRAPH 1978) 12 (3), 286–292.)
• 1980 BSP trees (Fuchs, H., Kedem, Z.M., Naylor, B.F. (1980). On visible surface generation by a priori tree structures. Computer Graphics (Proceedings of SIGGRAPH 1980) 14 (3), 124–133.)
• 1980 Ray tracing (Whitted, T. (1980). An improved illumination model for shaded display. Communications of the ACM 23 (6), 343–349.)
• 1981 Cook shader (Cook, R.L., Torrance, K.E. (1981). A reflectance model for computer graphics. Computer Graphics (Proceedings of SIGGRAPH 1981) 15 (3), 307–316.)
• 1983 MIP maps (Williams, L. (1983). Pyramidal parametrics. Computer Graphics (Proceedings of SIGGRAPH 1983) 17 (3), 1–11.)
• 1984 Octree ray tracing (Glassner, A.S. (1984). Space subdivision for fast ray tracing. IEEE Computer Graphics & Applications 4 (10), 15–22.)
• 1984 Alpha compositing (Porter, T., Duff, T. (1984). Compositing digital images. Computer Graphics (Proceedings of SIGGRAPH 1984) 18 (3), 253–259.)
• 1984 Distributed ray tracing (Cook, R.L., Porter, T., Carpenter, L. (1984). Distributed ray tracing. Computer Graphics (Proceedings of SIGGRAPH 1984) 18 (3), 137–145.)
• 1984 Radiosity (Goral, C., Torrance, K.E., Greenberg D.P., Battaile, B. (1984). Modelling the interaction of light between diffuse surfaces. Computer Graphics (Proceedings of SIGGRAPH 1984) 18 (3), 213–222.)
• 1985 Hemicube radiosity (Cohen, M.F., Greenberg, D.P. (1985). The hemi-cube: a radiosity solution for complex environments. Computer Graphics (Proceedings of SIGGRAPH 1985) 19 (3), 31–40.)
• 1986 Light source tracing (Arvo, J. (1986). Backward ray tracing. SIGGRAPH 1986 Developments in Ray Tracing course notes)
• 1986 Rendering equation (Kajiya, J. (1986). The rendering equation. Computer Graphics (Proceedings of SIGGRAPH 1986) 20 (4), 143–150.)
• 1987 Reyes rendering (Cook, R.L., Carpenter, L., Catmull, E. (1987). The reyes image rendering architecture. Computer Graphics (Proceedings of SIGGRAPH 1987) 21 (4), 95–102.)
• 1991 Hierarchical radiosity (Hanrahan, P., Salzman, D., Aupperle, L. (1991). A rapid hierarchical radiosity algorithm. Computer Graphics (Proceedings of SIGGRAPH 1991) 25 (4), 197–206.)
• 1993 Tone mapping (Tumblin, J., Rushmeier, H.E. (1993). Tone reproduction for realistic computer generated images. IEEE Computer Graphics & Applications 13 (6), 42–48.)
• 1993 Subsurface scattering (Hanrahan, P., Krueger, W. (1993). Reflection from layered surfaces due to subsurface scattering. Computer Graphics (Proceedings of SIGGRAPH 1993) 27 165–174.)
• 1995 Photon mapping (Jensen, H.W., Christensen, N.J. (1995). Photon maps in bidirectional monte carlo ray tracing of complex objects. Computers & Graphics 19 (2), 215–224.)
• 1997 Metropolis light transport (Veach, E., Guibas, L. (1997). Metropolis light transport. Computer Graphics (Proceedings of SIGGRAPH 1997) 16 65–76.)
• 1997 Instant Radiosity (Keller, A. (1997). Instant Radiosity. Computer Graphics (Proceedings of SIGGRAPH 1997) 24, 49–56.)
• 2002 Precomputed Radiance Transfer (Sloan, P., Kautz, J., Snyder, J. (2002). Precomputed Radiance Transfer for Real-Time Rendering in Dynamic, Low Frequency Lighting Environments. Computer Graphics (Proceedings of SIGGRAPH 2002) 29, 527–536.)

## Books and summaries

• Pharr; Humphreys (2004). Physically Based Rendering. Morgan Kaufmann. ISBN 0-12-553180-X.
• Shirley; Morley (2003). Realistic Ray Tracing (2nd ed.). AK Peters. ISBN 1-56881-198-5.
• Dutre; Bala; Bekaert (2002). Advanced Global Illumination. AK Peters. ISBN 1-56881-177-2.
• Akenine-Moller; Haines (2002). Real-time Rendering (2nd ed.). AK Peters. ISBN 1-56881-182-9.
• Strothotte; Schlechtweg (2002). Non-Photorealistic Computer Graphics. Morgan Kaufmann. ISBN 1-55860-787-0.
• Gooch; Gooch (2001). Non-Photorealistic Rendering. AKPeters. ISBN 1-56881-133-0.
• Jensen (2001). Realistic Image Synthesis Using Photon Mapping. AK Peters. ISBN 1-56881-147-0.
• Blinn (1996). Jim Blinns Corner - A Trip Down The Graphics Pipeline. Morgan Kaufmann. ISBN 1-55860-387-5.
• Glassner (1995). Principles Of Digital Image Synthesis. Morgan Kaufmann. ISBN 1-55860-276-3.
• Cohen; Wallace (1993). Radiosity and Realistic Image Synthesis. AP Professional. ISBN 0-12-178270-0.
• Foley; Van Dam; Feiner; Hughes (1990). Computer Graphics: Principles And Practice. Addison Wesley. ISBN 0-201-12110-7.
• Glassner (ed.) (1989). An Introduction To Ray Tracing. Academic Press. ISBN 0-12-286160-4.
• Description of the 'Radiance' system


text:
## Algebra and Trigonometry 10th Edition

Published by Cengage Learning

# Chapter 10 - Review Exercises - Page 763: 101

#### Answer

$-6$

#### Work Step by Step

The general form of a matrix of order $2 \times 2$ is: $det \ A=\begin{bmatrix} p & q \\ r & s\end{bmatrix}=ps-qr$ Since Row-1 has the most zeroes, we choose $R_1$. It has sign array $(+,+)$ as we go to the right. Now, $det \ A =-2 \begin{bmatrix} -1 & 0 \\ 1 & -3 \end{bmatrix}-0+0=-2(3-0)=-6$

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:
Plotting the solution of an integral equation

Posted 3 months ago
885 Views
|
10 Replies
|
6 Total Likes
|
 Hello All, I tried plotting the solution of the integral equations in this notebook, but the plot function gives empty plot. The solution contains Hypergeometric functions. Please guide what needs correction. Thanks.
10 Replies
Sort By:
Posted 3 months ago
 Your second integral is poorly typed. You almost surely need to insert a space between c and e. I wonder if c and C are meant to be different parameters. Then you set up an equation but you don't solve it. The equation does not depend on x, but you try to plot it as a function of x, which does not make much sense. Also, before plotting I suppose you need to give numerical values to most parameters.
Posted 3 months ago
 This is the updated notebook with numerical values for the coefficients(and yes, c and C are two different parameters). Now, the notebook contains only one integral equation whose solution needs to be plotted for the value of k=2.5. Thanks for your response.
Posted 3 months ago
 You what plot of T vs x, but where is x in integral solution ?There is only T.
Posted 3 months ago
 Your equation does not depend on x, only on T: diff = Subtract @@ Simplify[sol, T > 0]; Plot[diff, {T, 0, 2}] FindRoot[diff == 0, {T, 1.7}] There is a value of T that makes the two integrals equal.
Posted 3 months ago
 Alright. so, the plot should be over a wide range of values of T, but when i change the range in the Plot command from say {T, 0, 10}, the values go infinite. i have attached the updated notebook in which i have tried to plot T from 0 to 10. And the attached image shows how the actual plot should look like(here i have used k=2.5, so blue curve is relevant).
Posted 3 months ago
 A = 0.3136; B = 0.0692; c0 = 0.6207; a = 1.29; b = 0.1101; c = 3.014; sol[T_, k_] := NIntegrate[x (1 + x/((k - 3/2) T))^(-k - 1), {x, 0, Infinity}] - NIntegrate[ x (1 + x/((k - 3/2) T))^(-k - 1) (c*E^(-(x/a)) - c*E^(-x/b) - B*E^(-c0*x) + A), {x, 0, Infinity}] Plot[sol[T, 2.5], {T, 0, 3}](*for: k=2.5*) FindRoot[sol[T, 2.5], {T, 2},WorkingPrecision -> 20] (*{T ->1.7115048830163596308}*) The plot is different because it is not normalized.
Posted 3 months ago
 Oh okay. So, how can I normalize it?
Posted 3 months ago
 I don't know what functions are plotted in the book. However, in your own plot you need to increase the precision because there are numerical instabilities for larger values of T: diffExact = Rationalize[diff, 0]; Plot[diffExact, {T, 0, 10}, WorkingPrecision -> 30, PlotRange -> {-2, 1.5}]


text:
# The optimal step gradient method and applications

In this article, we propose an exercise which describes the optimal method of the step gradient for coercive functions on spaces of finite dimension. These specific problems are used in optimization theory and some applications in finance.

Problem: Let $f:\mathbb{R}^n\to \mathbb{R}$ be a function of class $C^1$. Suppose that there exists a real number $\alpha>0$ such that \begin{align*} \forall (u,v)\in \mathbb{R}^n\times \mathbb{R}^n,\qquad \langle \nabla f(v)-\nabla f(u),v-u\rangle \;\ge\alpha \|v-u\|^2. \end{align*}

• Prove that \begin{align*} \forall (u,v)\in \mathbb{R}^n\times \mathbb{R}^n,\qquad f(v)\ge f(u)+ \langle\nabla f(u),v-u\rangle+\frac{\alpha}{2} \|v-u\|^2. \end{align*}
• Deduce that $f$ admits a global minimum on $\mathbb{R}^n$, reached in a unique point that will be denoted by $a$.
• Let $u\in \mathbb{R}^n\backslash\{a\}$. Consider the function \begin{align*}\varphi_u:\mathbb{R}\to \mathbb{R},\quad t\mapsto f(u+t\nabla f(u)). \end{align*} Prove that $\varphi_u$ admits a global minimum on $\mathbb{R},$ reached in a unique point. This allows us to define a sequence $(u_k)_{k\ge 0}$ in $\mathbb{R}^n$ such that: $u_0\in \mathbb{R}^n$ ; if $k_k=a,$ we select $u_{k+1}=a,$ if not, let $t_k$ be the unique real number such that $\varphi_{u_k}(t_k)=\min(\varphi_{u_k})$. We then set \begin{align*} u_{k+1}=u_k+t_k \nabla f(u_k). \end{align*}
• Verify that for any $k\in\mathbb{N},$ $\nabla f(u_k)\bot \nabla f(u_{k+1})$.
• Prove that the series $(u_{k+1}-u_k)_{k\ge 0}$; $(\nabla f(u_{k+1})-\nabla f(u_k))_{k\ge 0}$ and $(\nabla f(u_k))_{k\ge 0}$ the suites tend towards $0$. Deduce that $u_k\to a$ as $k\to\infty$.


text:
×

# TSHIRTS - Editorial

Author: Lalit Kundu
Tester: Praveen Dhinwa and Hiroto Sekido
Editorialist: Lalit Kundu

EASY-MEDIUM

# PROBLEM:

There are N(<11) persons. Each person has his collection of distinct tshirts. What are the total number of different such arrangements such in which no two people wear same kind of tshirt. A person can have atmost 100 distinct tshirts.

# EXPLANATION:

It is a very standard kind of Dynamic Programming with bitmasking. So the idea here is to keep a 2-D array DP[2N][K], where DP[i][j] will store the answer only if tshirts from id 1 to j have been used. Also, let's say i when denoted in binary be b1,b2...bn. If bp(1 ≤ p ≤ n) is 1, it means that person with id==p has been alloted a tshirt and all persons with bits 1 are assigned distinct tshirts.
So, we'll write a recursive DP, which is obviously easier to write.
We keep a function rec(mask, tid) which means that tshirts till id tid have been processed and mask denotes which persons have been given tshirts. At each step we assign tshirts to each possible person and recursively calculate the number of ways.a
Following pseudo code will make it more clear.

dp[1<<N][K]={}
memset dp to -1    // dp[i][j]=-1 means it hasn't been calculated yet
def rec(mask, tid):  // tid denotes the tshirt id
if mask==2**(N)-1:  // all bits are set, all persons have been alloted tshirts
if tid==101:    // all tshirts finished
return 0
if dp[mask][tid]!=-1:   // it has already been calculated, we won't calculate it again
ans=0
ans += rec(mask,tid+1)  // the case when we don't assign tshirt with id=tid to anyone
// the case when we assign tshirt with id=tid to someone
// we will assign the tshirt with id=tid to all possible persons we can, and add to answer the respective number of ways
// note that we are assigning distinct tshirts only, since tshirt with id=tid has never been assigned before to anyone.
for persons p(0<=p<=N-1) which have tshirt with id=tid:
if mask&(1<<p): // person p + 1 has already been alloted a tshirt
continue    // do nothing

Our answer will be rec(0,1) ie. starting with mask=0(no one has been assigned any tshirt) and tid=1. Complexity will be in worst case O(K*2N).

# FURTHER LINKS AND SIMILAR PROBLEMS

This question is marked "community wiki".

3.0k93164187
accept rate: 12%

can anyone tell me bottom up approach to this problem. i m not able to figure out how to define state in this problem.

(19 Aug '14, 22:35)

 13 The pseudo code accesses dp[mask][tid]. dp has size dp[1<
 5 Shouldn't the expression in line 4 be - if mask==(2**N)-1:  answered 11 Aug '14, 19:09 126●1●3 accept rate: 20%
 3 Also, the dp[][] array should be - const int K=101; dp[1<
 2 Can you please provide some corner test cases. I am getting WA. answered 11 Aug '14, 17:20 16●2●3 accept rate: 0%
 2 How will u have a number with 100 bits?? Are doing it using array, then you can't perform bitwise operators directly?? answered 11 Aug '14, 17:36 81●1●5 accept rate: 0% 1 The number just needs 10 bits for the number of people. The tee shirt numbers are not part of the bitmask. (11 Aug '14, 21:50)
 2 What if a person doesn't have that TSHIRT ? answered 11 Aug '14, 18:09 26●1●1●4 accept rate: 0% 1 Then don't recurse. The code isn't present, but the idea is represented as a comment. (11 Aug '14, 21:52) He is definately oing 2 have a shirt read the question carefully,it says each person has atleast 1 shirt (12 Dec '16, 19:56) vchhabra2★
 1 good tutorial :D .. helped a lot answered 04 Jun '15, 04:04 1★snehil92 95●2●2 accept rate: 0%
 0 I think the complexity will be O( 2^N * K * N ) . Morover, if someone wants to see a backward implementation of this problem, can check my submission . Also, One can check a very similar problem ASSIGN on spoj. This problem + ASSIGN on spoj gives you two or more ways of solving this problem. In general when we need a set we can have options !! That is a very beautiful thing! One should learn that rather learn should feel that !! answered 23 Jul '15, 02:14 2★xlee 13●1 accept rate: 0%
 0 http://ideone.com/dTD9nL Can someone tell me where im going wrong ? answered 02 Oct '15, 10:14 1 accept rate: 0%
 0 answered 28 Jun '17, 16:57 1 accept rate: 0%
 0 in the solution if (mask == p) then 111 is returned and if not 011 is returned where p is all set mask . Can somebody tell me why? Because there no mention about it in the pseudo code answered 26 Aug '17, 14:23 4★sonu_628 345●8 accept rate: 8%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,682
×2,172
×1,672
×281
×33
×21

question asked: 11 Aug '14, 15:13

question was seen: 14,114 times

last updated: 26 Aug '17, 15:52


text:
0

# Section 1.3 - Adequate Sets of Connectives

The adequacy of connectives is novel, but I feel it distracts from the potential of variable truth functions. I suffered the section, but I with the exception of naming joint and alternative denail, I can't say I got much from it.

#### Concepts and Vocabulary

• Joint Denial: A binary truth function that only returns one when both inputs are zero. $$\begin{array}{c|c|c|c} A & B & A\downarrow B & (A,B)_\mathtt{0x1} \\ \hline 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \end{array}$$
• Alternative Denial: A binary function that returns one for all input conditions except when both inputs are one. $$\begin{array}{c|c|c|c} A & B & A\big| B & (A,B)_\mathtt{0x7} \\ \hline 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{array}$$
• Literal: A variable or its negation.
• Disjunctive Normal Form (dnf): A disjunction of conjunctions.
• Conjunctive Normal Form (cnf): A conjunction of disjunctions.
• (Degenerate) Conjunction: A literal.
• (Degenerate) Disjunction: A literal.
• Full dnf or cnf: A disjunction of conjunctions where each conjunction contains all the same variables, or a conjunction of disjunctions where each disjunction contains all the same variables.
• Resolution: A complete and total mess.
• $Res(\mathscr{B})$: A continuation of the pain above.
• Blatant Contradiction: A variable and its negation in a conjunction.
• Craig's Interpolation Theorem: If $\mathscr{B}\Rightarrow\mathscr{D}$ and $\mathscr{B}$ and $\mathscr{D}$ have some variables in common, then there exists a $\mathscr{C}$ such that $\mathscr{B}\Rightarrow\mathscr{C}$ and $\mathscr{C}\Rightarrow\mathscr{D}$

#### Propositions

Proposition 1.5

Every truth function is generated by a statement form involving the connectives $\neg$, $\land$, and $\vee$.

Proposition 1.6

Every truth function can be generated by a statement form containing as connectives only $\land$ and $\neg$, or only $\vee$ and $\neg$, or only $\Rightarrow$ and $\neg$.

Proposition 1.7

The only binary connectives that alone are adequate for the construction of all truth functions are $\downarrow$ and $\big|$.


text:
# Triple integral

## Homework Statement

evaluate ysinx from z= 0 to (1-y2)1/2, y = 0 to 1, x = 0 to pi

## The Attempt at a Solution

heres my work

-1/2sinx $$\int(1-y^2)^1/2 y dy$$ from 0 to 1 =
$$\int1/3*sinx dx$$ from 0 to pi = 2/3

## Answers and Replies

Related Calculus and Beyond Homework Help News on Phys.org
Dick