4
$\begingroup$

Can anyone point me in the direction of good introductory material on the use of mathematical notation in the field of computer science? I often come across notation in research papers that I don't understand and I would like to at least have an overview of its meaning/intent, if not a thorough understanding. I don't have much of a mathematical background and don't expect to become an expert in this field overnight but any ideas would be appreciated.

UPDATE: The kind of notation I've been having trouble with can be seen on page three of this article. Note: this isn't an article I've been using for research, it's just the first publicly available example I came across!

  • 0
    Do you have problem with later pages than three? Because for them, you should become familiar with the probabilistic language, for that case, I can say a few words.2013-01-10

5 Answers 5

6

That's set theory. I honestly recommend that you study set theory, as nowdays all mathematics are built on sets. Just pick any introductory book to set theory, that ill be (imo) enough.

Now, what you may having difficulties with, is the interpretation of those things, let's take an example from that page:

Given the set of N observations Y = {yi ; i = 1, . . . , N } we want to identify which observations belong to the same object.

This basically mean that $Y$ is a set containing observations, more simple (not so formal) translation could be: "We have a bunch of observations".

We are looking for a partition ω of observations from Y into several trajectories Yk ⊂ Y (subsets of Y ) such that each trajectory collects observations believed to come from a single person.

This now means that $\omega$ (defined in the next parragraph) is a partition from a space of partitions, and you're looking for subsets, that they call $Y_k$ that is believed to belong to the same person. Now the translation: "We are looking for observations that we believe belong to the same person, and we are going to separate the observations that belong to every person in different groups (sets)".

A valid partition expresses the set of all observations as an exhaustive union of trajectories: Y = Y1 ∪ . . . ∪ YKω , where Kω is the number of objects proposed by a partition ω. The trajectories must be mutually exclusive: Y ∩ Yk = ∅, when = k.

And last, they say a valid $\omega$ must have trajectories that contain (alltogether) the initial set $Y$, and that this trayectories' intersection must be empty. The translation: "The partition must have all subsets of observations, that means we must have formed groups that cover all observations, and two different subsets of observations cannot share a member, that would be obviously absurd, if we had two belonging to person A, and another two belonging to person B, and one of those two was repeated, then A and B would be the same person"

That goes on for the whole article. The final parragraph means:

We have a bunch of observations. We are looking for observations that we believe belong to the same person, and we are going to separate the observations that belong to every person in different groups (sets), that separation is called "partition". The partition must have all subsets of observations, that means we must have formed groups that cover all observations, and two different subsets of observations cannot share a member, that would be obviously absurd, if we had two belonging to person A, and another two belonging to person B, and one of those two was repeated, then A and B would be the same person.

This notation is used because it doesn't let space for ambiguity, and is more rigouruos, so besides studying set theory, which is basic, you should train you interpretation of these articles (just read more and try to do what I've done here)

BTW, I don't think there's any book about mathematical notation for computer science (it would really surprise me), because such thing doesn't exist, that's just mathematical/formal notation.

  • 0
    Thanks for substantial, detailed answer. Really useful points on the notation itself and the wider use of mathematical notation in academic papers and computer science.2013-01-11
2

It looks like the notation you've referenced is from set theory. I know the first chapters of this book discuss set theory somewhat. It's a free reference, so it doesn't cost anything but time to look at...

I haven't formally covered set theory yet in my curriculum, so I don't know of any other books to suggest... Perhaps look in your discrete math book?

2

The notation from the article you linked to is entirely from set theory. Any textbook from a discrete mathematics course should cover these notations and concepts reasonably well. "Discrete Mathematics with Applications" by Susana Epp was a good introduction and seems to be used a lot in computer science departments.

If you need to improve your background in mathematics for computer science, then I strongly recommend reading and working through Knuth's "The Art of Computer Programming" books.

2

Look at chapter one of this book, "Schaum's Outline of Set Theory and Related Topics". It's a short chapter and should cover all the notion on that page. You can also quickly look at this book, "Schaum's Outline of Probability, Random Variables, and Random Processes". Chapter one of this book has both the set theory notation, and the probability notation at the bottom of the page. They are both very simple books, without a lot of explanation, so it shouldn't take you very long to familiarize yourself with just the notation.

More broadly, the paper you provided looks like machine learning, a good introductory book is "Machine Learning: A Probabilistic Perspective". A review of probability starts on page 28. There is section called 'Notation' at the end of the book which lists some general machine learning notation.

1

I have used this Theoretical Computer Science Cheat Sheet to answer most of my questions.

  • 1
    @CMCDr$a$gonkai, My work-around was taking the .ps file to a print shop, where they printed and laminated for me.2015-02-15